* 'Probleme suplimentare':deque-si-aplicatii#probleme-suplimentare
* 'Bibliografie':deque-si-aplicatii#bibliografie

În acest articol voi prezenta o structură de date de tip coadă numită _deque_. Aceasta nu este una complexă, în schimb se va dovedi foarte folositoare. După o scurtă prezentare, mă voi axa pe 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 algoritmului.

În acest articol voi prezenta o structură de date liniară de tip listă numită _deque_. Aceasta nu este una complexă, în schimb se va dovedi foarte folositoare. După o scurtă prezentare, mă voi axa pe 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 algoritmului.

h2(#descriere). Descrierea structurii

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

Structura de _deque_ (pronunţat, de obicei, _deck_) poate fi privită ca o listă cu două capete prin intermediul cărora se şterg sau inserează noi elemente. În literatura de specialitate aceste capete se numesc _head_ şi _tail_, iar deque-ul mai este recunoscut şi ca fiind o coadă cu două capete _(double ended queue)_.

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

Pentru implementarea unui deque putem recurge la liste dublu înlănţuite sau la un vector static când se cunoaşte numărul elementelor din colecţie. Limbajul C++ pune şi el la dispoziţia programatorilor o implementare prin intermediul containerului '_std::deque_':http://www.cplusplus.com/reference/stl/deque/ din headerul _<deque>_.

h3(#operatii). Operaţii:

Mai jos sunt enumerate operaţiile care pot fi efectuate asupra unui deque împreună cu corespondentul lor în limbajul C++:

Vom putea utiliza această structură de date în situaţiile când avem nevoie de următoarele operaţii (sunt listate cu numele sub care se găsesc în limbajul C++):

* _front()_:	    întoarce primul element;
* _back()_:	    întoarce ultimul element;

* _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;

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

Toate aceste operaţii se execută în timp $O(1)$ pe o structură implementată de la zero sau în timp $O(1)$ 'amortizat':http://en.wikipedia.org/wiki/Amortized_analysis pentru containerul $deque$ din C++.

Î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. Aplicaţiile sunt prezentate în ordinea crescătoare a dificultăţii şi din acest motiv recomand cu căldură tuturor celor care au de învăţat din acest articol să le parcurgă în ordine.

Î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$. 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. Aplicaţiile sunt prezentate în ordinea crescătoare a dificultăţii şi din acest motiv le recomand cu căldură tuturor celor care învaţă din acest articol să le parcurgă în ordine.

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

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

bq. 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; prin rotaţie vom considera elementele în ordine inversă: ultimul va fi primul, penultimul va fi al doilea etc). 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$.

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

h2(#problema-2). '2. Vila 2':problema/vila2 (.campion, 2005)

h2(#problema-2). 2. 'Vila 2':problema/vila2 (.campion, 2005)

bq. Se dă un şir $S$ de $N$ numere întregi şi un $D$ număr natural. Se cere să determine diferenţa maximă dintre oricare două numere din şir cu proprietatea că diferenţa în modul a poziţiilor pe care se găsesc în şirul $S$ nu depăşeşte $D$.
Restricţii: $2 ≤ N ≤ 100 000$, $1 ≤ D ≤ N/2$.

Cum fiecare indice din $1$, $2$, .., $N$ trece cel mult o dată prin deque, complexitatea finală este $O(N)$ amortizat.

h2(#problema-3). '3. Şir':problema/sir

h2(#problema-3). 3. 'Şir':problema/sir

bq. Se dă un şir $S$ de numere întregi de lungime $N$. Se cere să se găsească secvenţa de lungime maximă cuprinsă între $X$ şi $Y$ astfel încât $MAX - MIN ≤ Z$, unde $MAX$ este maximul dintre toate numerele întregi din secvenţă iar $MIN$ minimul dintre acestea. Secvenţa soluţie va fi cea cu poziţia de început maximă dintre toate secvenţele de lungime maximă.
Restricţii: $3 ≤ N ≤ 100 000$, $1 ≤ X ≤ Y ≤ N$, $0 ≤ Z ≤ 30 000$.

Complexitatea finală va fi $O(N)$.

h2(#problema-4). '4. Platforma':http://campion.edu.ro/problems/3/509/platforma_ro.htm (.campion, 2009)

h2(#problema-4). 4. 'Platforma':http://campion.edu.ro/problems/3/509/platforma_ro.htm (.campion, 2009)

bq. Se dă o matrice $P$ de dimensiuni $M x N$ cu elemente numere întregi. Se defineşte valoarea maximă dintr-un dreptunghi de dimensiuni $R x C$ ca fiind valoarea maximă dintre elementele aflate în acel dreptunghi.
Cerinţă: Să se găsească un dreptunghi de dimensiuni $R x C$ cu valoarea maximă minimă.

Rezultă complexitatea finală $O(M * N)$.

h2(#problema-5). '5. Trans':problema/trans (ONI 2004)

h2(#problema-5). 5. 'Trans':problema/trans (ONI 2004)

bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$,.., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 ≤ i ≤ Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 ≤ i ≤ N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea $C{~i~}$.
Cerinţă: Pentru fiecare dintre cele $Q$ tipuri de camioane, determinaţi suma minimă plătită pentru a transporta toate cele $N$ blocuri.

}
==

h2(#problema-6). '6. Otilia':problema/otilia  (.campion, 2005)

h2(#problema-6). 6. 'Otilia':problema/otilia  (.campion, 2005)

bq. Otilia şi Burbucel au o grămadă de $N$ pietre şi vor juca un joc cu următoarele trei reguli: 1. Primul jucător are voie să ia din gramadă cel mult $K$ piese; 2. Cu excepţia primei mutări, fiecare jucător are voie să ia maxim $P * t$ pietre, unde $t$ este numărul de pietre care au fost substituite din grămadă la mutarea precedentă; 3. Pierde cel care mută ultimul (cel care ia ultimele pietre din grămadă).
Cerinţă: Se dau $M$ jocuri prin numerele $N$, $K$ şi $P$. Se cere să se determină dacă Otilia va câştiga fiecare din jocuri sau nu.

Este evident că prima relaţie o implică pe cea de-a doua. În momentul acesta se poate construi următorul algoritm: având lista de poziţii care pot fi bune pentru $X$ (sortată descrescător) o căutăm pe cea mai mare ca valoare care este într-adevăr bună. În principiu, scoatem din capul listei poziţiile rele până când dăm de o poziţie bună. La listă se va adăuga şi $X$ şi se va trece la pasul următor. Operaţiile algoritmului sunt chiar operaţiile asupra unui deque.

h2(#problema-7). '7. Bcrc':problema/bcrc (Stelele Informaticii, 2006)

h2(#problema-7). 7. 'Bcrc':problema/bcrc (Stelele Informaticii, 2006)

bq. Se consideră $N$ camere, numerotate de la $1$ la $N$, aşezate în cerc. Iniţial (la momentul de timp 0), ne aflăm în camera $1$. În fiecare moment de timp, putem alege să rămânem în camera în care ne aflăm sau să ne deplasăm într-o cameră vecină într-o unitate de timp. Se dă o listă de $M$ cutii ce conţin bomboane prin $T$, $C$ şi $B$: cutia apare la momentul $T$ în camera $C$ şi conţine $B$ bomboane. Cutia va dispărea la momentul $T + 1$.
Cerinţă: Cunoscând numărul de camere din labirint şi momentele de timp la care apar cutiile cu bomboane, determinaţi care este numărul maxim de bomboane pe care le putem culege.

Complexitatea finală: <tex> O(M * N) </tex>.

h2(#problema-8). '8. Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)

h2(#problema-8). 8. 'Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)

bq. Se dă o secvenţă $S$ de numere întregi de lungime $N$. Va trebui să se împartă secvenţa în mai multe subsecvenţe astfel încât suma valorilor din fiecare parte să nu depăşească un număr întreg $M$ dat, iar dacă însumăm maximul din fiecare subsecvenţă să obţinem o sumă cât mai mică.
Restricţii: $0 < N ≤ 100 000$, $0 ≤ S{~i~} ≤ 1 000 000$.