En ciencias de la computación , una cola de dos extremos (abreviada como deque , que se pronuncia deck , como "check" [1] ) es un tipo de datos abstracto que generaliza una cola , para la cual se pueden agregar o eliminar elementos del frente (head ) o espalda (cola). [2] También se le llama a menudo lista enlazada head-tail , aunque apropiadamente esto se refiere a una implementación de estructura de datos específica de una deque (ver más abajo).
Convenciones de nombres
Deque a veces se escribe dequeue , pero este uso generalmente está desaprobado en la literatura técnica o en la escritura técnica porque dequeue también es un verbo que significa "quitar 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 usa esta terminología.
Distinciones y subtipos
Esto difiere del tipo de datos abstractos de cola o de la lista primero en entrar, primero en salir ( FIFO ), donde los elementos solo se pueden agregar en un extremo y eliminar del otro. Esta clase de datos generales tiene algunos subtipos posibles:
- Una deque de entrada restringida es aquella en la que se puede eliminar desde ambos extremos, pero la inserción se puede realizar en un solo 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 básicos como los más comunes en la informática, las colas y las pilas pueden considerarse especializaciones de deques y pueden implementarse utilizando deques.
Operaciones
Las operaciones básicas en un deque son poner en cola y sacar de cola en cualquier extremo. También se implementan generalmente las operaciones peek , que devuelven el valor en ese extremo sin quitarlo de la cola.
Los nombres varían de un idioma a otro; las principales implementaciones incluyen:
operación | nombres comunes) | Ada | C ++ | Java | Perl | PHP | Pitón | Rubí | Oxido | JavaScript |
---|---|---|---|---|---|---|---|---|---|---|
insertar elemento en la parte posterior | inyectar, snoc, empujar | Append | push_back | offerLast | push | array_push | append | push | push_back | push |
insertar elemento en la parte delantera | empujar, contras | Prepend | push_front | offerFirst | unshift | array_unshift | appendleft | unshift | push_front | unshift |
eliminar el último elemento | expulsar | Delete_Last | pop_back | pollLast | pop | array_pop | pop | pop | pop_back | pop |
eliminar el primer elemento | música pop | Delete_First | pop_front | pollFirst | shift | array_shift | popleft | shift | pop_front | shift |
examinar el último elemento | ojeada | Last_Element | back | peekLast | $array[-1] | end |
| last | back | |
examinar el primer elemento | First_Element | front | peekFirst | $array[0] | reset |
| first | front | |
Implementaciones
Hay al menos dos formas comunes de implementar eficientemente una 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 en tiempo constante , buena localidad de referencia e inserción / eliminación ineficaz 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:
- Almacenar el contenido de deque en un búfer circular y solo cambiar el tamaño cuando el búfer se llena. Esto disminuye la frecuencia de cambios de tamaño.
- Asignar contenido deque desde el centro de la matriz subyacente y cambiar el tamaño de la matriz subyacente cuando se alcanza cualquiera de los extremos. Este enfoque puede requerir cambios de tamaño más frecuentes y desperdiciar más espacio, particularmente cuando los elementos solo se insertan en un extremo.
- Almacenar contenido en varias matrices más pequeñas, asignando 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.
Implementación puramente funcional
Las colas de dos extremos también se pueden implementar como una estructura de datos puramente funcional . [3] 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 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 en el peor momento de una operación es O ( n ) donde n es el número de elementos en la cola de dos extremos.
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 sus primeros i
elementos y los primeros i
elementos de l
, respectivamente. O, si |l| < i
, devuelven la lista vacía y l
respectivamente.
Una cola de dos extremos se representa como un séxtuple lenf, f, sf, lenr, r, sr
donde f
hay una lista enlazada que contiene el frente de la cola de longitud lenf
. De manera similar, r
es una lista enlazada que representa el reverso de la parte posterior de la cola, de longitud lenr
. Además, se asegura que |f| ≤ 2|r|+1
e |r| ≤ 2|f|+1
, intuitivamente, significa que ni la parte delantera ni la trasera contienen más de un tercio de la lista más un elemento. Finalmente, sf
y sr
son colas de f
y de r
, permiten programar el momento en el que se fuerzan algunas operaciones perezosas. Tenga en cuenta que, cuando una cola de dos extremos contiene n
elementos en la lista frontal y n
elementos en la lista posterior, el invariante de desigualdad permanece satisfecho después de las i
inserciones y d
eliminaciones cuando (i+d)/2 ≤ n
. Es decir, como máximo n/2
pueden ocurrir operaciones entre cada reequilibrio.
Intuitivamente, insertar un elemento x
delante de la cola de dos extremos lenf, f, sf, lenr, sr
conduce casi a la cola de dos extremos lenf+1, CONS(x, f), drop(2, sf), lenr, r, drop(2, sr)
, la cabeza y la cola de la cola de dos extremos lenf, CONS(x, f), sf, lenr, r, sr
son x
y casi lenf-1, f, drop(2, sf), lenr, r, drop(2, sr)
respectivamente, y la cabeza y la cola de lenf, NIL, NIL, lenr, CONS(x, NIL), drop(2, sr)
son x
y 0, NIL, NIL, 0, NIL, NIL
respectivamente. La función para insertar un elemento en la parte posterior, o para eliminar el último elemento de la cola de dos extremos, es similar a la función anterior que se ocupa del frente de la cola de dos extremos. Se dice casi porque, después de la inserción y después de una aplicación de tail , el invariante |r| ≤ 2|f|+1
puede dejar de satisfacerse. En este caso, es necesario reequilibrar la cola de dos extremos.
Para evitar una operación con un costos, el algoritmo utiliza la pereza con la memorización y obliga a que el reequilibrio se realice en parte durante las siguientes (|l| + |r|)/2
operaciones, es decir, antes del reequilibrio siguiente. Para crear la programación, se requieren algunas funciones auxiliares diferidas. La función rotateRev(f, r, a)
devuelve la lista f
, seguida de la lista r
y seguida de la lista a
. Se requiere en esta función que |r|-2|f|
sea 2 o 3. Esta función se define por inducción como rotateRev(NIL, r, a)=reverse(r++a)
donde ++ es la operación de concatenación, y por rotateRev(CONS(x, f), r, a)=CONS(x, rotateRev(f, drop(2, r), reverse (take(2, r))++a))
. rotateRev(f, r, NIL)
devuelve la lista f
seguida de la lista r
invertida. La función rotateDrop(f, j, r)
que devuelve f
seguida de ( r
sin j
el primer elemento) invertida también es necesaria, para j < |f|
. Se define por rotateDrop(f, 0, r) == rotateRev(f, r, NIL)
, rotateDrop(f, 1, r) == rotateRev(f, drop(1, r), NIL)
y rotateDrop(CONS(x, f), j, r) == CONS(x, rotateDrop(f, j-2), drop(2, r))
.
La función de equilibrado ahora se puede definir con
fun balance ( q as ( lenf , f , sf , lenr , r , sr )) = si lenf > 2 * lenr + 1 entonces sea val i = ( left + lenr ) div 2 val j = lenf + lenr - i val f ' = tome ( i , f ) val r ' = rotateDrop ( r , i , f ) in ( i , f' , f ' , j , r' , r ' ) de lo contrario, si lenf > 2 * lenr + 1 entonces sea val j = ( lenf + lenr ) div 2 val i = lenf + lenr - j val r ' = take ( i , r ) val f' = rotateDrop ( f , i , r ) in ( i , f ' , f' , j , r ' , r' ) más q
Tenga en cuenta que, sin la parte perezosa de la implementación, esta sería una implementación no persistente de la cola en el tiempo amortizado O (1) . En este caso, las listas y podrían eliminarse de la representación de la cola de dos extremos.sf
sr
Ayuda de idioma
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 vinculada, respectivamente.
La biblioteca de plantillas estándar de C ++ proporciona las plantillas de clase std :: deque y std :: list , para las implementaciones de matrices múltiples y listas vinculadas, respectivamente.
A partir de Java 6, el marco de colecciones de Java proporciona una nueva Deque
interfaz 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
, proporcionando las implementaciones de matriz dinámica y lista vinculada, respectivamente. Sin embargo, ArrayDeque , al contrario de su nombre, no admite el acceso aleatorio.
El prototipo de matriz de Javascript y las matrices de Perl tienen soporte nativo para eliminar ( shift y pop ) y agregar ( unshift y push ) elementos en ambos extremos.
Python 2.4 introdujo el collections
mó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 usar para implementar estructuras de datos Deque. Anteriormente, para hacer una estructura Deque, las funciones de matriz array_shift / unshift / pop / push tenían que usarse en su lugar.
El módulo Data.Sequence de GHC implementa una estructura deque funcional y eficiente en Haskell . La implementación utiliza 2-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 ). [3] [4] Kaplan y Tarjan fueron los primeros en implementar deques catenables óptimos de persistencia confluente. [5] Su implementación fue estrictamente funcional en el sentido de que no utilizó la evaluación perezosa. Okasaki simplificó la estructura de datos utilizando una evaluación perezosa con una estructura de datos de arranque y degradando los límites de rendimiento del peor de los casos a amortizados. Kaplan, Okasaki y Tarjan produjeron una versión amortizada más simple, sin arranque, que se puede implementar usando una evaluación diferida o de manera más eficiente usando la mutación de una manera más amplia pero aún restringida. Mihaesau y Tarjan crearon una implementación más simple (pero aún muy compleja) estrictamente funcional 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.
Rust std::collections
incluye VecDeque, que implementa una cola de dos extremos utilizando un búfer de anillo que se puede crecer.
Complejidad
- En una implementación de lista doblemente enlazada y asumiendo que no hay sobrecarga de asignación / desasignación, la complejidad de tiempo de todas las operaciones deque es O (1) . Además, la complejidad temporal de la inserción o eliminación en el medio, dado un iterador, es O (1); sin embargo, la complejidad temporal del acceso aleatorio por índice es O (n).
- En una matriz creciente, la complejidad de tiempo amortizado de todas las operaciones 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) .
Aplicaciones
Un ejemplo en el que se puede utilizar un deque es el algoritmo de robo de trabajo . [6] 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 hilo, el procesador obtiene el primer elemento del deque (usando la operación deque "eliminar el primer elemento"). Si el hilo actual se bifurca, se vuelve a colocar al frente de la 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 de la deque de otro procesador ("eliminar el último elemento") y ejecuta eso. El algoritmo de robo de trabajo lo utiliza la biblioteca Threading Building Blocks (TBB) de Intel para la programación paralela.
Ver también
- Tubo
- Cola
- Cola de prioridad
Referencias
- ^ Jesse Liberty; Siddhartha Rao; Bradley Jones. C ++ en una hora al día, Sams Teach Yourself , sexta edición. Sams Publishing, 2009. ISBN 0-672-32941-7 . Lección 18: Clases de arreglos dinámicos STL, págs. 486.
- ^ Donald Knuth . El arte de la programación informática , volumen 1: algoritmos fundamentales , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Sección 2.2.1: Pilas, Colas y Deques, págs. 238–243.
- ^ a b Okasaki, Chris (septiembre de 1996). Estructuras de datos puramente funcionales (PDF) (tesis doctoral). Universidad de Carnegie mellon. CMU-CS-96-177.
- ^ Adam L. Buchsbaum y Robert E. Tarjan. Deques de persistencia confluente mediante bootstrapping estructural de datos. Journal of Algorithms, 18 (3): 513–547, mayo de 1995. (págs. 58, 101, 125)
- ^ Haim Kaplan y Robert E. Tarjan. Representaciones puramente funcionales de listas ordenadas que pueden clasificarse. En Simposio ACM sobre Teoría de la Computación, páginas 202–211, mayo de 1996. (págs. 4, 82, 84, 124)
- ^ Blumofe, Robert D .; Leiserson, Charles E. (1999). "Programación de cálculos multiproceso por robo de trabajo" (PDF) . J ACM . 46 (5): 720–748. doi : 10.1145 / 324133.324234 .
enlaces externos
- Implementación de deque de código abierto con seguridad de tipos en Comprehensive C Archive Network
- Documentación SGI STL: deque ,>
- Proyecto de código: un estudio en profundidad del contenedor STL Deque
- Implementación deque en C
- Implementación de VBScript de stack, queue, deque y Red-Black Tree
- Múltiples implementaciones de deques no catenables en Haskell