De ce contează?
Imaginează-ți trei unelte de bucătărie: un teanc de farfurii, un rând la casă și un sertar deschis pe la ambele capete. De pe teanc iei mereu farfuria de deasupra — ultima pusă. La rând e servit primul cel care a venit primul. Sertarul deschis la ambele capete te lasă să bagi și să scoți și din față, și din spate. Stiva, coada și deque-ul sunt exact aceste trei unelte. Nu sunt rivale: fiecare e perfectă pentru o anumită formă de problemă, iar truc-ul de olimpic nu e să le memorezi, ci să recunoști din enunț pe care o cere problema.
Ideea-cheie
Le-ai învățat deja pe toate trei separat. Această lecție nu adaugă un algoritm nou — îți pune cele trei structuri una lângă alta ca să vezi că, în fond, diferă doar printr-un singur lucru: la ce capete ai voie să lucrezi.
- Stiva lucrează la un singur capăt: adaugi și scoți din același loc (vârful). De aici regula LIFO — Last In, First Out, ultimul intrat, primul ieșit.
- Coada lucrează la două capete opuse: adaugi la spate, scoți din față. De aici FIFO — First In, First Out, primul intrat, primul ieșit.
- Deque-ul (double-ended queue) lucrează la ambele capete liber: adaugi și scoți și în față, și în spate.
Privește lista de mai sus ca pe o ierarhie, nu ca pe trei lucruri fără legătură. Deque-ul le generalizează pe celelalte două: dacă folosești dintr-un deque doar un capăt, ai o stivă; dacă adaugi doar la un capăt și scoți doar de la celălalt, ai o coadă. Stiva și coada sunt deci cazuri particulare ale unui deque, fiecare cu o restricție impusă. Întreaga diferență se reduce la întrebarea: ce capete sunt deschise?