1
1. Recapitulare: coada FIFO si deque in Python
O coada (queue) este o structura FIFO: primul element intrat este primul care iese. In Python,
collections.deque implementeaza o coada eficienta cu O(1) la ambele capete.Analogie: randul la ghiseu
Prima persoana venita este prima servita. Ordinea de intrare = ordinea de iesire. Nu poti sari sau intra pe la spate.
from collections import deque coada = deque() coada.append("Ana") # enqueue: adaugam la spate O(1) coada.append("Bogdan") coada.append("Cristi") print("Coada initiala:", list(coada)) print("Lungime:", len(coada)) print(" Servire clienti:") while coada: client = coada.popleft() # dequeue: scoatem din fata O(1) print(f" Servit: {client} | Ramas in coada: {list(coada)}")
Output real (python coada_test1.py):
Coada initiala: ['Ana', 'Bogdan', 'Cristi'] Lungime: 3 Servire clienti: Servit: Ana | Ramas in coada: ['Bogdan', 'Cristi'] Servit: Bogdan | Ramas in coada: ['Cristi'] Servit: Cristi | Ramas in coada: []
De ce NU list.pop(0)?
list.pop(0) este O(n): deplaseaza toate elementele. deque.popleft() este O(1). Pentru cozi cu mii de elemente, diferenta este critica.
| Operatie | list Python | collections.deque |
|---|---|---|
| Adaugare la spate | append(x) — O(1) | append(x) — O(1) |
| Extragere din fata | pop(0) — O(n) | popleft() — O(1) |
| Acces la primul element | [0] — O(1) | [0] — O(1) |
2
2. Simulare: coada de imprimanta
Simularea cu coada modeleaza un sistem real unde evenimentele se proceseaza in timp, in ordine FIFO. Joburile de imprimanta se proceseaza in ordinea sosirii, indiferent de utilizator.
from collections import deque imprimanta = deque() imprimanta.append({"id": 1, "pagini": 3, "utilizator": "Ana"}) imprimanta.append({"id": 2, "pagini": 1, "utilizator": "Bogdan"}) imprimanta.append({"id": 3, "pagini": 5, "utilizator": "Cristi"}) print("Joburi in coada imprimantei:") for i, job in enumerate(imprimanta): print(f" [{i+1}] Job#{job['id']} - {job['pagini']} pagini - {job['utilizator']}") print(" Procesare:") total_pagini = 0 while imprimanta: job = imprimanta.popleft() total_pagini += job["pagini"] print(f" Tiparit Job#{job['id']} ({job['pagini']} pagini) - {job['utilizator']}") print(f" In asteptare: {len(imprimanta)} joburi") print(f" Total pagini tiparite: {total_pagini}")
Output real (python coada_test2.py):
Joburi in coada imprimantei:
[1] Job#1 - 3 pagini - Ana
[2] Job#2 - 1 pagini - Bogdan
[3] Job#3 - 5 pagini - Cristi
Procesare:
Tiparit Job#1 (3 pagini) - Ana
In asteptare: 2 joburi
Tiparit Job#2 (1 pagini) - Bogdan
In asteptare: 1 joburi
Tiparit Job#3 (5 pagini) - Cristi
In asteptare: 0 joburi
Total pagini tiparite: 9Complexitate
Fiecare job procesat exact o data: O(n) timp, O(n) spatiu.
Tiparul general al simularii cu coada: (1) Initializam coada; (2) Cat timp coada nu e vida: extragem, procesam, optional adaugam elemente noi; (3) Colectam rezultatele.
3
3. BFS (Breadth-First Search) — coada la lucru pe grafuri
BFS (parcurgere in latime) viziteaza toate nodurile unui graf nivel cu nivel. Coada garanteaza ca un nod la distanta d este procesat inaintea oricarui nod la distanta d+1.
Analogie: undele de apa
O piatra aruncata intr-un lac produce unde circulare. Toate punctele la raza 1 sunt atinse inainte de cele la raza 2. BFS functioneaza identic: exploreaza valuri concentrice pornind de la nodul sursa.
Graf exemplu: noduri 1–6, muchii: 1–2, 1–3, 2–4, 2–5, 3–6
from collections import deque graf = { 1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: [] } def bfs(start): vizitat = set() coada = deque() ordine = [] coada.append(start) vizitat.add(start) while coada: nod = coada.popleft() ordine.append(nod) print(f" Vizitat: {nod} | Coada: {list(coada)}") for vecin in graf[nod]: if vecin not in vizitat: vizitat.add(vecin) coada.append(vecin) return ordine print("BFS pornind din nodul 1:") rezultat = bfs(1) print(f" Ordine vizitare: {rezultat}")
Output real (python coada_test3.py):
BFS pornind din nodul 1: Vizitat: 1 | Coada: [] Vizitat: 2 | Coada: [3] Vizitat: 3 | Coada: [4, 5] Vizitat: 4 | Coada: [5, 6] Vizitat: 5 | Coada: [6] Vizitat: 6 | Coada: [] Ordine vizitare: [1, 2, 3, 4, 5, 6]
De ce vizitat este un set si nu o lista?
Verificarea vecin not in vizitat trebuie sa fie O(1). Un set ofera acces O(1) in medie. O lista ar face aceasta verificare O(n), incetinind BFS-ul de la O(V+E) la O(V·E).
Complexitate BFS
Timp: O(V + E) — fiecare nod vizitat exact o data, fiecare muchie examinata exact o data. Spatiu: O(V) pentru coada si multimea vizitat.
4
4. Deque: coada cu doua capete si fereastra glisanta
Un deque (double-ended queue, pronuntat “deck”) permite adaugarea si stergerea elementelor la ambele capete in O(1). Util cand avem nevoie de flexibilitate mai mare decat o coada simpla.
from collections import deque d = deque([10, 20, 30]) print("Deque initial:", list(d)) d.appendleft(5) print("Dupa appendleft(5):", list(d)) d.append(40) print("Dupa append(40):", list(d)) stanga = d.popleft() print(f"popleft() = {stanga}, deque ramas: {list(d)}") dreapta = d.pop() print(f"pop() = {dreapta}, deque ramas: {list(d)}") # maxlen: fereastra glisanta de dimensiune fixa fereastra = deque(maxlen=3) for val in [1, 2, 3, 4, 5]: fereastra.append(val) print(f" append({val}) -> {list(fereastra)}")
Output real (python coada_test4.py):
Deque initial: [10, 20, 30] Dupa appendleft(5): [5, 10, 20, 30] Dupa append(40): [5, 10, 20, 30, 40] popleft() = 5, deque ramas: [10, 20, 30, 40] pop() = 40, deque ramas: [10, 20, 30] append(1) -> [1] append(2) -> [1, 2] append(3) -> [1, 2, 3] append(4) -> [2, 3, 4] append(5) -> [3, 4, 5]
Parametrul maxlen creeaza o fereastra glisanta: cand deque-ul este plin, adaugarea unui element nou elimina automat elementul de la celalalt capat. Util pentru: media ultimelor N valori, log-uri de dimensiune fixa.
Atentie
Accesul la mijlocul unui deque (
d[i] pentru i interior) este O(n), nu O(1). Daca aveti nevoie de acces aleator frecvent, folositi o lista. Deque este optim doar pentru operatii la capete.5
5. C++ STL: std::queue — simulare clienti EXCLUSIV INTENSIV
Aceasta sectiune este destinata exclusiv profilului mat-info intensiv. La profilul standard, Python cu collections.deque este suficient.
In C++,
<queue> din STL ofera std::queue<T> pentru cozi FIFO. Operatii: push(x), pop(), front(), back(), empty(), size().Diferenta cruciala fata de Python
In C++,
queue::pop() NU returneaza elementul eliminat. Trebuie sa cititi cu front(), stocati valoarea, apoi apelati pop(). Uitarea acestui detaliu produce bug-uri silentioase.#include <iostream> #include <queue> #include <string> using namespace std; int main() { queue<string> coada; coada.push("Ana"); coada.push("Bogdan"); coada.push("Cristi"); cout << "Coada are " << coada.size() << " clienti." << endl; cout << "Primul la rand: " << coada.front() << endl; cout << "Ultimul la rand: " << coada.back() << endl; cout << " Servire clienti:" << endl; while (!coada.empty()) { cout << " Servit: " << coada.front() << " | Ramas: " << (coada.size() - 1) << endl; coada.pop(); } return 0; }
Output real (g++ -std=c++17 coada_cpp1.cpp -o coada_cpp1.exe && ./coada_cpp1.exe):
Coada are 3 clienti. Primul la rand: Ana Ultimul la rand: Cristi Servire clienti: Servit: Ana | Ramas: 2 Servit: Bogdan | Ramas: 1 Servit: Cristi | Ramas: 0
6
6. BFS si std::deque in C++ EXCLUSIV INTENSIV
BFS in C++ este cerut la concursuri (OJI, ONI, Baraj). Varianta cu matrice de adiacenta este cea mai simpla de implementat in timp limitat.
BFS complet in C++ cu matrice de adiacenta:
#include <iostream> #include <queue> using namespace std; int adj[7][7] = {0}; int main() { adj[1][2]=1; adj[1][3]=1; adj[2][4]=1; adj[2][5]=1; adj[3][6]=1; bool vizitat[7] = {false}; queue<int> coada; coada.push(1); vizitat[1] = true; cout << "BFS din nodul 1:" << endl; while (!coada.empty()) { int nod = coada.front(); coada.pop(); cout << " Vizitat: " << nod << endl; for (int v = 1; v <= 6; v++) { if (adj[nod][v] && !vizitat[v]) { vizitat[v] = true; coada.push(v); } } } return 0; }
Output real (g++ -std=c++17 coada_cpp2.cpp -o coada_cpp2.exe && ./coada_cpp2.exe):
BFS din nodul 1: Vizitat: 1 Vizitat: 2 Vizitat: 3 Vizitat: 4 Vizitat: 5 Vizitat: 6
std::deque — operatii la ambele capete:
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {10, 20, 30}; d.push_front(5); d.push_back(40); cout << "pop_front() = " << d.front() << endl; d.pop_front(); cout << "pop_back() = " << d.back() << endl; d.pop_back(); cout << "Final: "; for (int x : d) cout << x << " "; cout << endl; return 0; }
Output real (g++ -std=c++17 coada_cpp3.cpp -o coada_cpp3.exe && ./coada_cpp3.exe):
pop_front() = 5 pop_back() = 40 Final: 10 20 30
| Operatie | std::queue | std::deque | Complexitate |
|---|---|---|---|
| Adauga la spate | push(x) | push_back(x) | O(1) |
| Adauga la fata | NU exista | push_front(x) | O(1) |
| Scoate din fata | pop() | pop_front() | O(1) |
| Scoate din spate | NU exista | pop_back() | O(1) |
| Peek fata | front() | front() | O(1) |
| Acces index | NU exista | d[i] | O(1) |