* '_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_. Simplitatea acestei structuri poate nu are multe de spus ş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.

În acest articol voi prezenta o structură de date de tip listă numită _deque_. Simplitatea acestei structuri poate că nu are multe de spus iar din acest motiv am prezentat şi o serie de aplicaţii care vor arăta surprinzătoarea sa utilitate î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)_.

Structura de _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_, iar dequeul mai este recunoscut şi ca fiind o coadă cu două capete _(double ended queue)_.

Un deque poate fi implementat folosind liste dublu înlănţuite ori 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>_ containerul '_std::deque_':http://www.cplusplus.com/reference/stl/deque/.

Implementarea unui deque se poate face cu liste dublu înlănţuite ori 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>_ containerul '_std::deque_':http://www.cplusplus.com/reference/stl/deque/.

h3(#operatii). Operaţii:

* _push_back()_:  inserează un element în spate;
* _pop_front()_:  scoate primul element;
* _pop_back()_:   scoate ultimul element;

* _empty()_:      întoarce _true_ dacă dequel este gol.

* _empty()_:      întoarce _true_ dacă în deque nu se găseşte niciun element şi _false_ în caz contrar.

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_.

În multe aplicaţii unde soluţiile parţiale se reprezintă sub forma unui şir continuu de valori care permite inserarea şi ştergerea doar pe la capete (în general inserări pe la un capăt şi ştergeri pe la celălalt) se poate folosi un deque. Să urmărim în continuare cazuri concrete în care simplitatea unui deque duce la soluţii de multe ori optime şi implementări foarte scurte şi clare.

În multe aplicaţii unde soluţiile parţiale se reprezintă sub forma unui şir continuu de valori care permite inserarea şi ştergerea doar pe la capete se poate folosi un deque. În general, se fac inserări pe la un capăt şi ştergeri pe la celălalt. Să urmărim în continuare cazuri concrete în care simplitatea unui deque duce la soluţii de multe ori optime şi implementări foarte scurte şi clare.

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