Deque şi aplicaţii

(Categoria Structuri de date, Autor Xulescu)

• Conţinut:
• Introducere
• Operaţii

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

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

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.

Operaţii

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

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

Aplicaţii

Unde-i folosit dequeul? :-?

Book Pile (SGU)

(din ciclul cum sa faci un deque folositor) :)
...

Sir

(dequeuri pure)
...

Trans

(gen bun de problema)
...

Otilia (.campion)

(deque la o problema de teoria jocurilor)
...

Cut the Sequence (PKU)

(deque cu arbori de intervale, zice Paul)
...

Bcrc

(deque la programare dinamica)
...