h1. Deque şi aplicaţii

(Categoria _Structuri de date_, Autor _Xulescu_)
 
(toc){width: 20em}*{text-align:center} *Conţinut:*
* 'Introducere':deque-si-aplicatii#introducere
* 'Operaţii':deque-si-aplicatii#operatii
 

Î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ă.

h2. Introducere

h2(#introducere). Introducere

Un _deque_ (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_.

p=. !deque-si-aplicatii?deque1.png!

p=. !deque-si-aplicatii?deque.png 60%!

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

h2. Operaţii

h2(#operatii). Operaţii

Operaţiile ce se pot efectua în C++ asupra unui deque sunt următoarele:

* front():	    întoarce primul element;
* back():	    întoarce ultimul element;
* push_front(): inserează un element în faţă;
* push_back():  inserează un element în spate;
* pop_front():  scoate primul element;
* pop_back():   scoate ultimul element.

 
* _front()_:	    întoarce primul element;
* _back()_:	    întoarce ultimul element;
* _push_front()_: inserează un element în faţă;
* _push_back()_:  inserează un element în spate;
* _pop_front()_:  scoate primul element;
* _pop_back()_:   scoate ultimul element.

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