* _push_front()_: inserează un element în faţă;
* _push_back()_:  inserează un element în spate;
* _pop_front()_:  scoate primul element;

* _pop_back()_:   scoate ultimul element.

* _pop_back()_:   scoate ultimul element;
* _empty()_:      întoarce _true_ dacă dequel este gol.

Toate aceste operaţii se execută în timp $O(1)$ 'amortizat':http://en.wikipedia.org/wiki/Amortized_analysis.

Toate aceste operaţii se execută în timp $O(1)$ 'amortizat':http://en.wikipedia.org/wiki/Amortized_analysis. Pentru un plus de viteză va trebui să folosim un vector static cu dimensiunea egală cu numărul maxim de elemente ce pot trece prin deque, iar operaţiile implementate „de mână”, cu doi indecşi ce indică către head şi tail. Însă, în majoritatea aplicaţiilor timpul ne permite să folosim lejeritatea şi siguranţa clasei _std::deque_.

h2(#aplicatii). Aplicaţii

Unde-i folosit dequeul? :-?

Folosiţi deque! Foarte sănătos! :)

h3(#problema-1). Problema 1: 'Book Pile':http://acm.sgu.ru/problem.php?contest=0&problem=271 (SGU)

* $MinY[Q] > X - Q$, pentru $X$;
* $MinY[Q] > X - Q + 1$, pentru $X + 1$.

Este evident că prima relaţie o implică pe cea de-a doua. În momentul acesta se poate construi următorul algoritm: având lista de poziţii care pot fi bune pentru $X$ (sortată descrescător) o căutăm pe cea mai mare ca valoare care este într-adevăr bună. În principiu, scoatem din capul listei poziţiile rele până când dăm de o poziţie bună. La listă se va adăuga şi $X$ şi se trece la pasul următor. Aceste operaţii se pot implementa cu ajutorul unui deque.

Este evident că prima relaţie o implică pe cea de-a doua. În momentul acesta se poate construi următorul algoritm: având lista de poziţii care pot fi bune pentru $X$ (sortată descrescător) o căutăm pe cea mai mare ca valoare care este într-adevăr bună. În principiu, scoatem din capul listei poziţiile rele până când dăm de o poziţie bună. La listă se va adăuga şi $X$ şi se va trece la pasul următor. Operaţiile algoritmului sunt chiar operaţiile asupra unui deque.

h3(#problema-5). Problema 5: 'Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)

h2(#concluzii). Concluzii

Filozofia din spatele structurii de deque devine utilă, de obicei, în momentele finale ale rezolvării unei probleme. După cum s-a văzut în aplicaţiile precedente, acesta ajută la îmbunătăţirea complexităţii şi la eliminarea unor valori de care nu vom mai avea nevoie în viitor. Însă, ce pot spune cu certitudine este că acest deque pe cât este de simplu pe atât este de eficient.

Filozofia din spatele structurii de deque devine utilă, de obicei, în momentele finale ale rezolvării unei probleme. După cum s-a văzut în aplicaţiile precedente, dequeul ajută la îmbunătăţirea complexităţii prin eliminarea unor valori de care nu vom mai avea nevoie în viitor. Însă, ce pot spune cu certitudine este că această structură de date pe cât este de simplă pe atât este de eficientă.

h2(#probleme-suplimentare). Probleme suplimentare