Questa voce o sezione sull'argomento informatica è priva o carente dinote eriferimenti bibliografici puntuali.

---

Sebbene vi siano unabibliografia e/o deicollegamenti esterni, manca la contestualizzazione delle fonti connote a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoimigliorare questa vocecitando le fonti più precisamente. Segui i suggerimenti delprogetto di riferimento.

In informatica, unadeque (solitamente pronunciato comedeck, è l'abbreviazione didouble-ended queue, cioècoda doppia) è unastruttura dati astratta simile a una lista, anche chiamatalista concatenata testa-coda in quanto gli elementi possono essere aggiunti o rimossi solamente dalla testa o dalla coda.

Ladeque viene a volte scrittadequeue, ma questa pratica è generalmente scoraggiata nella letteratura tecnica poichédequeue è anche un verbo inglese che significa "rimuovere da una coda". Nonostante ciò, alcuni autori comeAlfred Aho,John Hopcroft, eJeffrey Ullman nel loro libroData Structures and Algorithms, adoperano la paroladequeue.Inoltre, per indicare unadeque vengono usati anche DEQ e DQ.

Questa struttura dati differisce da una normale codaFIFO 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:

• Unadeque a input ristretto è unadeque nella quale le rimozioni possono avvenire su entrambi i lati, e gli inserimenti da uno solo.
• Unadeque a output ristretto è unadeque 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, lacoda e lostack possono essere considerate particolari deque, e sono quindi implementabili usando una deque.

Unadeque supporta le seguenti operazioni:

Esistono almeno due modi di implementare efficientemente unadeque: attraverso unarray dinamico modificato o tramite unalista doppiamente concatenata.

Ladeque viene spesso implementata usando una variante dell'array dinamico che può accrescere la sua capienza da entrambi i lati e che viene anche chiamatodeque 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:

• Memorizzare il contenuto delladeque in unarray circolare ridimensionandolo solo quando è completamente pieno.
• Memorizzare il contenuto delladeque 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.

La libreria C++Standard Template Library offre laclassestd::deque e la classestd::list per l'implementazione degli array dinamici e della lista concatenata rispettivamente.

Java 6 offre una nuova interfacciaDeque che permette l'inserimento e la rimozione su entrambi i lati. È implementata da classi comeArrayDeque (anch'essa introdotta in Java 6) eLinkedList che forniscono le implementazioni dell'array dinamico e della lista concatenata rispettivamente.

Python 2.4 ha introdotto il modulocollections col supporto per gli oggettideque.

In PHP 5.3, l'estensione SPL contiene la classeSplDoublyLinkedList che può essere usata per l'implementazione di unadeque.

• In un'implementazione con lista doppiamente concatenata, lacomplessità di ogni operazione elencata sopra è indicata con la notazioneO-grande${\displaystyle O(1)}$.
• In un array dinamico, la complessità temporale di tutte le operazioni è${\displaystyle O(1)}$.

• (EN)Donald Ervin Knuth,The art of computer programming, 3ª ed., Addison-Wesley, 1997, pp. pp. 238–243,ISBN 978-0-201-89683-1.

• Array
• Lista concatenata
• Coda (informatica)
• Pila (informatica)

• (EN) Denis Howe,double-ended queue, inFree On-line Dictionary of Computing. Disponibile con licenzaGFDL
• SGI STL Documentation: deque<T, Alloc>, susgi.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, sucodeproject.com.URL consultato l'11 marzo 2009(archiviato dall'url originale il 30 agosto 2008).
• Diagram of a typical STL deque implementation, supages.cpsc.ucalgary.ca.
• deque implementation in flash actionscript 3 open source library, sudpdk.nl.URL consultato l'11 marzo 2009(archiviato dall'url originale il 24 luglio 2011).

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica

• Strutture dati

• Contestualizzare fonti - informatica
• Contestualizzare fonti - febbraio 2013