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)

Se dau N cărţi aşezate una deasupra celeilalte asupra cărora se vor efecta M operaţii de două tipuri: 1. ADD(nume) : se adaugă cartea nume deasupra celorlalte; 2. ROTATE : primele K cărţi de deasupra se rotesc (dacă sunt mai puţin de K cărţi atunci se vor roti toate). Se cere să se afişeze cărţile în ordine, prima fiind cea de deasupra, după efectuarea celor M operaţii.
Restricţii: 0 ≤ N, K ≤ 40 000, 0 ≤ M ≤ 100 000.

Soluţie:

Va urma...

Sir

(dequeuri pure)
...

Trans (ONI 2004)

(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 (Stelele Informaticii 2006)

(deque la programare dinamica)
...