Deque
În calcul, un deque (de obicei pronunțat ca punte, este o abreviere de coadă cu două capete , adică coadă dublă ) este o structură de date abstractă similară cu o listă, numită și listă legată cap-coadă deoarece elementele pot fi adăugate sau eliminate doar din cap sau din coadă.
Convențiile de denumire
La deque este uneori scris dequeue , dar această practică este în general descurajată în literatura tehnică, deoarece dequeue este, de asemenea, un verb englezesc care înseamnă „a scoate din coadă”. Cu toate acestea, unii autori precum Aho , Hopcroft și Ullman în cartea lor Structuri de date și algoritmi folosesc cuvântul dequeue . În plus, DEQ și DQ sunt de asemenea utilizate pentru a indica un deque.
Distincții și subtipuri
Această structură de date diferă de o coadă FIFO normală în care elementele pot fi adăugate doar pe o parte și eliminate de pe cealaltă. Unele dintre subtipurile posibile ale acestei structuri de date sunt:
- Un deque de intrare restricționat este un deque în care eliminările pot avea loc pe ambele părți, iar inserțiile pot avea loc doar pe o parte.
- Un deque de ieșire restricționat este un deque în care pot apărea inserții pe ambele părți și îndepărtări dintr-o singură.
Ambele structuri de date cele mai comune și fundamentale în calcul, coada și stiva pot fi considerate deque speciale și, prin urmare, sunt implementabile utilizând un deque.
Operațiuni
Una deque acceptă următoarele operațiuni:
| Operațiune | Ada | C ++ | Java | JavaScript | Perl | PHP | Piton | Rubin |
|---|---|---|---|---|---|---|---|---|
| Introduceți articolul ca ultima | Append | push_back | offerLast | push | push | array_push | append | push |
| Introduceți elementul ca mai întâi | Prepend | push_front | offerFirst | unshift | unshift | array_unshift | appendleft | unshift |
| Eliminați ultimul element | Delete_Last | pop_back | pollLast | pop | pop | array_pop | pop | pop |
| Eliminați primul element | Delete_First | pop_front | pollFirst | shift | shift | array_shift | popleft | shift |
| Examinați ultimul articol | Last_Element | back | peekLast | <obj>[<obj>.length - 1] | $_[-1] | end | <obj>[-1] | last |
| Examinați primul articol | First_Element | front | peekFirst | <obj>[0] | $_[0] | reset | <obj>[0] | first |
Implementări
Există cel puțin două moduri de implementare eficientă a unui deque: printr-o matrice dinamică modificată sau printr-o listă dublă legată .
Implementarea matricei dinamice
Deque este adesea implementat folosind o variantă a matricei dinamice care își poate crește capacitatea pe ambele părți și care este, de asemenea, numită matrice deque . Au toate proprietățile matricelor dinamice, cum ar fi timpul de acces constant arbitrar, localitatea bună și inserțiile și îndepărtările ineficiente ale centrului cu adăugarea inserțiilor și îndepărtărilor cu timp constant amortizat pe ambele părți, mai degrabă decât pe o singură parte. Două implementări comune sunt:
- Stocați conținutul deque într-o matrice circulară redimensionându-l numai atunci când este complet plin.
- Stocați conținutul deque începând de la centrul matricei subiacente și redimensionați-l la atingerea oricărui capăt. Această abordare poate necesita o scalare mai frecventă și poate pierde mai mult spațiu, mai ales atunci când elementele sunt adăugate doar dintr-o parte.
Suport lingvistic
Biblioteca de șabloane standard C ++ oferă clasa std :: deque și clasa std :: list pentru implementarea matricelor dinamice și, respectiv, a listei legate.
Java 6 oferă o nouă interfață Deque care permite inserarea și îndepărtarea pe ambele părți. Este implementat de clase precum ArrayDeque (introdus și în Java 6) și LinkedList care oferă implementări de matrice dinamică și respectiv listă legată.
Python 2.4 a introdus modulul de colecții cu suport pentru obiecte deque.
În PHP 5.3, extensia SPL conține clasa „SplDoublyLinkedList” care poate fi utilizată pentru implementarea unui deque.
Complexitate
- Într-o implementare a listei dublu legată, complexitatea fiecărei operațiuni enumerate mai sus este O (1).
- Într-o matrice dinamică, complexitatea în timp a tuturor operațiunilor este O (1)
Bibliografie
- Donald Knuth . The Art of Computer Programming , Volumul 1: Algoritmi fundamentali , ediția a treia. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Secțiunea 2.2.1: Stive, Cozi și Deques, pp. 238–243.
Elemente conexe
linkuri externe
- Documentație SGI STL: deque <T, Alloc> , pe sgi.com . Adus la 30 aprilie 2019 (arhivat din original la 29 decembrie 2017) .
- Project Code: un studiu aprofundat al containerului STL Deque , pe codeproject.com . Adus la 11 martie 2009 (arhivat din original la 30 august 2008) .
- Diagrama unei implementări tipice STL deque , pe pages.cpsc.ucalgary.ca .
- implementarea deque în biblioteca de acțiuni open source flashcript 3 , pe dpdk.nl. Adus la 11 martie 2009 (arhivat din original la 24 iulie 2011) .
