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

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

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

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

h3. Soluţie:

Soluţia problemei se poate deduce urmând paşii următori. Să presupunem că avem cărţile $A B C$ iniţial şi $K = 3$. Dacă îl vom adăuga pe $D$, atunci nu vor rămâne importante decât cărţile $D A B$, deoarece, dacă vom roti ulterior ultimele $K$ cărţi, $C$ nu va mai fi niciodată considerat, cărţile fiind doar adăugate, iar o dată ce o carte iese din „top {$K$}” cărţi nu va mai fi posibil să i se schimbe poziţia pe raft. Să rotim acum „top {$K$}” cărţi. Noua ordine va fi $B A D$ şi $C$ pe raft la loc sigur. Dacă îl vom adăuga pe $E$, topul se va schimba în $E B A$ iar pe raft, în mod sigur vor fi, în această ordine, $D C$. Proprietatea celor $K$ cărţi din vârf este: o secvenţă continuă de elemente, la care se adaugă noi elemente sau se elimină dintre acestea numai pe la _capete_. Aceste capete sunt chiar head şi tail ale unui deque.

Soluţia problemei se poate deduce urmând paşii următori. Să presupunem că iniţial avem cărţile $A B C$ şi $K = 3$. Dacă îl vom adăuga pe $D$, atunci nu vor rămâne importante decât cărţile $D A B$, deoarece, dacă vom roti ulterior ultimele $K$ cărţi, $C$ nu va mai fi niciodată considerat, cărţile fiind doar adăugate, iar o dată ce o carte iese din „top {$K$}” cărţi nu va mai fi posibil să i se schimbe poziţia pe raft. Să rotim acum „top {$K$}” cărţi. Noua ordine va fi $B A D$ şi $C$ pe raft la loc sigur. Dacă îl vom adăuga pe $E$, topul se va schimba în $E B A$ iar pe raft, în mod sigur vor fi, în această ordine, $D C$. Proprietatea celor $K$ cărţi din vârf este: o secvenţă continuă de elemente, la care se adaugă noi elemente sau se elimină dintre acestea numai pe la _capete_. Aceste capete sunt chiar head şi tail ale unui deque.

p=. !deque-si-aplicatii?bookpile.png 40%!

h3. Soluţie:

Soluţia nu este greu de intuit. Considerăm indicii succesiv $1$, $2$, .. , $N$. Va trebuie ca pentru fiecare secvenţă $(i - D, i]$ să determinăm valoarea maximă şi pe cea minimă, iar diferenţa lor să o comparăm cu rezultatul obţinut până în acel moment. Pentru fixarea ideilor, să urmărim cum putem determina valoarea maximă din fiecare secvenţă $(i - D, i]$.

Soluţia nu este greu de intuit. Dacă vom considera indicii $1$, $2$, .. , $N$ succesiv va trebuie ca pentru fiecare secvenţă $(i - D, i]$ să determinăm valoarea maximă şi pe cea minimă, iar diferenţa lor să o comparăm cu rezultatul obţinut până în acel moment. Pentru fixarea ideilor, să urmărim cum putem determina valoarea maximă din fiecare secvenţă $(i - D, i]$.

_Observaţie_: „Fie $i{~1~}$, $i{~2~}$ doi indici astfel încât $i - D < i{~1~} < i{~2~} ≤ i$.

# Dacă $S[i{~1~}] < S[i{~2~}]$ atunci, cât timp cei doi indici vor fi în intervalul $(i - D, i]$, valoarea de pe poziţia $i{~2~}$ va fi întotdeauna preferată valorii de pe poziţiei $i{~1~}$. Când unul din indici nu va mai fi în acest interval, cel expediat va fi $i{~1~}$ şi, astfel, $i{~2~}$ rămâne în continuare preferat.

# Dacă $S[i{~1~}] < S[i{~2~}]$ atunci, cât timp cei doi indici vor fi în intervalul $(i - D, i]$, valoarea de pe poziţia $i{~2~}$ va fi întotdeauna preferată valorii de pe poziţia $i{~1~}$. Când unul din indici nu va mai fi în acest interval, cel expediat va fi $i{~1~}$ şi, astfel, $i{~2~}$ rămâne în continuare preferat.

# Dacă $S[i{~1~}] > S[i{~2~}]$ atunci îl vom păstra pe $i{~2~}$, deoarece este candidat la maxim în viitor.”
Cu această observaţie deducem că într-o secvenţă $(i - D, i]$ vom avea un şir $i{~1~} < i{~2~} < ... < i{~K~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > ... > S[i{~K~}]$. Când vom avansa la secvenţa următoare, $(i - D + 1, i + 1]$, vom şterge din indicii $i{~1~}$, $i{~2~}$... atâta timp cât nu se găsesc în intervalul curent şi vom şterge din poziţiile $i{~K~}$, $i{~K-1~}$... cât timp $S[i + 1] > S[i{~K~}]$, $S[i + 1] > S[i{~K-1~}]$... adică cât timp se îndeplineşte primul punct din observaţia anterioară.

Prima rezolvare se găseşte uşor, deoarece nu facem decât să urmărim textul: pentru fiecare poziţie $i$ fixată ({$i$} ia valorile $1$, $2$, .., $N$ succesiv) vom determina pentru aceasta secvenţa cerută, adică vom plimba un $j$ între poziţiile $i - Y$ şi $i - X$. Pentru un interval $(j, i]$ vom determina $MAX$ şi $MIN$ în $O(log{~2~}N)$ cu un arbore de intervale, iar daca diferenţa dintre acestea nu depăşeşte $Z$ vom compara cu soluţia finală. Complexitatea finală va fi $O(N * (Y - X) * log{~2~}Y)$.

Să presupunem că pentru poziţia curentă $i$, l-am găsit pe $j$ cuprins între $i - Y$ şi $i - X$ care îndeplineşte optimul. Ce proprietăţi are $j$?

Să presupunem că pentru poziţia curentă $i$, l-am găsit pe $j$ cât mai mic cuprins între $i - Y$ şi $i - X$ astfel încât secvenţa $(j, i]$ este candidată la soluţie. Ce proprietăţi are $j$?

* $i - Y ≤ j ≤ i - X$ şi $MAX - MIN ≤ Z$;
* dacă îl incrementăm pe $j$ la $j + 1$ atunci dacă $j ≤ i - X$ cu siguranţă $MAX - MIN ≤ Z$ şi astfel soluţia va fi mai scurtă;

Cu cei doi indici $i$ şi $j$ vom accesa fiecare element din cele $N$ de cel mult $2$ ori, o dată cu $i$ şi o dată cu $j$. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}Y)$ pentru determinarea maximului şi minimului.

Pentru fixarea ideilor să urmărim cum îl calculăm pe $MAX$. Observaţia care ne ajută în multe probleme pentru reducerea complexităţii de la $O(log{~2~}N)$ la $O(1)$ amortizat este următoarea:

Pentru fixarea ideilor să urmărim cum îl vom calcula pe $MAX$. Observaţia care ne ajută în multe probleme pentru reducerea complexităţii de la $O(log{~2~}N)$ la $O(1)$ amortizat este următoarea:

_Observaţie_: „Fixăm $i{~1~}$ şi $i{~2~}$ astfel încât $j < i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~2~}] > S[i{~1~}]$ poziţia $i{~2~}$ va fi întotdeauna mai importantă decât poziţia $i{~1~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ şi $i{~2~}$ nu vor mai fi ambele în intervalul $(j, i]$, poziţia eliminată va fi {$i{~1~}$}. Dacă însă $S[i{~1~}] > S[i{~2~}]$, atunci poziţia $i{~1~}$ va umbri poziţia $i{~2~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ va fi eliminat, atunci e posibil ca $i{~2~}$ să fie un candidat la $MAX$ dintre restul elementelor de la dreapta sa. În acest caz, nu putem afirma nimic şi vom păstra cele două poziţii.”

* <tex> bst_{i,c} = Min\ \{\ Minim(bst_{j,0},\ bst_{j,1}) - sum_{j,c}\ :\ i - K \le j \le i - 1\ \} + sum_{i,c} + T; </tex>

Notez în continuare, pentru uşurinţă în scriere, <tex> T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} </tex>. Să fixăm doi indici <tex> i_{1} </tex> şi <tex> i_{2} </tex>, astfel încât <tex> i - K \le i_{1} < i_{2} \le i - 1 </tex>. Dacă <tex> T_{i_{1},c} > T_{i_{2},c} </tex> atunci, întotdeauna poziţia <tex> i_{2} </tex> va fi preferată poziţiei <tex> i_{1} </tex>. Când cele două nu se vor mai afla ambele în intervalul <tex> [i - K, i - 1] </tex>, poziţia eliminată va fi poziţia <tex> i_{1} </tex>. Dacă <tex> T_{i_{1},c} < T_{i_{2},c} </tex>, atunci nu putem decide care poziţie este mai bună în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe că în intervalul <tex> [i - K, i - 1] </tex> vom avea o serie de indecşi candidaţi la minim <tex> i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 </tex> astfel încât <tex> T_{i_{1},c} < T_{i_{2},c} <  .. < T_{i_{n},c} </tex>. Mai departe, găsim <tex> bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T </tex>. Urmează să îl introducem şi pe <tex> T_{i,c} </tex>, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>, în şirul de indecşi de mai sus. Acest lucru se va face în felul următor: se vor elimina din <tex> i_{n}, , i_{n-1}, \ldots </tex> atâta timp cât <tex> T_{i_{n},c} > T_{i,c} </tex>, <tex> T_{i_{n-1},c} > T_{i,c} \ldots </tex> adică atâta timp cât poziţia <tex> i </tex> este preferată lui <tex> i_{n}, i_{n-1}, \ldots </tex>. Fiind la poziţia <tex> i + 1 </tex>, intervalul se va transforma în <tex> [i - K + 1, i] </tex>, aşadar, vom mai elimina din primii indici <tex> i_{1}, i_{2}, \ldots </tex> atâta timp cât <tex> i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots </tex>.

Notez în continuare, pentru uşurinţă în scriere, <tex> T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} </tex>. Să fixăm doi indici <tex> i_{1} </tex> şi <tex> i_{2} </tex>, astfel încât <tex> i - K \le i_{1} < i_{2} \le i - 1 </tex>. Dacă <tex> T_{i_{1},c} > T_{i_{2},c} </tex> atunci întotdeauna poziţia <tex> i_{2} </tex> va fi preferată poziţiei <tex> i_{1} </tex>. Când cele două nu se vor mai afla ambele în intervalul <tex> [i - K, i - 1] </tex>, poziţia eliminată va fi poziţia <tex> i_{1} </tex>. Dacă <tex> T_{i_{1},c} < T_{i_{2},c} </tex>, atunci nu putem decide care poziţie este mai bună în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe că în intervalul <tex> [i - K, i - 1] </tex> vom avea o serie de indecşi candidaţi la minim <tex> i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 </tex> astfel încât <tex> T_{i_{1},c} < T_{i_{2},c} <  .. < T_{i_{n},c} </tex>. Mai departe, găsim <tex> bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T </tex>. Urmează să îl introducem şi pe <tex> T_{i,c} </tex> în şirul de indecşi de mai sus, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>. Acest lucru se va face în felul următor: se vor elimina din <tex> i_{n}, , i_{n-1}, \ldots </tex> atâta timp cât <tex> T_{i_{n},c} > T_{i,c} </tex>, <tex> T_{i_{n-1},c} > T_{i,c} \ldots </tex> adică atâta timp cât poziţia <tex> i </tex> este preferată lui <tex> i_{n}, i_{n-1}, \ldots </tex>. Fiind la poziţia <tex> i + 1 </tex>, intervalul se va transforma în <tex> [i - K + 1, i] </tex>, aşadar, vom mai elimina din primii indici <tex> i_{1}, i_{2}, \ldots </tex> atâta timp cât <tex> i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots </tex>.

După cum am arătat şi la problema precedentă, acest şir de indecşi <tex> i_{1}, i_{2}, \ldots, i_{n} </tex> are proprietatea că este un şir continuu de numere care admite inserări prin dreapta (tail) şi ştergeri prin stânga (head). Şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va trece o singură dată prin deque şi va fi şters cel mult o dată, complexitatea soluţiei în acest caz va fi <tex> O(Q * N) </tex>.

După cum am arătat şi la problema precedentă, acest şir de indecşi <tex> i_{1}, i_{2}, \ldots, i_{n} </tex> are proprietatea că este un şir continuu de numere care admite inserări prin dreapta (tail) şi ştergeri prin stânga (head). Şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va trece o singură dată prin deque, complexitatea soluţiei va fi <tex> O(N) </tex> pentru fiecare camion, deci <tex> O(Q * N) </tex> în total.

În practică, programul este scurt, clar şi foarte eficient:

În practică, programul este scurt, clar şi eficient:

== code(cpp) |
#include <iostream>

Soluţia foloseşte metoda programării dinamice.

O stare se reprezintă prin camera în care ne aflăm şi momentul de timp. Fie <tex> bst_{i,j} </tex> numărul maxim de bomboane culese până în momentul <tex> i </tex> când ne găsim în camera <tex> j </tex>. O observaţie evidentă este că <tex> bst_{i,j} </tex> se poate modifica doar în momentele în care apar cutiile. Prin urmare, vom considera momentele de timp când apar cutiile, momente ce sunt în număr de <tex> M </tex>, <tex> bst_{i,j} </tex> însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera <tex> j </tex> unde am cules cutia <tex> i </tex>. De cine depinde această stare? Ştim că <tex> bst_{i-1,1\ldotsN} </tex> a fost deja calculat în mod optim. Să notăm cu <tex> T </tex> diferenţa de timp dintre momentele la care apare cutia <tex> i </tex> şi cutia <tex> i - 1 </tex>. În acest moment, <tex> i </tex> şi cameră <tex> j </tex> putem ajunge din maxim <tex> T </tex> camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:

O stare se reprezintă prin camera în care ne aflăm şi momentul de timp. Fie <tex> bst_{i,j} </tex> numărul maxim de bomboane culese până în momentul <tex> i </tex> când ne găsim în camera <tex> j </tex>. O observaţie evidentă este că <tex> bst_{i,j} </tex> se poate modifica doar în momentele în care apar cutiile. Prin urmare, vom considera momentele de timp când apar cutiile, momente ce sunt în număr de <tex> M </tex>, <tex> bst_{i,j} </tex> însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera <tex> j </tex> unde am cules cutia <tex> i </tex>. De cine depinde această stare? Ştim că <tex> bst_{i-1,1 \ldots N} </tex> a fost deja calculat în mod optim. Să notăm cu <tex> T </tex> diferenţa de timp dintre momentele la care apare cutia <tex> i </tex> şi cutia <tex> i - 1 </tex>. În această stare, <tex> i </tex> şi cameră <tex> j </tex>, putem ajunge din maxim <tex> T </tex> camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:

* <tex> bst_{i,j} = Min\{\ bst_{i-1,j-T},\ bst_{i-1,j-T+1}, \ldots,\ bst_{i-1,j}, \ldots,\ bst_{i-1,j+T-1},\ bst_{i-1,j+T}\ \}; </tex>

Metoda directă şi, aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul se deplasează constant spre dreapta, dacă vom considera indicii <tex> j </tex> în ordine <tex> 1, 2, 3, \ldots </tex>, fiind reprezentat de un şir de valori de lungime constantă în care noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Vom folosi un deque de lungime <tex> T * 2 </tex> şi vom proceda ca în problemele precedente, eliminând poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a acestei explicaţii.

Metoda directă, şi aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul <tex> [j-T,j+T] </tex> se deplasează constant spre dreapta, dacă vom considera indicii <tex> j </tex> în ordine <tex> 1, 2, 3, \ldots </tex>. În acest interval noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Însă, cum am arătat în problemele precedente, nu avem nevoie de toate valorile din acest interval. Şi din acest motiv vom folosi un deque de lungime <tex> T * 2 + 1 </tex> cu care vom elimina poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a acestei explicaţii.

p=. !deque-si-aplicatii?bcrc.png 40%!

h3. Soluţie:

Şi această soluţie foloseşte metoda programării dinamice. Construim <tex> bst_{i} </tex> egal cu costul minim de a împărţi primele <tex> i </tex> numere din <tex> S </tex>. Pentru a calcula <tex> bst_{i} </tex> alegem toate secvenţele posibile care se termină pe o poziţia <tex> j </tex>, <tex> j < i </tex>, şi adunăm valorile corespunzătoare:

Şi această soluţie foloseşte metoda programării dinamice. Construim <tex> bst_{i} </tex> egal cu costul minim de a împărţi primele <tex> i </tex> numere din <tex> S </tex>. Pentru a calcula <tex> bst_{i} </tex> alegem toate secvenţele posibile care încep la o poziţie <tex> j+1 </tex>, <tex> j < i </tex>, şi adunăm valorile corespunzătoare:

* <tex> bst_{i} = Min\{bst_{j} + Max\{S_{j+1},.., S_{i}\}\ :\ 0 \le j < i, \displaystyle\sum_{k=j+1}^{i} S_{k} \le M\}; </tex>

h2(#concluzii). Concluzii

Filozofia din spatele structurii de deque devine utilă, de obicei, în părţile finale ale rezolvării unei probleme. Însă, ce pot spune cu certitudine este că această structură de date pe cât este de simplă pe atât este de eficientă.

Filozofia din spatele structurii de deque devine utilă, de obicei, în părţile finale ale rezolvării unei probleme. Însă, ce pot spune cu certitudine este că această structură de date pe cât este de simplă pe atât este de eficientă şi necesară.

h2(#probleme-suplimentare). Probleme suplimentare