En ciencias da computación, unha cola de dobre extremo (abreviada deque) é un tipo de dato abstracto que serve como contedor, cun acceso restrinxido aos elementos almacenados. Como xeneralización tanto da pila como da cola, a deque pode ter funcións semellantes ás dun buffer de datos: pódese usar como retentor (cola) ou para retroceso (pila). Porén, ofrece maior flexibilidade na xestión da orde dos elementos, e algúns algoritmos se basean nas súas funcionalidades.

Descrición A cola de dobre extremo preséntase habitualmente como unha cola xeneralizada, o que lle dá o nome: é unha cola que «permite insercións e borrados nos dous extremos». A deque tamén se describe como unha xeneralización da pila, como «dúas pilas unidas pola base», cun elemento inferior compartido, ou como unha combinación de pila e cola. Así, pola contra, a cola e a pila son formas restrinxidas da deque.

Empréganse distintas analoxías con obxectos do mundo real para describir a deque. Compárase cun «barallo de cartas», co que a estrutura comparte algunhas propiedades e a pronuncia. Tamén se compara cun «collar con doas que se poden engadir ou retirar por calquera dos extremos». Como a cola, represéntase como un conxunto de elementos aliñados nun tubo aberto polos dous extremos; a diferenza da cola, os elementos poden moverse en ambas as direccións dentro do tubo. O «modelo ferroviario» introducido por Knuth (a partir do «patio de manobras» de Dijkstra) céntrase na similitude coa cola, cunha entrada e unha saída, e con conmutadores para seleccionar o lado da deque ao que se accede.

As operacións principais dunha deque actúan sobre calquera dos dous lados (ou extremos) da estrutura: engadir un elemento á colección (enqueue), retirar un elemento (dequeue) e ler un elemento (peek). Nun momento dado só se poden acceder a dous elementos, un por cada lado, segundo o historial da estrutura. O elemento designado nun lado é o último inserido nese lado (comportamento LIFO) ou, se non hai ningún, o máis antigo inserido no outro lado (comportamento FIFO). Esta política de servizo dálle á estrutura máis flexibilidade e versatilidade, pero tamén a fai máis difícil de comprender e usar.

As seis operacións principais dunha deque pódense describir de dúas maneiras, a partir das operacións de cola (ou pila): duplicándoas en cada extremo (add_left, add_right, etc.) ou xeneralizándoas cun parámetro que indica a localización na que se realiza a operación (add(left,...), add(right,...), etc.). Cada enfoque ten as súas vantaxes: o primeiro permite sobrecargar as operacións pero precisa nomes distintos en cada lado, mentres que o segundo simplifica a interface reducindo á metade o número de operacións e aproveita a simetría da estrutura. No que segue, adoptarase a segunda opción para evitar repeticións innecesarias.

A deque ten outros dous subtipos posibles: Unha deque restrinxida na entrada é aquela na que se pode borrar por calquera dos extremos, pero só se pode inserir por un extremo. É unha cola cunha saída traseira, ou unha pila cunha saída inferior. Unha deque restrinxida na saída é aquela na que se pode inserir por calquera dos extremos, pero só se pode borrar por un extremo. É unha cola cunha entrada frontal, ou unha pila cunha entrada inferior. A pesar das súas limitacións, estes subtipos teñen moitas aplicacións e algunhas das súas implementacións poden ser máis simples.

+ Exemplo de operacións nunha deque, partindo dunha deque baleira Operacións Contido add(left,DE) DE add(right,CK) DE, CK remove(left) CK add(left,STA) STA, CK add(right,QUE) STA, CK, QUE add(right,UE) STA, CK, QUE, UE remove(left) CK, QUE, UE remove(left) QUE, UE add(left,DE) DE, QUE, UE remove(right) DE, QUE

Segundo Knuth, estas estruturas adoitan describirse como distintas formas de listas lineais restrinxidas, ou secuencias. Manteñen os elementos contidos nunha orde dada mentres só permiten acceder a algúns deles: o primeiro e/ou o último da secuencia. Con todo, outros autores obxectan que «ocultan o seu dinamismo interno ao usuario» e que só as implementacións habituais son lineais. Consideran que estas estruturas de acceso restrinxido son: semiestruturadas: teñen «un elemento especial ou designado pero ningunha relación lóxica entre o resto dos elementos», e «a operación que elimina un elemento non toma ningún elemento como parámetro»; ou estruturas de puntos, «porque só existen dous puntos dunha cola para o mundo exterior»: a pila sería entón unha estrutura dun punto, mentres que a cola e a deque son estruturas de dous puntos.

Por exemplo, unha deque pódese implementar cun montículo mínimo-máximo ou cun conxunto: antes de inserir un elemento, etiquétase cun número enteiro usado como o seu valor no montículo, que depende do historial do contedor. Os elementos almacenados nun montículo non están ordenados e as súas localizacións dependen do estado interno da estrutura. Outra estrutura de acceso restrinxido común é a cola de prioridade, que non é unha estrutura linear.

A deque pódese xeneralizar engadindo algunhas operacións: unha deque con orde de montículo, ou mindeque, permite a operación find-min. Tamén é posible a concatenación rápida ou mesmo óptima.

Algúns autores consideran que a estrutura deque ten pouco uso, menos útil cós seus subtipos restrinxidos, especialmente a pila e a cola.

Especificación Aquí considérase a deque como non limitada: pode conter un número ilimitado (e indefinido) de elementos. Unha deque limitada é posible e require unha especificación lixeiramente distinta, pero cando se produce un desbordamento o comportamento depende da implementación: valor de erro, excepción, borrado, etc.

Sexa unha deque , un elemento e un lado con .

Operacións chave: con

Como estrutura linear, a deque pódese especificar en termos da concatenación (notada «») de secuencias e secuencias unitarias (notadas «»). Secuencia baleira:

Pódese obter unha especificación axiomática (ou alxébrica) da deque estendendo e fundindo as da pila e da cola.

Restricións axiomáticas:

como pila:

(1) como cola:

, para (2) , para (3)

A secuencia de operacións do exemplo anterior dá lugar á seguinte expresión, que se pode simplificar cos axiomas (1), (2) e (3), dando como resultado final .

Á inversa, a pila e a cola pódense especificar axiomaticamente en termos da deque.

Terminoloxía O termo deque úsase como abreviatura de Double-Ended QUEue (cola de dobre extremo). Ás veces emprégase dequeue, pero pode confundir, xa que o termo tamén se usa para a operación de retirar un elemento da deque. Unha deque tamén se pode chamar lista ligada cabeza-cola (head-tail linked list), aínda que propiamente isto se refire a unha implementación concreta. Unha deque restrinxida na saída pode designarse como steque (de stack-ended queue).

Non hai un vocabulario estándar asociado ás deques. Os termos enqueue e dequeue, tomados da estrutura de cola, denotan xeralmente as operacións básicas dunha deque, en calquera dos extremos. Pero os artigos e as implementacións reais adoitan usar nomes distintos. Os nomes das operacións varían segundo o contexto, o autor, a implementación ou a linguaxe de programación: por analoxía cunha cola: enqueue e dequeue, ou push e pull; por analoxía cunha pila: push e pop nun lado, e quizais inject e eject no outro; por analoxía cunha lista: cons e uncons nun lado, snoc e unsnoc no outro; por analoxía cun vector: append nun lado, prepend no outro, ou shift e unshift.

A diferenza das estruturas de datos asociadas, a deque é simétrica. Os seus lados poden nomearse libremente segundo o contexto: por analoxía cunha cola: front e back; por analoxía cunha pila: top e bottom; por analoxía cunha lista: head ou last; por analoxía cun vector: first e end, ou first e last; finalmente, left e right conservan a simetría orixinal da estrutura.

O nome completo dunha operación pode ser unha combinación do nome da operación básica e do nome do lado: por exemplo, push_front e pop_back. Tamén se implementan xeralmente operacións de «vista» (peek), que devolven o valor dun extremo sen extraelo. No contexto da programación funcional, a operación dequeue (que devolve dous valores: o elemento retirado e a nova deque) non se usa; substitúese por unha función peek (é dicir, head e last) e unha función que devolve a deque menos o extremo, é dicir, tail e init.

Implementacións Hai polo menos dúas formas comúns de implementar eficientemente unha deque, que adoitan enfrontarse entre si: cunha lista ligada dobre ou cun vector dinámico modificado. Hai moitas variacións e as implementacións reais adoitan ser solucións híbridas. Ademais, existen varias implementacións puramente funcionais da cola de dobre extremo.

Lista ligada dobre Aínda que unha lista simple pode implementar unha deque, unha lista ligada dobre é máis adecuada pola súa simetría para conseguir un acceso rápido aos dous extremos da lista (head e tail, de aí o nome lista ligada cabeza-cola). A solución obvia é xestionar dúas referencias; alternativamente, a deque pódese construír como lista circular.

Nunha implementación con lista ligada dobre, e supoñendo que non hai custo de asignación/liberación, a complexidade temporal de todas as operacións da deque é . Ademais, a inserción ou o borrado no medio, dado un iterador, tamén se pode facer en tempo constante; con todo, o tempo de acceso aleatorio por índice é . Do mesmo xeito, atopar un elemento concreto require normalmente . As estruturas de datos ligados teñen xeralmente pouca localidade de referencia.

Vector dinámico miniatura|alt=Inserción nun vector dinámico.|Insírense varios valores ao final dun vector dinámico mediante expansión xeométrica. As celas grises indican espazo reservado para a expansión. A maioría das insercións son rápidas (tempo constante), mentres que algunhas son lentas pola necesidade de reasignación (tempo ). Neste caso tamén, aínda que se pode usar un vector dinámico para implementar unha deque, é máis adecuada unha variante que poida medrar polos dous extremos, chamada ás veces deque de vector. Isto pódese conseguir de varias maneiras, por exemplo: desprazando a posición do primeiro elemento do vector na memoria reservada: o espazo non usado distribúese polos dous lados dos datos; cun vector circular.

A complexidade temporal amortizada de todas as operacións dunha deque de vector é , grazas á expansión xeométrica do buffer traseiro. Ademais, o acceso aleatorio por índice leva tempo constante; pero o tempo medio de inserción ou borrado no medio é . Grazas ao acceso aleatorio rápido, atopar un elemento nun vector ordenado leva tempo (busca binaria). Cada vez que se redimensiona o vector, todo o contido móvese: o uso de memoria duplícase momentaneamente e pérdense todas as referencias directas (externas) ao contido.

Implementacións funcionais e persistentes As actualizacións dunha lista ligada dobre inmutable non ofrecen directamente o mesmo custo constante ca as dunha lista mutable: conservar versións pode requirir copiar nós e reconstruír ligazóns. Tamén copiar un vector completo en cada actualización sería custoso; os vectores persistentes adoitan representarse con árbores. Unha implementación puramente funcional da deque pode partir de listas ligadas simples e técnicas de compartición e reequilibrado para manter a persistencia.