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 coadă cu două capete.

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.

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.

Toate aceste operaţii se execută în timp O(1) amortizat.