De ce contează?
Gândește-te la o ușă batantă de la intrarea unui restaurant: nu se deschide doar
într-o direcție, ca o ușă obișnuită. Oamenii pot intra și pot ieși pe la oricare
dintre cele două capete, fără să deranjeze pe nimeni din mijloc. Un deque este
exact asta pentru date: o structură în care poți adăuga și scoate elemente la
ambele capete, instant.
Ce este
deque (de la double-ended queue, citește „dec") este o structură liniară care
îți permite să operezi la ambele capete — și la început, și la sfârșit.
O coadă obișnuită (queue) e strictă: intri pe la spate, ieși pe la față. Un
deque ridică această restricție: poți adăuga sau scoate de la oricare capăt, în
plus poți citi orice element din interior prin index, ca la un vector.
Operațiile esențiale, toate O(1):
push_back(x)— adaugăxla coadă (dreapta);push_front(x)— adaugăxla cap (stânga);pop_back()— scoate elementul din coadă;pop_front()— scoate elementul din cap;dq[i]— acces direct la elementul de pe pozițiai, tot în O(1).
Diferența-cheie față de queue: la queue ai acces doar la un capăt pentru
adăugare și la celălalt pentru scoatere. La deque ambele capete acceptă
ambele operații, iar adăugarea la stânga (push_front) costă tot O(1) — nu
trebuie să muți nimic, spre deosebire de un vector. De aici și utilitatea lui în
deque-ul monoton și în fereastra glisantă, unde scoți de la un capăt și adaugi la
celălalt în aceeași trecere.