Cola de dos extremos

En informática, una cola de dos extremos (abreviado como deque, pronunciado deck, como "cheque") es un tipo de datos abstracto que generaliza una cola, para la cual se pueden agregar o quitar elementos del frente (cabeza) o del reverso (cola). A menudo también se denomina lista enlazada de cabeza y cola, aunque propiamente se refiere a una estructura de datos específica implementación de una deque (ver más abajo).

Convenciones de nomenclatura

Deque a veces se escribe dequeue, pero este uso generalmente está en desuso en la literatura técnica o la escritura técnica porque dequeue también es un verbo que significa & #34;para eliminar de una cola". Sin embargo, varias bibliotecas y algunos escritores, como Aho, Hopcroft y Ullman en su libro de texto Estructuras de datos y algoritmos, lo deletrean dequeue. John Mitchell, autor de Concepts in Programming Languages, también usa esta terminología.

Distinciones y subtipos

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

• Una deque restringida por entrada es una donde la eliminación se puede hacer desde ambos extremos, pero la inserción se puede hacer sólo en un extremo.
• Una deque restringida por la salida es una donde la inserción se puede hacer en ambos extremos, pero la eliminación se puede hacer sólo desde un extremo.

Tanto los tipos de lista básicos como los más comunes en computación, las colas y las pilas pueden considerarse especializaciones de deques y pueden implementarse mediante deques.

Operaciones

Las operaciones básicas en un deque son poner en cola y dequeue en cualquier extremo. También se implementan generalmente las operaciones peek, que devuelven el valor en ese extremo sin sacarlo de la cola.

Los nombres varían entre idiomas; Las principales implementaciones incluyen:

Implementaciones

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

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

• Guardar contenidos deque en un búfer circular, y sólo redimensionarse cuando el búfer se llena. Esto disminuye la frecuencia de los tamaños.
• Asignar contenidos deque desde el centro de la matriz subyacente, y redimensionar la matriz subyacente cuando se llega a cualquier extremo. Este enfoque puede requerir un redimensionamiento más frecuente y desperdiciar más espacio, especialmente cuando los elementos sólo se insertan en un extremo.
• Guardar contenidos en múltiples arrays más pequeños, asignando arrays 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 uno de los arrays más pequeños.

Implementación puramente funcional

Las colas de dos extremos también se pueden implementar como una estructura de datos puramente funcional. Existen dos versiones de la implementación. El primero, llamado 'deque en tiempo real, se presenta a continuación. Permite que la cola sea persistente con operaciones en O(1) en el peor de los casos, pero requiere listas perezosas con memorización. El segundo, 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 momento de una operación es O(n) donde n es el número de elementos en la cola doble.

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

Deques en tiempo real a través de reconstrucción y programación perezosas

Una cola de dos extremos se representa como un séxtuple (len_front, front, tail_front, len_rear, rear, tail_rear) donde front es una lista enlazada que contiene el frente de la cola de longitud len_front. De manera similar, rear es una lista enlazada que representa el reverso de la parte trasera de la cola, de longitud len_rear. Además, se asegura que |front| ≤ 2|trasero|+1 y |trasero| ≤ 2|frontal|+1 - intuitivamente, significa que tanto la parte delantera como la trasera contienen entre un tercio menos uno y dos tercios más uno de los elementos. Finalmente, tail_front y tail_rear son colas de front y de rear, que permiten programar el momento en que algunas operaciones perezosas son forzados. Tenga en cuenta que, cuando una cola de dos extremos contiene elementos n en la lista frontal y elementos n en la lista posterior, la invariante de desigualdad permanece satisfecha después de i< /code> inserciones y d eliminaciones cuando (i+d) ≤ n/2. Es decir, como máximo pueden ocurrir n/2 operaciones entre cada reequilibrio.

Primero demos una implementación de las diversas operaciones que afectan el frente del deque: contras, cabeza y cola. Esas implementaciones no necesariamente respetan el invariante. En un segundo momento explicaremos cómo modificar un deque que no satisface el invariante en uno que lo satisfaga. Sin embargo, usan el invariante, en el sentido de que si el frente está vacío, la parte trasera tiene como máximo un elemento. Las operaciones que afectan al final de la lista se definen de manera similar por simetría.

vacío = ()0, NIL, NIL, 0, NIL, NIL)diversión insertar '()x, ()len_front, frontal, tail_front, len_rear, trasero, tail_rear) = ()len_front+1, CONS()x, frontal), gota()2, tail_front), len_rear, trasero, gota()2, tail_rear)diversión cabeza(__, CONS()h, _), _ _ _ _) = hdiversión cabeza(__, NIL, _ _ CONS()h, NIL), _) = hdiversión cola '()len_front, CONS()head_front, frontal), tail_front, len_rear, trasero, tail_rear) = ()len_front - 1, frontal, gota()2, tail_front), len_rear, trasero, gota()2, tail_rear)diversión cola '(__, NIL, _ _ CONS()h, NIL), _) = vacío

Queda por explicar cómo definir un método balance que reequilibra el deque si insert' o tail rompen el invariante. El método insert y tail se puede definir aplicando primero insert' y tail' y luego aplicando saldo.

diversión saldo()q como ()len_front, frontal, tail_front, len_rear, trasero, tail_rear) = Deja floor_half_len = ()len_front + len_rear) / 2 dentro Deja ceil_half_len = len_front + len_rear - floor_half_len dentro si len_front ■ 2*len_rear+1 entonces Deja val frontal ' = Toma.()ceil_half_len, frontal) val trasero ' = rotación Suelta()trasero, floor_half_len, frontal) dentro ()ceil_half_len, frontal ', frontal ', floor_half_len, trasero ', trasero ') más si len_front ■ 2*len_rear+1 entonces Deja val trasero ' = Toma.()floor_half_len, trasero) val frontal ' = rotación Suelta()frontal, ceil_half_len, trasero) dentro ()ceil_half_len, frontal ', frontal ', floor_half_len, trasero ', trasero ') más q

Donde rotateDrop(front, i, rear)) devolver la concatenación de front y de drop(i, rear). Eso esfront' = rotateDrop(front, ceil_half_len, rear) puesto front' el contenido de front y el contenido de rear que ya no está rear'. Desde que caen n elementos ${displaystyle O(n)}$ tiempo, utilizamos la pereza para asegurar que los elementos se reduzcan dos por dos, con dos gotas que se hacen durante cada uno tail' y cada uno insert' operación.

diversión rotación Suelta()frontal, i, trasero) = si i . 2 entonces rotación Rev()frontal, gota()i, trasero), $NIL) más Deja $CONS()x, frontal ') = frontal dentro $CONS ()x, rotación Suelta()frontal ', j-2, gota()2, trasero))

donde rotateRev(front, middle, rear) es una función que devuelve el frente, seguido del medio invertido, seguido del trasero. 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 usa el invariante de que |rear|-2|front| es 2 o 3.

diversión rotación Rev()NIL, trasero, a)= inversión()trasero+a)diversión rotación Rev()CONS()x, frontal), trasero, a)= CONS()x, rotación Rev()frontal, gota()2, trasero), inversión ()Toma.()2, trasero)++a)

donde ++ es la función que concatena dos listas.

Implementación sin pereza

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

Soporte de idiomas

Los contenedores de Ada proporcionan los paquetes genéricos Ada.Containers.Vectors y Ada.Containers.Doubly_Linked_Lists, para las implementaciones de matriz dinámica y lista enlazada, respectivamente.

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

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

Prototipo de matriz de Javascript & Los arreglos de Perl tienen soporte nativo tanto para eliminar (cambiar y sacar) como para agregar (quitar y empujar) elementos en ambos extremos.

Python 2.4 introdujo el módulo colecciones con soporte para objetos deque. Se implementa utilizando una lista doblemente enlazada de subarreglos de longitud fija.

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

El módulo Data.Sequence de GHC implementa una estructura deque eficiente y funcional en Haskell. La implementación utiliza 2 o 3 árboles de 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 usa una evaluación muy perezosa). Kaplan y Tarjan fueron los primeros en implementar deques catenables persistentes confluentes óptimos. Su implementación fue estrictamente puramente funcional en el sentido de que no utilizó una evaluación perezosa. Okasaki simplificó la estructura de datos utilizando una evaluación diferida con una estructura de datos de arranque y degradando los límites de rendimiento del peor de los casos a amortizado. Kaplan, Okasaki y Tarjan produjeron una versión amortizada más simple, sin arranque, que se puede implementar mediante una evaluación perezosa o de manera más eficiente mediante la mutación de una manera más amplia pero aún restringida. Mihaesau y Tarjan crearon una implementación estrictamente puramente funcional más simple (pero aún muy compleja) de deques catenables, y también una implementación mucho más simple de deques no catenables estrictamente puramente funcionales, los cuales tienen límites óptimos en el peor de los casos.

Las std::collections de Rust incluyen VecDeque, que implementa una cola de dos extremos mediante un búfer de anillo ampliable.

Complejidad

• En la aplicación de una lista doblemente vinculada y asumiendo que no se asignen ni desalojen, la complejidad del tiempo de todas las operaciones de que se trate es O(1). Además, la complejidad del tiempo de inserción o eliminación en el medio, dada un iterador, es O(1); sin embargo, la complejidad del tiempo de acceso aleatorio por índice es O(n).
• En una matriz creciente, la complejidad amortizada del tiempo de todas las operaciones deque es O(1). Además, la complejidad temporal del acceso aleatorio por índice es O(1); pero la complejidad del tiempo de inserción o eliminación en el medio es O(n).

Aplicaciones

Se puede utilizar una cola doble para almacenar el historial de navegación: se añaden nuevos sitios web al final de la cola, mientras que las entradas más antiguas serán eliminadas cuando la historia sea demasiado grande. Cuando un usuario pide borrar el historial de navegación durante la última hora, se eliminan las entradas más recientes.

Un ejemplo en el que se puede usar un deque es el algoritmo de robo de trabajo. Este algoritmo implementa la programación de tareas para varios procesadores. Se mantiene un deque separado con subprocesos para ejecutar para cada procesador. Para ejecutar el siguiente subproceso, el procesador obtiene el primer elemento de la deque (mediante la operación de deque "eliminar el primer elemento"). Si el subproceso actual se bifurca, se vuelve a colocar al frente del deque ("insertar elemento al frente") y se ejecuta un nuevo subproceso. Cuando uno de los procesadores finaliza la ejecución de sus propios subprocesos (es decir, su deque está vacío), puede "robar" un hilo de otro procesador: obtiene el último elemento del 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.