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.
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 Alfred Aho, John Hopcroft, e Jeffrey Ullman nel loro libro Data Structures and Algorithms, adoperano la parola dequeue. Inoltre, per indicare una deque vengono usati anche DEQ e DQ.
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:
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.
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 |
Esistono almeno due modi di implementare efficientemente una deque: attraverso un array dinamico modificato o tramite una lista doppiamente concatenata.
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à, e 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:
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.
Wikimedia Commons contiene immagini o altri file su Deque
