* 'Probleme suplimentare':deque-si-aplicatii#probleme-suplimentare
* 'Bibliografie':deque-si-aplicatii#bibliografie

În acest articol voi prezenta o structură de date de tip listă numită deque şi o serie de aplicaţii utile care vă vor demonstra simplitatea şi utilitatea folosirii acesteia, în special în concursurile de informatică.

În acest articol voi prezenta o structură de date de tip listă numită _deque_. Simplitatea acestei structuri poate induce în eroare şi din acest motiv am prezentat şi o serie de aplicaţii care vor arăta neaşteptata sa utilitate şi apariţie în locurile unde am fi crezut că nu se mai poate face nimic pentru a reduce complexitatea.

h2(#introducere). Introducere
_Dequeul_ (pronunţat de obicei _deck_) poate fi privit ca o colecţie de tip listă ce are două capete prin care se şterg sau inserează noi elemente. În literatura de specialitate, aceste capete se numesc _head_ şi _tail_, iar dequeul mai este recunoscut şi ca fiind o coadă cu două capete _(double ended queue)_.

p=. !deque-si-aplicatii?deque0.png 70%!
 

Un deque poate fi implementat folosind liste dublu înlănţuite, sau cu un vector static când se cunoaşte numărul elementelor din colecţie. Ce trebuie reţinut este că limbajul C++ pune la dispoziţia utilizatorilor prin intermediul headerului _#include <deque>_ clasa _std::deque_.
h2(#operatii). Operaţii

Mai jos sunt operaţii ce se pot efectua cu un deque, iar în stânga corespondentul lor în limbajul C++:

Mai jos sunt operaţiile care pot fi efectuate asupra unui deque, iar în stânga corespondentul lor în limbajul C++:

* _front()_:	    întoarce primul element;
* _back()_:	    întoarce 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. 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_.

p=. !deque-si-aplicatii?new_deque.png 75%!
 
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 limita de timp permite folosirea lejerităţii şi siguranţei clasei _std::deque_.

h2(#aplicatii). Aplicaţii