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

p=. !deque-si-aplicatii?deque0.png 70%!

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

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

La final, când se vor termina operaţiile, cărţilor de pe raft li se vor adăuga cele din deque şi se va afişa soluţia. În cazul presupus, soluţia va fi: $E B A D C$.

Pentru a înţelege cum se folosesc funcţiile membru ale clasei std::deque, am adăugat o parte din cod:
 
== code(cpp) |
    deque <string> deq;        // dequeul
    vector <string> res;       // rezultatul
 
    int rotated = 0;           // iniţial, secvenţa nu este rotită
 
    for (int i = 0; i < M; ++ i) {
        if (deq.size() > K) {
            if (rotated == false) {
                for (; deq.size() > K; deq.pop_back())
                    res.push_back( deq.back() );
            }
            else {
                for (; deq.size() > K; deq.pop_front())
                    res.push_back( deq.front() );
            }
        }
 
        if (s-a citit "ROTATE")
            rotated = !rotated;
        else           // name conţine numele cărţii ce se va adăuga
            rotated == false ? deq.push_front( name ) : deq.push_back( name );
    }
 
    if (rotated == false) {
        for (; deq.size() > 0; deq.pop_back())
            res.push_back( deq.back() );
    }
    else {
        for (; deq.size() > 0; deq.pop_front())
            res.push_back( deq.front() );
    }
==
 

Întrucât operaţiile unui deque se execută în $O(1)$ amortizat, soluţia are complexitatea $O(N + M)$.
h3. 'Sir':problema/sir