De ce contează?
Imaginează-ți o coadă la patiserie cu două ferestre, una la fiecare capăt: poți intra pe la stânga, poți intra pe la dreapta, și poți pleca tot pe la oricare din ele. Nu mai ești obligat, ca la o coadă obișnuită, să intri în spate și să ieși în față. Această „coadă cu două capete" se numește deque (double-ended queue) și exact libertatea ei la ambele capete o face unealta perfectă pentru o problemă clasică de concurs: maximul pe fereastră glisantă.
Intuiția
Un deque e o coadă la care ambele capete sunt deschise: adaugi sau scoți la fel
de ieftin în față ca în spate. Gândește-te la o foaie de hârtie pe care poți
scrie un nume fie sus, fie jos, și poți șterge tot fie de sus, fie de jos —
nimic din mijloc nu se mișcă. Toate cele patru operații (push_front,
push_back, pop_front, pop_back) costă O(1).