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 , para la cual se pueden agregar o eliminar elementos del frente (cabeza) o espalda (cola). [2] A menudo también se le llama lista enlazada cabecera-cola , aunque propiamente esto se refiere a una implementación de estructura de datos específica de un deque (ver más abajo).
Deque a veces se escribe dequeue , pero este uso generalmente está obsoleto en la literatura técnica o en la escritura técnica 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 Estructuras de datos y algoritmos , lo escriben fuera de cola . John Mitchell , autor de Conceptos en lenguajes de programación, también utiliza esta terminología.
Esto difiere del tipo de datos abstractos de cola o lista de primero en entrar, primero en salir ( FIFO ), donde los elementos solo se pueden agregar en un extremo y eliminarse en el otro. Esta clase de datos generales tiene algunos subtipos posibles:
Tanto los tipos de listas básicos como los más comunes en informática, colas y pilas pueden considerarse especializaciones de deques y pueden implementarse utilizando deques.
Las operaciones básicas en una cola son poner en cola y sacar de cola en cualquier extremo. También se implementan generalmente operaciones de visualización , que devuelven el valor en ese extremo sin sacarlo de la cola.
Los nombres varían entre idiomas; 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 matriz 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 amortizada en tiempo constante en ambos extremos, en su lugar. de un solo extremo. Tres implementaciones comunes incluyen:
Las colas de dos extremos también se pueden implementar como una estructura de datos puramente funcional . [3] : 115 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) el peor de los casos, pero requiere listas diferidas con memorización . El segundo, sin listas perezosas ni memorización, se presenta al final de las secciones. Su tiempo de amortización es O (1) si no se utiliza la persistencia; pero la complejidad de una operación en el peor momento 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, eso 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 dos extremos se representa como un séxtuplo (len_front, front, tail_front, len_rear, rear, tail_rear)donde fronthay una lista vinculada que contiene el frente de la cola de longitud len_front. De manera similar, reares una lista enlazada que representa el reverso del final de la cola, de longitud len_rear. Además, se asegura que |front| ≤ 2|rear|+1e |rear| ≤ 2|front|+1intuitivamente 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_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 dos extremos contiene nelementos en la lista frontal y nelementos en la lista posterior, la invariante de desigualdad permanece satisfecha 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 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 una segunda ocasión explicaremos cómo modificar un deque que no satisface el invariante por uno que sí lo satisface. Sin embargo, utilizan el invariante, en el sentido de que si el frente está vacío, entonces el trasero 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 ) inserción divertida ' ( x , ( len_front , front , tail_front , len_rear , rear , tail_rear )) = ( len_front+ 1 , CONS ( x , front ), drop ( 2 , tail_front ), len_rear , rear , drop ( 2 , tail_rear )) cabeza divertida ((_, CONS ( h , _), _, _, _, _)) = h cabeza divertida ((_, NIL , _, _ , CONS ( h , NIL ), _)) = h fun tail' (( len_front , CONS ( head_front , front ), tail_front , len_rear , rear , tail_rear )) = ( len_front - 1 , front , drop ( 2 , tail_front ) , len_rear , rear , drop ( 2 , tail_rear )) fun tail' ((_, NIL , _, _, CONS ( h , NIL ), _)) = vacío Queda por explicar cómo definir un método balanceque reequilibre el deque si insert'rompe tailel invariante. El método inserty tailse puede definir aplicando primero insert'y tail'luego aplicando balance.
equilibrio divertido ( q as ( len_front , front , tail_front , len_rear , rear , tail_rear )) = let floor_half_len = ( len_front + len_rear ) / 2 in let ceil_half_len = len_front + len_rear - Floor_half_len in if len_front > 2 *len_rear+ 1 entonces let val front' = tomar ( ceil_half_len , front ) val rear' = rotarDrop ( rear , Floor_half_len , front ) in ( ceil_half_len , front' , front' , Floor_half_len , rear' , rear' ) else if len_front > 2 *len_rear+ 1 entonces let val rear' = tomar ( floor_half_len , rear ) val front' = rotarDrop ( front , ceil_half_len , rear ) in ( ceil_half_len , front' , front' , Floor_half_len , rear' , rear' ) else qdonde rotateDrop(front, i, rear))devuelve la concatenación de fronty de drop(i, rear). Eso se front' = rotateDrop(front, ceil_half_len, rear)incluye en front'el contenido de fronty el contenido de reareso aún no está en rear'. Dado que eliminar nelementos lleva tiempo, utilizamos la pereza para asegurarnos de que los elementos se eliminen de dos en dos, realizándose dos caídas durante cada operación . tail'insert'
divertido rotarDrop ( front , i , rear ) = si i < 2 entonces rotateRev ( front , drop ( i , rear ), NIL ) de lo contrario, deja que CONS ( x , front' ) = front en CONS ( x , rotateDrop ( front' , j - 2 , caída ( 2 , trasera )))donde rotateRev(front, middle, rear)hay una función que devuelve el frente, seguido por el medio invertido, seguido por la parte trasera. Esta función también se define utilizando la pereza para garantizar que se pueda calcular paso a paso, ejecutando un paso durante cada uno insert'y tail'tomando un tiempo constante. Esta función utiliza el invariante que |rear|-2|front|es 2 o 3.
divertido rotarRev ( NIL , trasero , a ) = revertir ( trasero ) ++a divertido rotarRev ( CONS ( x , delantero ), trasero , a ) = CONS ( x , rotarRev ( frente , 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 diferida de la implementación, esta sería una implementación no persistente de la cola en O (1) tiempo amortizado . En este caso, las listas tail_fronty tail_rearpodrían eliminarse de la representación de la cola de doble extremo.
Los contenedores de Ada proporcionan los paquetes genéricos Ada.Containers.Vectorsy Ada.Containers.Doubly_Linked_Lists, para las implementaciones de matriz dinámica y lista vinculada, respectivamente.
La biblioteca de plantillas estándar de C++ proporciona las plantillas de clase std::dequey std::list, para las implementaciones de múltiples matrices y listas vinculadas, 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 nueva en Java 6) y LinkedList, que proporcionan implementaciones de matriz dinámica y lista vinculada, respectivamente. Sin embargo, ArrayDequeal contrario de su nombre, no admite acceso aleatorio.
El prototipo de matriz de Javascript y las matrices de Perl tienen soporte nativo para eliminar (shift y pop) y agregar (desplazar y push) elementos en ambos extremos.
Python 2.4 introdujo el collectionsmódulo 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 clase 'SplDoublyLinkedList' que se puede utilizar para implementar estructuras de datos Deque. Anteriormente, 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. Existen otras posibilidades (rápidas) para implementar colas dobles puramente funcionales (por lo tanto, también persistentes ) (la mayoría utiliza una evaluación muy diferida ). [3] [4] Kaplan y Tarjan fueron los primeros en implementar deques catenables persistentes y confluentes óptimos. [5] Su implementación fue estrictamente funcional en el sentido de que no utilizó una evaluación diferida. Okasaki simplificó la estructura de datos mediante el uso de 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. [6] Kaplan, Okasaki y Tarjan produjeron una versión amortizada, sin arranque y más simple que se puede implementar mediante una evaluación diferida o utilizando de manera más eficiente la mutación de una manera más amplia pero aún restringida. [7] Mihaescu y Tarjan crearon una implementación estrictamente puramente funcional (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. [8]
Rust std::collectionsincluye VecDeque, que implementa una cola de doble extremo utilizando un búfer de anillo ampliable.
_-_Google_Android_12_(cropped).png/1280px-Back_button_history_(Ecosia_browser_-_Google_Pixel_4a)_-_Google_Android_12_(cropped).png){kind=tracking}
Un ejemplo en el que se puede utilizar un deque es el algoritmo de robo de trabajo . [9] Este algoritmo implementa la programación de tareas para varios procesadores. Se mantiene una cola separada con subprocesos a ejecutar para cada procesador. Para ejecutar el siguiente hilo, el procesador obtiene el primer elemento de la deque (usando la operación deque "eliminar el primer elemento"). Si el hilo actual se bifurca, se vuelve a colocar al frente del deque ("insertar elemento al frente") y se ejecuta un nuevo hilo. Cuando uno de los procesadores termina la ejecución de sus propios subprocesos (es decir, su deque está vacío), puede "robar" un subproceso de otro procesador: obtiene el último elemento del deque de otro procesador ("eliminar el último elemento") y ejecuta él. El algoritmo de robo de trabajo es utilizado por la biblioteca Threading Building Blocks (TBB) de Intel para la programación paralela.