De ce contează?
Ai în trusă mai multe unelte care seamănă: un ciocan, un ciocan de cauciuc, un ciocan mic de bijutier. Nu sunt interschimbabile — fiecare e cel mai bun pentru o anumită lovitură. La fel sunt stiva, coada și deque-ul: alegi după ordinea în care vrei să intre și să iasă datele.
Întrebarea care decide: în ce ordine ies datele?
Toate structurile liniare din acest capitol stochează elemente. Diferența e din ce capăt scoți. Pune-ți o singură întrebare:
- Scot ultimul intrat? → stivă (LIFO)
- Scot primul intrat? → coadă (FIFO)
- Scot de la oricare capăt? → deque
- Inserez/șterg des la poziții din interior, cunoscute? → listă înlănțuită
- Vreau acces direct la al i-lea element? → vector
Nu memora aplicații pe de rost. Întreabă-te ce ordine de ieșire cere problema, și structura se alege singură. „Inversare”, „undo”, „paranteze” → LIFO. „Pe rând”, „nivel cu nivel” → FIFO.
Tabel de decizie
| Ai nevoie de... | Structura | De ce |
|---|---|---|
| Ultimul intrat iese primul | Stivă | LIFO — un singur capăt |
| Primul intrat iese primul | Coadă | FIFO — BFS, procesare „pe rând” |
| Ambele capete în O(1) | Deque | fereastră glisantă, monotone |
| Inserare/ștergere O(1) la pointer dat | Listă | nu muți restul elementelor |
| Acces la al i-lea în O(1) | Vector | elemente lipite în memorie |
Cum recunoști în enunț
- „verifică parantezele / expresia”, „cel mai apropiat element mai mare”, „simulare cu undo” → stivă.
- „distanța minimă în labirint”, „propagare nivel cu nivel”, „procesează în ordinea sosirii” → coadă (adesea Lee/BFS).
- „maximul/minimul fiecărei ferestre de lungime k” → deque monoton.
- „inserez mereu la capete, lista crește/scade des, nu am nevoie de index” → listă înlănțuită.
Capcana de altitudine: multe probleme se pot rezolva cu mai multe structuri, dar una e clar mai simplă. Dacă te trezești că „forțezi” un vector să facă ce face natural o coadă, oprește-te și schimbă structura.
Greșeli de alegere
Greșeli frecvente de concurs:
- Stivă în loc de coadă la BFS: obții o parcurgere în adâncime și distanțe greșite.
- Vector unde trebuie coadă: scoaterea din față a unui vector e O(n); pe n mare → limită de timp.
- Deque ținând valori, nu indici: pentru ferestre glisante ai nevoie de indici ca să elimini elementele ieșite.
- Listă unde un vector ajunge: dacă faci acces la al i-lea element, lista te costă O(n) degeaba; vectorul e O(1).
Recapitulare
- Întrebarea-cheie: în ce ordine ies datele? Răspunsul îți dă structura.
- LIFO → stivă; FIFO → coadă; ambele capete → deque; index direct → vector.
- Alege structura care face natural ce cere problema, nu cea pe care o forțezi.