Invatare Atomica

Coada — structura FIFO

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei intelege principiul FIFO (First In, First Out), vei sti sa implementezi o coada in Python cu collections.deque si vei aplica operatiile fundamentale enqueue si dequeue. Sectiunile marcate ⚡ EXCLUSIV INTENSIV acopera implementarea in C++ si coada circulara.

Dupa aceasta lectie vei putea:

  • Sa definesti principiul FIFO si sa il distingi de LIFO (stiva)
  • Sa implementezi o coada in Python cu collections.deque
  • Sa aplici operatiile enqueue, dequeue, front, este_vida cu complexitate O(1)
  • Sa argumentezi de ce list.pop(0) este O(n) iar deque.popleft() este O(1)
  • Sa modelezi probleme reale cu o coada (ghiseu, planificator de procese)
  • ⚡ (Intensiv) Sa folosesti std::queue in C++ cu push/pop/front/back
  • ⚡ (Intensiv) Sa construiesti o coada circulara cu tablou si indici modulo

Incearca singur!

Provocare:

La un ghiseu vin pe rand: Ion, apoi Maria, apoi Andrei. Ghiseul serveste in ordinea sosirii. Daca se mai aseaza Pavel la rand dupa Andrei, scrie ordinea completa in care vor fi serviti toti patru si explica in doua cuvinte principiul care guverneaza aceasta ordine.

💡 Ai nevoie de un indiciu?

Primul care a intrat in coada (Ion) este primul servit. Aceasta este proprietatea FIFO: First In, First Out.

Ordinea: Ion → Maria → Andrei → Pavel.

1

1. Ce este coada? Principiul FIFO

O coada (en. queue) este o structura de date liniara care respecta principiul FIFO (First In, First Out): elementul adaugat cel mai devreme este si primul eliminat. Adaugarea se face la un capat numit rear (spate), iar eliminarea la celalalt capat, front (fata).
Coada (FIFO) vs Stiva (LIFO):

Coada (FIFO): rand la ghiseu — primul sosit, primul servit.
Stiva (LIFO): teanc de farfurii — ultima pusa, prima luata.

Operatii coada: enqueue(x) — adauga la spate; dequeue() — scoate din fata. Ambele sunt O(1) cu implementarea corecta.

Diagrama structura FIFO:
  enqueue(A)  enqueue(B)  enqueue(C)
  +-------+-------+-------+
  |   A   |   B   |   C   |
  +-------+-------+-------+
  ^                       ^
FRONT                   REAR
(dequeue de aici)  (enqueue aici)

  dequeue() --> returneaza A (primul intrat)
2

2. Implementare Python cu collections.deque

Python ofera collections.deque ca implementare eficienta pentru coada. append() adauga la spate — O(1). popleft() scoate din fata — O(1). Comparativ, list.pop(0) este O(n) deoarece deplaseaza toate elementele ramase.
# Demonstratie: Coada FIFO cu lista Python
from collections import deque

coada = deque()

# Enqueue (adaugare la coada)
coada.append("Alice")
coada.append("Bob")
coada.append("Carol")

print("Dupa enqueue Alice, Bob, Carol:")
print("Coada:", list(coada))
print("Front (primul):", coada[0])
print("Rear (ultimul):", coada[-1])

# Dequeue (scoatere din fata)
primul = coada.popleft()
print("\nDupa dequeue:")
print("Scos:", primul)
print("Coada acum:", list(coada))
Output real (rulat cu python):
Dupa enqueue Alice, Bob, Carol:
Coada: ['Alice', 'Bob', 'Carol']
Front (primul): Alice
Rear (ultimul): Carol

Dupa dequeue:
Scos: Alice
Coada acum: ['Bob', 'Carol']
3

3. Clasa Coada — interfata explicita

Implementam o clasa Coada care incapsuleaza un deque si expune interfata standard: enqueue, dequeue, front, este_vida, dimensiune. Toate operatiile sunt O(1).
from collections import deque

class Coada:
    def __init__(self):
        self.elemente = deque()

    def enqueue(self, valoare):
        """Adauga la spate (rear) - O(1)"""
        self.elemente.append(valoare)

    def dequeue(self):
        """Scoate din fata (front) - O(1)"""
        if self.este_vida():
            raise IndexError("Coada este vida!")
        return self.elemente.popleft()

    def front(self):
        """Returneaza primul element fara al elimina - O(1)"""
        if self.este_vida():
            raise IndexError("Coada este vida!")
        return self.elemente[0]

    def este_vida(self):
        return len(self.elemente) == 0

    def dimensiune(self):
        return len(self.elemente)

    def __str__(self):
        return "Coada: " + str(list(self.elemente)) + " (front -> rear)"

# Test
c = Coada()
c.enqueue(10)
c.enqueue(20)
c.enqueue(30)
print(c)
print("front():", c.front())
print("dequeue():", c.dequeue())
print(c)
print("dimensiune():", c.dimensiune())
Output real (rulat cu python):
Coada: [10, 20, 30] (front -> rear)
front(): 10
dequeue(): 10
Coada: [20, 30] (front -> rear)
dimensiune(): 2
Complexitate toate operatiile:

enqueue(x) — adauga la rear: O(1)
dequeue() — elimina din front: O(1)
front() — citeste capul fara eliminare: O(1)
este_vida() — test gol: O(1)
dimensiune() — numara elemente: O(1)

4

4. Aplicatie: Simulare ghiseu banca

Coada este structura naturala pentru orice sistem unde ordinea de intrare = ordinea de procesare: ghiseu banca, coada imprimanta, planificator procese OS, parcurgere BFS in grafuri.
from collections import deque

print("=== Simulare ghiseu banca ===")
ghiseu = deque()

# Sosesc clienti
clienti_sositi = ["Ion", "Maria", "Andrei", "Elena", "Mihai"]
for client in clienti_sositi:
    ghiseu.append(client)
    print(f"  {client} s-a asezat la coada. Coada: {list(ghiseu)}")

print()
print("Servire clienti:")
numar_servit = 0
while ghiseu:
    client_servit = ghiseu.popleft()
    numar_servit += 1
    print(f"  Servit clientul {numar_servit}: {client_servit}. Ramasi: {list(ghiseu)}")
print("Toti clientii au fost serviti!")
Output real (rulat cu python):
=== Simulare ghiseu banca ===
  Ion s-a asezat la coada. Coada: ['Ion']
  Maria s-a asezat la coada. Coada: ['Ion', 'Maria']
  Andrei s-a asezat la coada. Coada: ['Ion', 'Maria', 'Andrei']
  Elena s-a asezat la coada. Coada: ['Ion', 'Maria', 'Andrei', 'Elena']
  Mihai s-a asezat la coada. Coada: ['Ion', 'Maria', 'Andrei', 'Elena', 'Mihai']

Servire clienti:
  Servit clientul 1: Ion. Ramasi: ['Maria', 'Andrei', 'Elena', 'Mihai']
  Servit clientul 2: Maria. Ramasi: ['Andrei', 'Elena', 'Mihai']
  Servit clientul 3: Andrei. Ramasi: ['Elena', 'Mihai']
  Servit clientul 4: Elena. Ramasi: ['Mihai']
  Servit clientul 5: Mihai. Ramasi: []
Toti clientii au fost serviti!
5

5. Coada in C++ cu std::queue EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

Biblioteca standard C++ ofera std::queue (header <queue>). Operatii: push(x) (enqueue), pop() (elimina din front, nu returneaza), front() (citeste capul), back() (citeste coada), size(), empty(). Toate sunt O(1).

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;

    // push() = enqueue
    q.push(10);
    q.push(20);
    q.push(30);

    cout << "Dimensiune: " << q.size() << endl;
    cout << "Front (primul): " << q.front() << endl;
    cout << "Back (ultimul): " << q.back() << endl;

    // Citim front() inainte de pop() (pop nu returneaza valoarea)
    cout << "Dequeue: " << q.front() << endl;
    q.pop();

    cout << "Dupa dequeue, front: " << q.front() << endl;
    cout << "Dimensiune acum: " << q.size() << endl;

    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
Dimensiune: 3
Front (primul): 10
Back (ultimul): 30
Dequeue: 10
Dupa dequeue, front: 20
Dimensiune acum: 2
Python vs C++ — diferenta de design:

Python deque: popleft() — scoate SI returneaza valoarea intr-un apel.
C++ std::queue: front() citeste, pop() elimina — doua apeluri separate. Motivul: pop() nu face copie inutila a valorii (eficienta la tipuri mari).

6

6. Coada circulara cu tablou EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

Implementarea cu tablou static si doi indici (front, rear) devine circulara prin operatorul modulo %. Avantaj: reutilizeaza spatiul eliberat prin dequeue, fara deplasarea elementelor. Enqueue si dequeue raman ambele O(1).

#include <iostream>
using namespace std;

const int MAXN = 5;

struct CoadaCirculara {
    int date[MAXN];
    int front, rear, dimensiune;

    CoadaCirculara() : front(0), rear(0), dimensiune(0) {}

    bool esteVida()  { return dimensiune == 0; }
    bool estePlina() { return dimensiune == MAXN; }

    void enqueue(int val) {
        if (estePlina()) {
            cout << "Coada plina! Nu se poate adauga " << val << endl;
            return;
        }
        date[rear] = val;
        rear = (rear + 1) % MAXN;
        dimensiune++;
    }

    int dequeue() {
        if (esteVida()) { return -1; }
        int val = date[front];
        front = (front + 1) % MAXN;
        dimensiune--;
        return val;
    }

    int getFront() { return date[front]; }
};

int main() {
    CoadaCirculara c;
    c.enqueue(1);
    c.enqueue(2);
    c.enqueue(3);
    cout << "front: " << c.getFront() << ", dim: " << c.dimensiune << endl;
    cout << "dequeue: " << c.dequeue() << endl;
    c.enqueue(4);
    cout << "front: " << c.getFront() << ", dim: " << c.dimensiune << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
front: 1, dim: 3
dequeue: 1
front: 2, dim: 3
De ce circulara?

Fara modulo, dupa N dequeue-uri, front ajunge la sfarsitul tabloului si spatiul din fata nu se mai poate reutiliza chiar daca exista locuri libere. Formula (rear + 1) % MAXN face indicele sa se intoarca la 0, permitand reutilizarea continua fara realocare.

Exercitii practice

Exercitiul 1 (Nivel minim) — Urmarire manuala

Fie urmatoarea secventa de operatii pe o coada initial vida:

enqueue(5), enqueue(3), enqueue(8), dequeue(), enqueue(1), dequeue()

a) Ce elemente raman in coada dupa toate operatiile?
b) Ce valori au returnat cele doua operatii dequeue()?
c) Care este valoarea returnata de front() la final?

Exercitiul 2 (Nivel standard) — Palindrom cu coada si stiva

Scrie o functie Python este_palindrom(sir) care foloseste simultan o coada (deque) si o stiva (list) si returneaza True daca sirul este palindrom, False altfel.

Exemplu: "racecar" → True, "hello" → False.

Indiciu: Pune toate caracterele in coada (append) si in stiva (append). Compara popleft() cu pop() pentru fiecare pozitie.

Exercitiul 3 (Nivel performanta) — Simulare printer INTENSIV

Simuleaza o imprimanta de retea cu o coada de documente. Fiecare document are id, prioritate (1-5, informativa) si numar de pagini. Implementeaza clasa PrinterQueue cu:

  • add_job(id, prioritate, pagini) — adauga la coada
  • print_next() — printeaza documentul din fata (afiseaza id + pagini)
  • total_pages_waiting() — returneaza suma paginilor in asteptare

Testare: adauga 3 documente, printeaza 2, calculeaza paginile ramase.

Nota: Aceasta este o coada FIFO simpla (nu coada de prioritati; prioritatea e doar informativa).

Ce ai invatat astazi

  • Principiul FIFO: First In, First Out — primul intrat este primul iesit
  • enqueue (adauga la rear) si dequeue (scoate din front): ambele O(1) cu deque
  • collections.deque: append() = enqueue, popleft() = dequeue
  • Clasa Coada cu interfata explicita: enqueue, dequeue, front, este_vida, dimensiune
  • Aplicatie: simulare ghiseu — ordinea servirii = ordinea sosirii
  • list.pop(0) este O(n); deque.popleft() este O(1) — diferenta de mii de ori la volum mare
  • INTENSIV std::queue C++: push(), front() + pop() (doua apeluri separate)
  • INTENSIV Coada circulara: (front/rear + 1) % MAXN, reutilizare spatiu, O(1)

Urmatoarea lectie

Continua cu Lectia 4 — Aplicatii cu cozi: simulare procese, BFS preview, deque.

Continua →