Cola de dos extremos

En informática , una cola de doble extremo (abreviada como deque , / dɛk / DEK ^[1] ) es un tipo de datos abstracto que generaliza una cola , a la que se pueden agregar o quitar elementos ya sea del frente (cabeza) o de la parte posterior (cola). [ ^2] También se la suele llamar lista enlazada de cabeza-cola , aunque propiamente esto se refiere a una implementación de estructura de datos específica de una deque (ver más abajo).

Deque a veces se escribe dequeue , pero este uso generalmente está en desuso en la literatura técnica o en los escritos técnicos porque dequeue también es un verbo que significa "eliminar de una cola". Sin embargo, varias bibliotecas y algunos escritores, como Aho , Hopcroft y Ullman en su libro de texto Data Structures and Algorithms , lo escriben dequeue . John Mitchell , autor de Concepts in Programming Languages, también utiliza esta terminología.

Esto difiere del tipo de datos abstractos de cola o lista FIFO ( primero en entrar, primero en salir ), donde los elementos solo se pueden agregar en un extremo y quitar en el otro. Esta clase de datos general tiene algunos subtipos posibles:

• Una deque con entrada restringida es aquella en la que se puede eliminar desde ambos extremos, pero se puede insertar solo en un extremo.
• Una deque con salida restringida es aquella en la que la inserción se puede realizar en ambos extremos, pero la eliminación se puede realizar desde un solo extremo.

Tanto los tipos de listas más comunes como los más básicos en informática, las colas y las pilas , pueden considerarse especializaciones de deques y pueden implementarse mediante deques. Un deque es una estructura de datos que permite a los usuarios realizar operaciones de inserción y extracción en ambos extremos, lo que proporciona flexibilidad en la gestión del orden de los elementos.

Las operaciones básicas en una cola de doble cola son poner y quitar de la cola en cada extremo. También se implementan generalmente operaciones de inspección , que devuelven el valor en ese extremo sin quitarlo de la cola.

Los nombres varían según el idioma; las principales implementaciones incluyen:

Hay al menos dos formas comunes de implementar eficientemente un deque: con una matriz dinámica modificada o con una lista doblemente enlazada .

El enfoque de matriz dinámica utiliza una variante de una matriz dinámica que puede crecer desde ambos extremos, a veces llamada deques de matriz . Estos deques de matriz tienen todas las propiedades de una matriz dinámica, como acceso aleatorio de tiempo constante , buena localidad de referencia e inserción/eliminación ineficiente en el medio, con la adición de inserción/eliminación de tiempo constante amortizada en ambos extremos, en lugar de solo en un extremo. Tres implementaciones comunes incluyen:

• Almacenar el contenido de deque en un búfer circular y cambiar el tamaño solo cuando el búfer se llena. Esto reduce la frecuencia de los cambios de tamaño.
• Asignar contenidos de deque desde el centro de la matriz subyacente y redimensionar la matriz subyacente cuando se alcanza uno de los extremos. Este enfoque puede requerir redimensionamientos más frecuentes y desperdiciar más espacio, en particular cuando los elementos solo se insertan en un extremo.
• Almacenar contenidos en múltiples matrices más pequeñas y asignar matrices adicionales al principio o al final según sea necesario. La indexación se implementa manteniendo una matriz dinámica que contiene punteros a cada una de las matrices más pequeñas.

Las colas de doble extremo también se pueden implementar como una estructura de datos puramente funcional . ^{[3] : 115} Existen dos versiones de la implementación. La primera, llamada ' deque en tiempo real , se presenta a continuación. Permite que la cola sea persistente con operaciones en O (1) tiempo de peor caso, pero requiere listas perezosas con memorización . La segunda, sin listas perezosas ni memorización, se presenta al final de las secciones. Su tiempo amortizado es O (1) si no se usa la persistencia; pero la complejidad en el peor tiempo de una operación es O ( n ) donde n es el número de elementos en la cola de doble extremo.

Recordemos que, para una lista l, , |l|denota su longitud, que NILrepresenta una lista vacía y CONS(h, t)representa la lista cuya cabeza es hy cuya cola es t. Las funciones drop(i, l)y take(i, l)devuelven la lista lsin sus primeros ielementos, y los primeros ielementos de l, respectivamente. O, si |l| < i, devuelven la lista vacía y lrespectivamente.

Una cola de doble extremo se representa como un séxtuple (len_front, front, tail_front, len_rear, rear, tail_rear)donde frontes una lista enlazada que contiene el frente de la cola de longitud len_front. De manera similar, reares una lista enlazada que representa el reverso de la parte posterior de la cola, de longitud len_rear. Además, se asegura que |front| ≤ 2|rear|+1y |rear| ≤ 2|front|+1- intuitivamente, significa que tanto el frente como la parte posterior contienen entre un tercio menos uno y dos tercios más uno de los elementos. Finalmente, tail_fronty tail_rearson colas de fronty de rear, permiten programar el momento en el que se fuerzan algunas operaciones perezosas. Tenga en cuenta que, cuando una cola de doble extremo contiene nelementos en la lista frontal y nelementos en la lista posterior, entonces el invariante de desigualdad permanece satisfecho después de ilas inserciones y deliminaciones cuando (i+d) ≤ n/2. Es decir, como máximo n/2pueden ocurrir operaciones entre cada reequilibrio.

Primero, vamos a dar una implementación de las diversas operaciones que afectan al frente de la deque - cons, head y tail. Esas implementaciones no necesariamente respetan el invariante. En una segunda ocasión, explicaremos cómo modificar una deque que no satisface el invariante para convertirla en una que lo satisfaga. Sin embargo, utilizan el invariante, ya que si el frente está vacío, entonces la parte posterior tiene como máximo un elemento. Las operaciones que afectan la parte posterior de la lista se definen de manera similar por simetría.

vacío  =  ( 0 ,  NIL ,  NIL ,  0 ,  NIL ,  NIL ) 
divertido  insertar' ( x ,  ( len_delante ,  delantero ,  cola_delantera ,  len_trasero ,  trasero ,  cola_trasera ))  = 
  ( len_delante + 1 ,  CONS ( x ,  delantero ),  soltar ( 2 ,  cola_delantera ),  len_trasero ,  trasero ,  soltar ( 2 ,  cola_trasera )) 
divertido  cabeza ((_,  CONS ( h ,  _),  _,  _,  _,  _))  =  h 
divertido  cabeza ((_,  NIL ,  _,  _,  CONS ( h ,  NIL ),  _))  =  h 
divertido  cola' (( len_delante ,  CONS ( cabeza_delantera ,  delantero ),  cola_delantera ,  len_trasero ,  trasero ,  cola_trasera ))  = 
  ( len_delante  -  1 ,  delantero ,  soltar ( 2 ,  cola_delantera ),  len_trasero ,  trasero ,  soltar ( 2 ,  cola_trasera )) 
diversión  cola' ((_,  NIL ,  _,  _,  CONS ( h ,  NIL ),  _))  =  vacío

Queda por explicar cómo definir un método balanceque reequilibre la deque si insert'o tailrompe la invariante. El método inserty tailse puede definir aplicando primero insert'y tail'y luego aplicando balance.

 equilibrio divertido ( q  como  ( len_delante ,  delantero ,  cola_delantera ,  len_trasera ,  trasera ,  cola_trasera ))  = 
  let  suelo_mitad_len  =  ( len_delante  +  len_trasera )  /  2  en 
  let  techo_mitad_len  =  len_delante  +  len_trasera  -  suelo_mitad_len  en 
  si  len_delante  >  2 * len_trasera+ 1  entonces 
    let  val  delantero'  =  tomar ( techo_mitad_len ,  delantero ) 
        val  trasero'  =  rotateDrop ( trasero ,  suelo_mitad_len ,  delantero ) 
    en  ( techo_mitad_len ,  delantero' ,  delantero' ,  suelo_mitad_len ,  trasero' ,  trasero' ) 
  de lo contrario  si  len_delante  >  2 * len_trasera+ 1  entonces 
    let  val  trasero'  =  tomar ( suelo_mitad_len ,  trasero ) 
        val  delantero'  =  rotateDrop ( delantero ,  techo_mitad_len ,  trasero ) 
    en  ( longitud_mitad_techo ,  delantero' ,  delantero' ,  longitud_mitad_piso ,  trasero' ,  trasero' ) 
  de lo contrario  q

donde rotateDrop(front, i, rear))devuelve la concatenación de fronty de drop(i, rear). Que se front' = rotateDrop(front, ceil_half_len, rear)coloca en front'el contenido de fronty el contenido de rearque no está ya en rear'. Como eliminar nelementos lleva tiempo, usamos la pereza para asegurarnos de que los elementos se eliminen de dos en dos, con dos eliminaciones realizadas durante cada operación . ${\displaystyle O(n)}$tail'insert'

fun  rotateDrop ( delantero ,  i ,  trasero )  = 
  si  i  <  2  entonces  rotateRev ( delantero ,  soltar ( i ,  trasero ),  NIL ) 
  de lo contrario,  dejar  CONS ( x ,  delantero' )  =  delantero  en 
    CONS ( x ,  rotateDrop ( delantero' ,  j- 2 ,  soltar ( 2 ,  trasero )))

donde rotateRev(front, middle, rear)es una función que devuelve el frente, seguido por el medio invertido, seguido por la parte posterior. Esta función también se define utilizando la pereza para garantizar que se pueda calcular paso a paso, con un paso ejecutado durante cada insert'y tail'y tomando un tiempo constante. Esta función utiliza el invariante que |rear|-2|front|es 2 o 3.

fun  rotateRev ( NIL ,  trasero ,  a )  = 
  revertir ( trasero ) ++a 
fun  rotateRev ( CONS ( x ,  delantero ),  trasero ,  a )  = 
  CONS ( x ,  rotateRev ( delante ,  soltar ( 2 ,  trasero ),  revertir ( tomar ( 2 ,  trasero )) ++a ))

¿Dónde ++está la función que concatena dos listas?

Tenga en cuenta que, sin la parte perezosa de la implementación, esta sería una implementación no persistente de la cola en tiempo amortizado O (1) . En este caso, las listas y podrían eliminarse de la representación de la cola de doble extremo. tail_fronttail_rear

Los contenedores de AdaAda.Containers.Vectors proporcionan los paquetes genéricos y Ada.Containers.Doubly_Linked_Lists, para las implementaciones de matrices dinámicas y listas enlazadas, respectivamente.

La biblioteca de plantillas estándar de C++ proporciona las plantillas de clase std::dequey std::list, para las implementaciones de matrices múltiples y listas enlazadas, respectivamente.

A partir de Java 6, el marco de colecciones de Java proporciona una nueva Dequeinterfaz que proporciona la funcionalidad de inserción y eliminación en ambos extremos. Se implementa mediante clases como ArrayDeque(también nuevas en Java 6) y LinkedList, que proporcionan las implementaciones de matriz dinámica y lista enlazada, respectivamente. Sin embargo, ArrayDeque, al contrario de lo que sugiere su nombre, no admite el acceso aleatorio.

El prototipo de matriz de Javascript y las matrices de Perl tienen soporte nativo tanto para eliminar (shift y pop) como para agregar (unshift y push) elementos en ambos extremos.

Python 2.4 introdujo el collectionsmódulo con soporte para objetos deque. Se implementa mediante una lista doblemente enlazada de submatrices de longitud fija.

A partir de PHP 5.3, la extensión SPL de PHP contiene la clase 'SplDoublyLinkedList' que se puede utilizar para implementar estructuras de datos Deque. Antes, para crear una estructura Deque, se debían utilizar las funciones de matriz array_shift/unshift/pop/push.

El módulo Data.Sequence de GHC implementa una estructura deque funcional y eficiente en Haskell . La implementación utiliza árboles de 2 a 3 dedos anotados con tamaños. Hay otras posibilidades (rápidas) para implementar colas dobles puramente funcionales (por lo tanto también persistentes ) (la mayoría utilizando una evaluación muy diferida ). ^{[3] [4]} Kaplan y Tarjan fueron los primeros en implementar colas dobles catenables persistentes y confluentes óptimas. ^[5] Su implementación fue estrictamente puramente funcional en el sentido de que no utilizó una evaluación diferida. Okasaki simplificó la estructura de datos utilizando una evaluación diferida con una estructura de datos con arranque y degradando los límites de rendimiento del peor de los casos a amortizado. ^[6] Kaplan, Okasaki y Tarjan produjeron una versión amortizada, sin arranque y más simple que se puede implementar utilizando una evaluación diferida o de manera más eficiente utilizando la mutación de una manera más amplia pero aún restringida. ^[7] Mihaescu y Tarjan crearon una implementación estrictamente puramente funcional más simple (pero aún altamente compleja) de deques catenables, y también una implementación mucho más simple de deques no catenables estrictamente puramente funcionales, ambas con límites óptimos en el peor de los casos. ^[8]

Rust std::collectionsincluye VecDeque, que implementa una cola de doble extremo utilizando un búfer de anillo ampliable.

• En una implementación de lista doblemente enlazada y suponiendo que no hay sobrecarga de asignación/desasignación, la complejidad temporal de todas las operaciones de deque es O(1) . Además, la complejidad temporal de inserción o eliminación en el medio, dado un iterador, es O(1); sin embargo, la complejidad temporal de acceso aleatorio por índice es O(n).
• En una matriz en crecimiento, la complejidad temporal amortizada de todas las operaciones de deque es O(1) . Además, la complejidad temporal del acceso aleatorio por índice es O(1); pero la complejidad temporal de la inserción o eliminación en el medio es O(n) .

Un ejemplo en el que se puede utilizar una deque es el algoritmo de robo de trabajo . ^[9] Este algoritmo implementa la programación de tareas para varios procesadores. Se mantiene una deque separada con subprocesos a ejecutar para cada procesador. Para ejecutar el siguiente subproceso, el procesador obtiene el primer elemento de la deque (utilizando la operación de deque "eliminar el primer elemento"). Si el subproceso actual se bifurca, se vuelve a poner al frente de la deque ("insertar elemento al frente") y se ejecuta un nuevo subproceso. Cuando uno de los procesadores termina la ejecución de sus propios subprocesos (es decir, su deque está vacía), puede "robar" un subproceso de otro procesador: obtiene el último elemento de la deque de otro procesador ("eliminar el último elemento") y lo ejecuta. El algoritmo de robo de trabajo es utilizado por la biblioteca Threading Building Blocks (TBB) de Intel para la programación paralela.

• Tubo
• Cola de prioridad

• Implementación de deque de código abierto con seguridad de tipos en Comprehensive C Archive Network
• Documentación STL de SGI: deque<T, Alloc>
• Proyecto de código: un estudio en profundidad del contenedor STL Deque
• Implementación de Deque en C Archivado el 6 de marzo de 2014 en Wayback Machine.
• Implementación de VBScript de pila, cola, deque y árbol rojo-negro
• Varias implementaciones de deques no catenables en Haskell