Deque
![Nessuna nota a piè di pagina](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b7/Question_book_magnify.svg/45px-Question_book_magnify.svg.png)
In informatica, una deque (solitamente pronunciato come deck, è l'abbreviazione di double-ended queue, cioè coda doppia) è una struttura dati astratta simile a una lista, anche chiamata lista concatenata testa-coda in quanto gli elementi possono essere aggiunti o rimossi solamente dalla testa o dalla coda.
Convenzioni sul nome
La deque viene a volte scritta dequeue, ma questa pratica è generalmente scoraggiata nella letteratura tecnica poiché dequeue è anche un verbo inglese che significa "rimuovere da una coda". Nonostante ciò, alcuni autori come Aho, Hopcroft, e Ullman nel loro libro Data Structures and Algorithms, adoperano la parola dequeue. Inoltre, per indicare una deque vengono usati anche DEQ e DQ.
Distinzioni e sotto-tipi
Questa struttura dati differisce da una normale coda FIFO nella quale gli elementi possono essere aggiunti solo da una parte e rimossi dell'altra. Alcuni dei possibili sotto-tipi di questa struttura dati sono:
- Una deque ad input ristretto è una deque nella quale le rimozioni possono avvenire su entrambi i lati, e gli inserimenti da uno solo.
- Una deque ad output ristretto è una deque nella quale gli inserimenti possono avvenire su entrambi i lati, e le rimozioni da uno solo.
Entrambe le strutture dati più comuni e fondamentali dell'informatica, la coda e lo stack possono essere considerate particolari deque, e sono quindi implementabili usando una deque.
Operazioni
Una deque supporta le seguenti operazioni:
Operazione | Ada | C++ | Java | JavaScript | Perl | PHP | Python | Ruby |
---|---|---|---|---|---|---|---|---|
Inserisci elemento come ultimo | Append | push_back | offerLast | push | push | array_push | append | push |
Inserisci elemento come primo | Prepend | push_front | offerFirst | unshift | unshift | array_unshift | appendleft | unshift |
Rimuovi ultimo elemento | Delete_Last | pop_back | pollLast | pop | pop | array_pop | pop | pop |
Rimuovi primo elemento | Delete_First | pop_front | pollFirst | shift | shift | array_shift | popleft | shift |
Esamina ultimo elemento | Last_Element | back | peekLast | <obj>[<obj>.length - 1] | $_[-1] | end | <obj>[-1] | last |
Esamina primo elemento | First_Element | front | peekFirst | <obj>[0] | $_[0] | reset | <obj>[0] | first |
Implementazioni
Esistono almeno due modi di implementare efficientemente una deque: attraverso un array dinamico modificato o tramite una lista doppiamente concatenata.
Implementazione tramite array dinamico
La deque viene spesso implementata usando una variante dell'array dinamico che può accrescere la sua capienza da entrambi i lati e che viene anche chiamato deque array. Essi hanno tutte le proprietà degli array dinamici, come tempo costante di accesso arbitrario, buona località, ed inserimenti e rimozioni al centro inefficienti con l'aggiunta di inserimenti e rimozioni con tempo ammortizzato costante da entrambi i lati, invece che da un lato solo. Due implementazioni comuni sono:
- Memorizzare il contenuto della deque in un array circolare ridimensionandolo solo quando è completamente pieno.
- Memorizzare il contenuto della deque a partire dal centro dell'array sottostante e ridimensionarlo quando una delle due estremità viene raggiunta. Questo approccio può richiedere ridimensionamenti più frequenti e spreca più spazio, in particolare quando gli elementi vengono aggiunti da una parte sola.
Supporto nei linguaggi
La libreria C++ Standard Template Library offre la classe std::deque e la classe std::list per l'implementazione degli array dinamici e della lista concatenata rispettivamente.
Java 6 offre una nuova interfaccia Deque
che permette l'inserimento e la rimozione su entrambi i lati. È implementata da classi come ArrayDeque
(anch'essa introdotta in Java 6) e LinkedList
che forniscono le implementazioni dell'array dinamico e della lista concatenata rispettivamente.
Python 2.4 ha introdotto il modulo collections col supporto per gli oggetti deque.
In PHP 5.3, l'estensione SPL contiene la classe 'SplDoublyLinkedList' che può essere usata per l'implementazione di una deque.
Complessità
- In un'implementazione con lista doppiamente concatenata, la complessità di ogni operazione elencata sopra è O(1).
- In un array dinamico, la complessità temporale di tutte le operazioni è O(1)
Bibliografia
- Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
Voci correlate
- Array
- Lista concatenata
- Coda (informatica)
- Pila (informatica)
Collegamenti esterni
- (EN) Denis Howe, double-ended queue, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
- SGI STL Documentation: deque<T, Alloc>, su sgi.com. URL consultato il 30 aprile 2019 (archiviato dall'url originale il 29 dicembre 2017).
- Code Project: An In-Depth Study of the STL Deque Container, su codeproject.com. URL consultato l'11 marzo 2009 (archiviato dall'url originale il 30 agosto 2008).
- Diagram of a typical STL deque implementation, su pages.cpsc.ucalgary.ca.
- deque implementation in flash actionscript 3 open source library, su dpdk.nl. URL consultato l'11 marzo 2009 (archiviato dall'url originale il 24 luglio 2011).
V · D · M | |
---|---|
Tipi | Collezione · Container |
Astratte | Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset) |
Array | Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso |
Collegate | Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR |
Alberi | B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario |
Grafi | Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico |
Alberi di partizionamento dei dati spaziali | Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree |
Lista di strutture dati |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)