Hispanopedia Wiki
Articulo de referencia

Cola de doble extremo

\n Input \n Input \n \n \n Output \n Output \n \n \n ''as a queue'' \n ''as a stack'' \n \n{{image label end}}"}},"i":0}}]}"> Aporte Aporte Producción Producción como una cola c...

Hispanopedia WikiContenido en espanolLectura gratuita
Cola de doble extremo como tubería

En informática , una cola de doble extremo (abreviada como deque — / d ɛ k / DEK ) es un tipo de dato abstracto que actúa como contenedor , con acceso restringido a los elementos almacenados. Como generalización tanto de la pila como de la cola , la deque puede tener funciones similares a las de un búfer de datos : puede utilizarse como retenedor (cola) o para retroceso (pila). Sin embargo, ofrece mayor flexibilidad en la gestión del orden de los elementos y algunos algoritmos se basan en sus funcionalidades.

Descripción

La cola de doble extremo se presenta con mayor frecuencia como una cola generalizada, de ahí su nombre. Es una cola que "permite inserciones y eliminaciones en ambos extremos". La deque también se describe como una generalización de la estructura de datos abstracta de pila , como "dos pilas unidas en la base", con un elemento inferior compartido, o como una combinación de la pila y la cola. [ 1 ] [ a ] ​​[ b ] Y, a la inversa, la cola y la pila son formas restringidas de la deque.

Se utilizan diferentes analogías con objetos del mundo real para describir la deque. Se la compara con una "baraja de cartas" con la que comparte algunas propiedades y la pronunciación. [ 3 ] [ 4 ] : 239 [ 5 ] La deque también se compara con un "collar con cuentas que se pueden añadir o quitar por ambos extremos". Al igual que la cola, se representa como un conjunto de elementos alineados en un tubo abierto por ambos extremos; a diferencia de la cola, los elementos pueden moverse en ambas direcciones dentro del tubo. El "modelo ferroviario" introducido por Knuth (en honor a "Dijkstra's shunting yard" ) [ 4 ] : 240 se centra en la similitud con la cola, con una entrada y una salida, y conmutadores para seleccionar el lado de la deque al que se accede. [ 6 ] : 175

Modelo ferroviario de un deque

Se dice que las operaciones principales en una cola doble actúan en cualquiera de los extremos de la estructura: agregar un elemento a la colección ( enqueue ), eliminar un elemento (dequeue ) y leer un elemento ( peek ). En un momento dado, solo se puede acceder a dos elementos desde cualquiera de los extremos de la cola doble, según el historial de la estructura. El elemento designado en un extremo es el último que se ha insertado en ese extremo ( comportamiento LIFO ) o, si no hay ninguno  , el más antiguo que se ha insertado en el otro extremo ( comportamiento FIFO ). Esta política de servicio le da a la estructura mayor flexibilidad y versatilidad, pero también es más difícil de comprender y usar. [ c ]

Las seis operaciones principales en una deque se pueden describir de dos maneras, según las operaciones de la cola (o pila): duplicándolas en cada extremo de la estructura ( add_left, add_right, etc.), o generalizándolas con un parámetro que indica la ubicación donde se realiza una operación ( add(left,...), add(right,...), etc.). Cada enfoque tiene sus ventajas: el primero permite sobrecargar las operaciones, pero requiere nombres diferentes en cada lado, mientras que el segundo simplifica la interfaz al reducir a la mitad el número de operaciones y permite aprovechar la simetría de la estructura. [ 7 ] A continuación, optaremos por la segunda opción para evitar repeticiones innecesarias.

La cola doble tiene otros dos subtipos posibles (las formas más restringidas son inútiles):

  • Una cola doblemente extendida (deque) con restricción de entrada es aquella en la que se puede eliminar un elemento desde cualquiera de sus extremos, pero solo se puede insertar uno. Es una cola con una salida hacia atrás, o una pila con una salida hacia abajo.
  • Una cola de doble extremo con restricción de salida es aquella en la que se pueden realizar inserciones en ambos extremos, pero solo eliminaciones en uno. Es una cola con entrada frontal o una pila con entrada inferior.

A pesar de sus limitaciones, estos subtipos tienen muchas aplicaciones y algunas de sus implementaciones pueden ser más sencillas.

Según Knuth, [ 4 ] estas estructuras se describen a menudo como diferentes formas de listas lineales restringidas o secuencias . Mantienen los elementos contenidos en un orden determinado, pero solo permiten el acceso a algunos de ellos: el primero y/o el último de la secuencia. Sin embargo, otros autores objetan que «ocultan su dinamismo interno al usuario» [ 2 ] : 139 y que solo las implementaciones comunes son lineales. Consideran que estas estructuras de datos de acceso restringido son:

  • semiestructuradas : tienen "un elemento especial o designado, pero ninguna relación lógica entre el resto de los elementos", y "la operación que elimina un elemento no toma ningún elemento como parámetro"; [ 8 ] : xiii, 189
  • o estructuras de puntos "porque solo existen dos puntos de una cola para el mundo exterior" [ 2 ] : 129 : la pila es entonces una estructura de un punto, mientras que la cola y la deque son estructuras de dos puntos.

Por ejemplo, una deque puede implementarse con un montón min-max o con un conjunto : antes de insertar un elemento, se le asigna una etiqueta con un entero que se utiliza como su valor en el montón, y que depende del historial del contenedor. [ 8 ] : A1 Los elementos almacenados en un montón no están ordenados y sus ubicaciones dependen del estado interno de la estructura. Otra estructura común de acceso restringido es la cola de prioridad , que no es una estructura lineal.

La deque se puede generalizar mediante la adición de algunas operaciones: una deque con orden de montón, o mindeque , permite la operación find-min . También es posible una concatenación rápida o incluso óptima. [ 9 ] : 276 [ 10 ] [ 11 ]

Algunos autores consideran que la estructura deque doble es de poca utilidad, menos útil que sus formas restringidas, especialmente la pila y la cola. [ 1 ] [ 2 ] [ 9 ] [ d ]

  1. ↑ "Es un misterio por qué no se le llama pila doble, ya que esa es al menos una descripción igual de precisa", [ 2 ] : 131
  2. ↑ La deque puede entonces verse "como una supercola o una superpila". [ 1 ]
  3. ↑ "Si se insertan dos nodos en un extremo y se eliminan del otro, saldrán en orden de cola. Si ambos se eliminan del extremo de entrada, saldrán en orden de pila. Si se eliminan de extremos opuestos, su orden de salida será aleatorio." [ 2 ] : 131
  4. ↑ "¡una estructura de datos que busca una aplicación!", citado por Roy S. Ellzey en 1989. [ 12 ]

Especificación

Aquí, la cola doble se considera ilimitada: puede contener un número ilimitado (e indefinido) de elementos. Es posible una cola doble limitada, que requiere una especificación ligeramente diferente, pero cuando se produce un desbordamiento, el comportamiento depende de la implementación: valor de error, excepción, eliminación, etc.

Sea una cola doble d ∈ D , un elemento x ∈ X y un lado (extremo) e ∈ E = {izquierda, derecha} con ¬ izquierda = derecha

   Operaciones clave: con D * = D \ {Λ}

Como estructura lineal, la deque se puede especificar en términos de concatenación (denotada " ~ ") de secuencias y secuencias únicas (denotadas " < ... > ").

Se puede obtener una especificación axiomática (o algebraica ) de la deque extendiendo y fusionando las de la pila y la cola. [ 13 ] [ 14 ] [ 15 ] (véase la tesis de Nguyen para una formulación alternativa [ 16 ] ).

   Restricciones axiomáticas:

  • como una pila:
  • como una cola, ∀ d ≠ Λ :

La secuencia de operaciones del ejemplo anterior da como resultado la siguiente expresión:

d = eliminar ( derecha, agregar ( izquierda, DE, eliminar ( izquierda, eliminar ( izquierda, agregar ( derecha, UE, agregar ( derecha, QUE, agregar ( izquierda, STA, eliminar ( izquierda, agregar ( derecha, CK, agregar ( izquierda, DE,Λ) ))))))))))

Esto se puede simplificar con los axiomas ( 1 ) , ( 2 ) y ( 3 ) . En orden de aplicación, desde la cola doble vacía:

Esto da como resultado la siguiente expresión:

d = sumar (izquierda, DE, sumar (derecha, QUE,Λ))

Como una transformación a partir de una secuencia vacía  :

< > agregar (derecha, QUE) ⟼ < QUE> agregar (izquierda, DE) ⟼ < DE, QUE>

Por el contrario, la pila y la cola se pueden especificar axiomáticamente en términos de la deque.

Especificación heredada de la pila

   Sea una pila s ∈ S ⊂ D

Operaciones:
Axiomas:
Especificación heredada de la cola

   Sea una cola q ∈ Q ⊂ D

Operaciones:
Axiomas:

Terminología

El término deque ( / d ɛ k / DEK ) se utiliza como abreviatura de Double -Ended QUE ue ( cola de doble extremo ). A veces se usa Dequeue , pero puede resultar confuso, ya que el término también se utiliza para la operación de eliminar un elemento de la deque. Una deque también puede denominarse lista enlazada cabeza-cola , aunque propiamente dicho se refiere a una implementación específica . Una deque con restricción de salida puede designarse como steque (por stack-ended queue, cola de extremo de pila). [ 17 ] : 53

No existe un vocabulario estándar asociado a las deque. Los términos «enqueue» y «dequeue» , tomados de la estructura de cola, generalmente denotan las operaciones básicas en una deque, en cualquiera de sus extremos. Sin embargo, los artículos y las implementaciones reales suelen usar nombres diferentes. Los nombres de las operaciones varían según el contexto, el autor, la implementación o el lenguaje de programación.

  • en analogía con una cola: encolar y desencolar , o empujar y tirar ;
  • En analogía con una pila: se insertan y extraen elementos de un lado, y posiblemente se inyectan y expulsan elementos del otro lado;
  • En analogía con una lista: cons y uncons en un lado, snoc y unsnoc en el otro lado;
  • En analogía con una matriz: agregar en un lado, anteponer en el otro lado, o desplazar y desplazar .

A diferencia de las estructuras de datos asociadas, la cola doble es simétrica. Sus lados pueden nombrarse libremente según el contexto:

  • en analogía con una cola: delante y detrás ;
  • en analogía con una pila: arriba y abajo ;
  • en analogía con una lista: cabeza o último ;
  • en analogía con una matriz: primero y final , o primero y último ;
  • Finalmente, tanto a la izquierda como a la derecha se conserva la simetría original de la estructura.

El nombre completo de una operación puede ser una combinación del nombre de la operación básica y el nombre de la operación secundaria: por ejemplo, push_front y pop_back . En un mismo contexto, pueden asociarse términos de diferentes analogías: append y pop , push y shift , o front y tail . Finalmente, algunos lenguajes de programación utilizan incluso nombres distintos según la estructura de datos subyacente.

También se suelen implementar las operaciones de "mirar" (peek) , que devuelven el valor de un extremo sin extraerlo de la cola. A menudo se nombran según el lado de destino: por ejemplo, ` top` es el valor del elemento en la parte superior de la cola doble. En el contexto de la programación funcional, no se utiliza la operación de extracción (que devuelve dos valores: el elemento eliminado y la nueva cola doble). Se reemplaza por una función de "mirar" (es decir, ` head` y `last` ) y una función que devuelve la cola doble sin el final, es decir, ` tail` e ` init` .

Implementaciones

Existen al menos dos métodos comunes para implementar eficientemente una cola de doble extremo (deque), que a menudo se contraponen : mediante una lista doblemente enlazada o mediante un arreglo dinámico modificado. Hay muchas variantes y las implementaciones reales suelen ser soluciones híbridas. Además, existen varias implementaciones puramente funcionales de la cola de doble extremo.

Lista doblemente enlazada

Si bien una lista simple puede implementar una cola doblemente enlazada (deque), una lista doblemente enlazada es más adecuada por su simetría para lograr un acceso rápido a ambos extremos de la lista ( cabeza y cola , de ahí el nombre de lista enlazada cabeza-cola ). La solución obvia es gestionar dos referencias; alternativamente, la deque puede construirse como una lista circular.

Una lista doblemente enlazada cuyos nodos contienen tres campos: un valor entero, el enlace al siguiente nodo y el enlace al nodo anterior.
Una lista doblemente enlazada cuyos nodos contienen tres campos: el enlace al nodo anterior, un valor de elemento y el enlace al nodo siguiente.

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 la cola doblemente enlazada es O(1) . Además, la inserción o eliminación en el medio, dado un iterador, también se puede lograr en tiempo constante; sin embargo, el tiempo que toma el acceso aleatorio por índice es O(n) . De manera similar, encontrar un elemento específico normalmente requiere un tiempo de O(n) . Las estructuras de datos enlazadas generalmente tienen una localidad de referencia deficiente.

Matriz dinámica

Se insertan varios valores al final de una matriz dinámica mediante expansión geométrica. Las celdas grises indican el espacio reservado para la expansión. La mayoría de las inserciones son rápidas ( tiempo constante ), mientras que algunas son lentas debido a la necesidad de reasignación ( tiempo Θ( n ) , etiquetado con tortugas).

En este caso también, si bien se puede usar un arreglo dinámico para implementar una deque, una variante que pueda crecer desde ambos extremos es más apropiada. A esto a veces se le llama deque de arreglo . Esto se puede lograr de varias maneras, por ejemplo:

  • Al desplazar la posición del primer elemento de la matriz en la memoria reservada, el espacio no utilizado se distribuye a ambos lados de los datos;
  • con una disposición circular .

La complejidad temporal amortizada de todas las operaciones de deque con un deque de array es O(1) , gracias a la expansión geométrica del búfer de back-end. Además, el acceso aleatorio por índice toma un tiempo constante  ; pero el tiempo promedio que se toma para la inserción o eliminación en el medio es O(n) . Gracias al rápido acceso aleatorio, encontrar un elemento en un array ordenado es un tiempo O(log n) ( búsqueda binaria ). Cada vez que se redimensiona el array, se mueve todo el contenido: el uso de memoria se duplica momentáneamente (o más), y se pierden todas las referencias directas (externas) al contenido del array.

Implementaciones funcionales y persistentes

Las listas doblemente enlazadas no pueden utilizarse como estructuras de datos inmutables . Además, un array inmutable sería muy ineficiente (un array suele simularse mediante un árbol ). Una implementación puramente funcional de la cola doblemente enlazada puede basarse en una pila, que se implementa fácilmente con una lista simplemente enlazada como estructura inmutable y persistente .

Existen varios trabajos en la literatura que abordan este problema. Todos ellos utilizan dos ideas clave. La primera es que una cola doble (deque) puede representarse mediante un par de pilas, una que representa la parte frontal de la cola y la otra la parte posterior. Cuando un lado queda vacío debido a demasiadas operaciones de extracción o expulsión , la cola, ahora en una sola pila, se copia en dos pilas, cada una con la mitad de los elementos. Esta división equitativa garantiza que dicha copia, aunque costosa, ocurra con poca frecuencia. Un sencillo argumento de amortización muestra que esto proporciona una simulación en tiempo lineal de una cola doble mediante un número constante de pilas: k operaciones de cola doble, partiendo de una cola doble vacía, se simulan con O(k) operaciones de pila. [...] La segunda idea consiste en utilizar la copia incremental para convertir esta simulación en tiempo lineal en una simulación en tiempo real: tan pronto como las dos pilas se desequilibran lo suficiente, comienza la copia para crear dos pilas equilibradas.

— Kaplan, Haim; Tarjan, Robert E. (1995). "Listas persistentes con concatenación mediante ralentización recursiva". Actas del 27.º simposio anual de la ACM sobre teoría de la computación . Las Vegas, Nevada. pp. 93–102 . doi : 10.1145/225058.225090 .  (versión preliminar de [ 18 ] )

Este último proceso podría ser bastante complicado, ya que necesita ejecutarse concurrentemente con otras operaciones y completarse antes de la siguiente, para lograr una complejidad de tiempo real amortizada. El siguiente paso es admitir las operaciones en un tiempo de peor caso O(1) . Otro desafío es la concatenación en tiempo real de deques. Okasaki da una solución simple que usa listas perezosas combinadas con memorización . El balanceo de pila a pila es entonces parcialmente automático por medio de una programación precisa de funciones incrementales. [ 17 ] : 52−59 : 115 Sin embargo, algunos autores consideran que dicho algoritmo no es puramente funcional ya que la memorización se considera un efecto secundario . [ 18 ] : 581 Kaplan y Tarjan dan su propia versión del deque puramente funcional (no concatenable), basado en tres ideas: [ 18 ]

  • arranque de la estructura de datos , que da como resultado una estructura recursiva que prevé el árbol de dedos : una deque es una tripleta que consiste en una subdeque flanqueada por dos búferes de tamaño limitado. Enqueue y dequeue operan básicamente en los búferes (en tiempo real debido al tamaño limitado) y avanzan un paso en el proceso de equilibrio;
  • Ralentización recursiva , inspirada en la representación binaria redundante (RBR), donde un dígito adicional 2representa un acarreo suspendido: la sub-deque contiene pares de elementos de la deque padre, y la propagación del proceso de balanceo a la sub-deque se retrasa como la propagación del acarreo después del incremento o decremento de un número RBR; [ 17 ] : 105
  • y una modificación de la estructura principal de la estructura en forma de árbol de dedos (una pila) en una pila de pilas que puede considerarse como una lista de salto de 2 niveles . Esto permite un acceso en tiempo real a las sub-deques desequilibradas. De forma análoga a un RBR, las subpilas representan bloques contiguos de 1dígitos, que pueden saltarse para acceder al siguiente 2, es decir, un acarreo suspendido.

En este artículo, Kaplan y Tarjan también presentan una versión aún más compleja que logra la concatenación en tiempo real. Sin embargo, esta descripción es principalmente textual. J. Viennot, A. Wendling, A. Guéneau y F. Pottier publican una implementación verificada de esta estructura de datos (en OCaml y Rocq ), junto con una descripción formal y un análisis detallado del algoritmo. [ 19 ]

En términos más generales, la concatenación en tiempo real requiere que una deque sea una tupla que consta principalmente de dos subestructuras, que a su vez contienen deques o compuestos de deques. La columna lineal de la deque no concatenable se reemplaza entonces por un esqueleto binario .

Kaplan, Okasaki y Tarjan produjeron una versión amortizada más simple que puede implementarse usando evaluación perezosa o de manera más eficiente usando mutación de una forma más amplia pero aún restringida. [ 20 ] Mihaescu y Tarjan crearon una implementación estrictamente funcional más simple (pero aún muy compleja) de deques concatenables, y también una implementación mucho más simple de deques no concatenables estrictamente funcionales, ambas con límites óptimos en el peor caso (no publicados oficialmente). [ 21 ]

Soporte de idiomas

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.

Diagrama de clases UML de una cola de doble extremo
Diagrama de clases UML de una cola de doble extremo

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 enlazadas, respectivamente.

A partir de Java 6, el marco de colecciones de Java proporciona una nueva Dequeinterfaz que ofrece 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 las implementaciones de arreglos dinámicos y listas enlazadas, respectivamente. Sin embargo, la ArrayDeque, contrariamente a lo que sugiere su nombre, no admite acceso aleatorio.

El prototipo Array de JavaScript y los arrays 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 utilizando una lista doblemente enlazada de submatrices de longitud fija.

A partir de PHP 5.3, la extensión SPL de PHP incluye la clase 'SplDoublyLinkedList', que permite implementar estructuras de datos Deque. Anteriormente, para crear una estructura Deque, era necesario utilizar las funciones array_shift/unshift/pop/push.

El módulo Data.Sequence de GHC implementa una estructura de deque eficiente y funcional en Haskell . La implementación utiliza 2 o 3 árboles de dedos anotados con tamaños.

Rust std::collectionsincluye VecDeque , que implementa una cola de doble extremo utilizando un búfer circular de tamaño variable.

Aplicaciones

R DELQUE.(J) - ELIMINA AL USUARIO J DE LAS COLAS R ENDQUE.(J) - COLOCA AL USUARIO J AL FINAL DE LA COLA NIVEL(J) R BEGQUE.(J) - COLOCA AL USUARIO J AL PRINCIPIO DE LA COLA DE NIVEL(J)

En 1965, incluso antes de que se le diera nombre a la cola doble (deque) , un fragmento de código de las notas técnicas de CTSS describe tres subrutinas que manipulan las colas de "usuarios". Solo se ejecutan las dos primeras subrutinas, pero la idea de una cola menos restringida está presente y codificada en una biblioteca. [ 22 ]

Una cola de doble extremo siempre puede sustituir a una cola o a una pila. Por lo tanto, las aplicaciones prácticas de la cola de doble extremo suelen ser versiones extendidas de algoritmos basados ​​en pilas o colas. De hecho, muchas aplicaciones solo necesitan una cola de doble extremo con restricción de salida o (más raramente) de entrada. Aquí solo se enumeran las aplicaciones prácticas que se basan de forma óptima en una cola de doble extremo estricta, es decir, que solo necesitan acceder a los elementos de ambos extremos uno a uno.

Cola monótona

Una cola doblemente extendida (deque) con restricción de entrada se puede usar para construir una cola monótona , es decir, una subsecuencia cuyos elementos están en un orden dado, ya sea creciente o decreciente. Dada una secuencia, el algoritmo solo conserva los elementos en el orden deseado y descarta los demás. El orden de los elementos se preserva. Para construir una secuencia monótona creciente (o decreciente), solo se utilizan operaciones de pila.

  • Comience con una cola doble vacía,
  • Para cada elemento de la secuencia de entrada:
    • Mientras el último elemento de la cola doble sea mayor (o menor) que el elemento actual, elimínelo.
    • Empuja el elemento actual a la cola doble.
std :: deque <int> increase_monotonic_queue ( std :: vector <int> & seq [ ] ) { std :: deque <int> q ; for ( std :: size_t i = 0 ; i < seq.size ( ) ; i ++ ) { while ( ! q.empty ( ) && q.back ( ) > seq [ i ] ) q.pop_back ( ) ; q.push_back ( seq [ i ] ) ; } return q ; }​​​​​

Los elementos de la secuencia monótona se pueden extraer de la otra cola (de ahí el uso de una cola doble).

Se puede utilizar una cola monótona para encontrar el valor mínimo o máximo en una ventana deslizante sobre una secuencia con una complejidad temporal lineal. [ 23 ] La complejidad de una solución ingenua es O(nk) en tiempo y O(1) en espacio, donde n es la longitud de la secuencia de entrada y k el tamaño de la ventana. Una solución que utiliza algún método de búsqueda tiene una complejidad temporal de O(n.log n) y O(n) en espacio.

En el siguiente código, la cola monótona almacena referencias a los elementos de la secuencia.

#incluye <vector> #incluye <deque>typedef std :: vector < int >:: const_iterator seq_iterator ; typedef std :: deque < seq_iterator > monotonic_queue ;monotonic_queue & decreasing_monotonic_queue_push ( monotonic_queue & q , seq_iterator i ) { while ( ! q . empty () && * q . back () < * i ) q . pop_back (); q . push_back ( i ); return q ; }std :: vector <int> max_of_subarrays ( std :: vector <int> & seq , std :: size_t win_sz ) { std :: vector <int> max_of_sub ; monotonic_queue decreasing ; seq_iterator i = seq.begin ( ) ; // escanear la primera ventana for ( size_t win_i = 0 ; i < seq.end ( ) && win_i < win_sz ; i ++ , win_i ++ ) decreasing_monotonic_queue_push ( decreasing , i ) ; max_of_sub.push_back ( * decreasing.front ( ) ) ; // escanear el resto de la secuencia for ( / * mantener i * / ; i < seq.end ( ) ; i ++ ) { if ( decreasing.front ( ) < = i - win_sz ) decreasing . pop_front ( ); // sale del ámbito decreasing_monotonic_queue_push ( decreasing , i ); max_of_sub.push_back ( * decreasing.front ( ) ) ; } return max_of_sub ; }

Cada elemento de la secuencia de entrada se inserta y se extrae como máximo una vez, lo que resulta en 2.n operaciones. La complejidad temporal es entonces O(n) . La complejidad espacial es O(k) , el tamaño máximo de la cola doble.

De manera similar, una cola monótona permite la optimización de algunos casos de programación dinámica equivalentes al problema de la subsecuencia de menor peso  : problema de la ruta más corta para un grafo dirigido ponderado, salto de párrafo , etc. Se dice que estos problemas son convexos o cóncavos , y por lo tanto monótonos . La complejidad temporal se reduce entonces de O(n² ) a O (n·log n) , y O(n) en situaciones propicias. [ 24 ] [ 25 ]

Otra aplicación directa de la cola monótona es la cola mínima o minqueue . En este caso, la cantidad de elementos en la ventana varía. La minqueue es una estructura de datos con una interfaz de cola que, además, proporciona acceso directo al elemento mínimo almacenado. Las operaciones clave son entonces enqueue , dequeue y find min . A pesar de que el nombre alude al montón (min/max) , la min/max-queue no es una cola de prioridad : el orden de los elementos se mantiene desde la entrada hasta la salida (política FIFO). Una versión simple de una min-queue con tiempo amortizado O(1) es una cola normal combinada con una cola monótona creciente auxiliar, que proporciona el elemento mínimo en su frente. La adición de un elemento se aplica a ambas colas, y cuando el elemento mínimo se desencola de la cola normal (es decir, el mismo elemento frontal), también se desencola de la cola monótona. [ 9 ]

Envolvente convexa de una polilínea simple

El algoritmo de Melkman calcula la envoltura convexa de una cadena poligonal simple (o un polígono simple ) en tiempo lineal. La principal diferencia con otros algoritmos similares es que Melkman requiere que se agreguen o eliminen vértices en ambos extremos de la cadena que forma la envoltura. De ahí el uso de una cola doble (deque). El algoritmo calcula la posición de cada nuevo vértice con respecto al primer y último segmento (dos vértices cada uno) de la cadena de la envoltura (almacenada en la cola doble). El vértice se ignora o se agrega (encola) a ambos lados de la cola doble (la envoltura es un bucle), después de eliminar (desencolar) algunos vértices anteriores que ahora se encuentran en el lado interior de la envoltura. [ 26 ] [ 27 ] [ 28 ]

from collections import dequedef posición ( A , B , C ): det = ( B . X - A . X ) * ( C . Y - A . Y ) - ( B . Y - A . Y ) * ( C . X - A . X ) if det > 0 : return 1 # C está a la izquierda de la línea AB elif det < 0 : return 0 # C está a la derecha de la línea AB else : return - 1 # AB y C son colinealesdef melkman ( ruta ): si posición ( ruta [ 0 ], ruta [ 1 ], ruta [ 2 ]) == 1 : casco = deque ([ ruta [ 2 ], ruta [ 0 ], ruta [ 1 ], ruta [ 2 ]]) de lo contrario : casco = deque ([ ruta [ 2 ], ruta [ 1 ], ruta [ 0 ], ruta [ 2 ]]) para v en ruta [ 3 :] : si posición ( casco [ 0 ], casco [ 1 ], v ) == 1 y posición ( casco [ - 2 ], casco [ - 1 ], v ) == 1 : continuar mientras posición ( casco [ 0 ], casco [ 1 ], v ) <= 0 : casco . popleft () casco . agregar a la izquierda ( 0 , v ) mientras posición ( casco [ -2 ] , casco [ -1 ] , v ) < = 0 : casco.pop ( ) casco.append ( v ) devolver casco

Cola de prioridad simple

Las pilas y las colas pueden considerarse como tipos particulares de colas de prioridad , donde la prioridad está determinada por el orden en que se insertan los elementos. De manera similar, una cola doble (deque) puede implementar una cola de prioridad con dos niveles: los elementos de alta prioridad se agregan al frente de la cola doble, mientras que los de baja prioridad se agregan al final. [ 1 ] A menos que un elemento pueda cancelarse o robarse y luego expulsarse desde el fondo, una cola doble con restricción de salida es suficiente.

De este modo, es posible modificar el algoritmo estándar de Dijkstra para encontrar el camino más corto desde un único origen en un grafo con aristas de coste 0 y coste 1. Una cola doble sustituye a la cola de prioridad mínima . Los elementos de coste 0 se encolan delante de la cola doble (alta prioridad) y siempre se procesan antes que los elementos de mayor coste (baja prioridad) que se encolan al final.

Una cola doble (deque) se utiliza en el algoritmo de robo de trabajo . [ 29 ] Este algoritmo implementa la planificación de tareas para varios procesadores. Se mantiene una cola doble independiente con los hilos que se ejecutarán para cada procesador. Para ejecutar el siguiente hilo, el procesador obtiene el primer elemento de la cola doble (mediante la operación "eliminar el primer elemento"). Si el hilo actual se bifurca, se vuelve a colocar al principio de la cola doble ("insertar elemento al principio") y se ejecuta un nuevo hilo. Cuando uno de los procesadores termina la ejecución de sus propios hilos (es decir, su cola doble está vacía), puede "robar" un hilo de otro procesador: obtiene el último elemento de la cola doble 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.

Autómata de Deque

Un autómata de cola doble (AD) es una máquina de estados finitos equipada con una memoria auxiliar de cola doble. Generaliza el autómata de pila (AP) y el autómata de cola (autómata de elevación, AEL). Como tal, es equivalente a una máquina de Turing y, por lo tanto, puede procesar la misma clase de lenguajes formales . Pero a diferencia del AP y el AEL, que imponen la serialización, un autómata de cola doble permite la ejecución paralela o intercalada de algunas operaciones. [ 30 ]

Véase también

Referencias

  1. 1 2 3 4 Lewis, TG (Theodore Gyle) (1976). Aplicación de estructuras de datos . Houghton Mifflin. pág. 56. ISBN  9780395240601.
  2. 1 2 3 4 5 Amsbury, Wayne. Estructuras de datos : de matrices a colas de prioridad . Wadsworth. ISBN  9780534045906.
  3. ↑ Thomas, Pete; Robinson, Hugh; Emms, Judy (1988). Tipos de datos abstractos: su especificación, representación y uso . Serie de matemáticas aplicadas y ciencias de la computación de Oxford. Oxford : Nueva York: Clarendon Press ; Oxford University Press. pág. 142. ISBN    978-0-19-859663-9.
  4. 1 2 3 Knuth, Donald Ervin (1997). El arte de la programación informática . Vol. 1: Algoritmos fundamentales (3.ª ed.). Reading, Mass: Addison-Wesley. Sección 2.2.1: Pilas, colas y deques. ISBN   0-201-89683-4.
  5. ↑ 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 matrices dinámicas de STL, pág. 486.
  6. ↑ Smith, Harry F. (1987). Estructuras de datos : forma y función . Harcourt Brace Jovanovich. ISBN  9780155168206.
  7. ↑ Booch, Grady (1987). Componentes de software con Ada: estructuras, herramientas y subsistemas . Menlo Park, California: Benjamin/Cummings Pub. Co. Capítulo 7. ISBN 978-0-8053-0610-1.
  8. 1 2 Dale, Nell ; Walker, Henry M. (1996). Tipos de datos abstractos: especificaciones, implementaciones y aplicaciones . Jones & Bartlett Learning. ISBN 978-0-66940000-7.
  9. 1 2 3 Brass, Peter (2008). Estructuras de datos avanzadas . Cambridge University Press. pág. 272. ISBN  978-1-108-73551-3.
  10. ↑ Gajewska, Hania; Tarjan, Robert E. (1986). "Deques con orden de montículo" . Information Processing Letters . 22 (4): 197– 200. doi : 10.1016/0020-0190(86)90028-1 . Recuperado el 28 de febrero de 2026 .
  11. ↑ Buchsbaum, Adam L.; Sundar, Rajamani; Tarjan, Robert E. (1995). "Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues" . SIAM Journal on Computing . 24 (6): 1190– 1206. doi : 10.1137/S0097539792242144 . ISSN 0097-5397 . Recuperado el 28 de febrero de 2026 . 
  12. ↑ Ellzey, Roy S. (1991). Estructuras de datos para sistemas de información informática (2.ª ed.). Nueva York: Macmillan. ISBN  978-0-574-18740-6.
  13. ↑ Centro de Información Técnica de Defensa (1989-08-01). DTIC ADA218855: Verificación automática de la coherencia en tiempo de ejecución y depuración de programas especificados formalmente . págs. 6–7 . 
  14. ↑ Centro de Información Técnica de Defensa (1991-10-01). DTIC ADA311117: Especificación del paquete Anna: Estudios de caso . pág. 41. 
  15. ↑ Louden, Kenneth C. (1995). Lenguajes de programación: principios y práctica . Serie PWS-KENT en ciencias de la computación (3.ª ed. [impresa]). Boston, MA: PWS. ISBN  978-0-534-93277-0.
  16. ↑ Nguyen, Doan Han (diciembre de 1995). Un modelo arquitectónico para la búsqueda de componentes de software (Tesis). Monterey, California. Naval Postgraduate School. págs. 108–109 . 
  17. 1 2 3 Okasaki, Chris (septiembre de 1996). Estructuras de datos puramente funcionales (PDF) (tesis doctoral). Universidad Carnegie Mellon. CMU-CS-96-177.
  18. 1 2 3 Kaplan, Haim; Tarjan, Robert E. (1999). "Deques puramente funcionales en tiempo real con concatenación" . Journal of the ACM . 46 (5): 577– 603. doi : 10.1145/324133.324139 .
  19. ^ Viena, Jules; Wendling, Arturo; Guéneau, Armaël; Pottier, François (12 de mayo de 2025). "Deques en tiempo real catenables puramente funcionales verificados". arXiv : 2505.07681 [ cs.PL ].
  20. ↑ Kaplan, Haim; Okasaki, Chris; Tarjan, Robert E. (2000). "Simple Confluently Persistent Catenable Lists" (PS) . SIAM Journal on Computing . 30 (3): 965– 977. doi : 10.1137/S0097539798339430 . Archivado del original el 25 de septiembre de 2010.
  21. ↑ Mihaescu, Radu; Tarjan, Robert (agosto de 2003), "Notas sobre Deques concatenables en Pure Lisp" , Ciencias de la Computación 528 Estructuras de datos y algoritmos de grafos , Ciencias de la Computación (material del curso), Universidad de Princeton, archivado del original (DOC) el 17 de septiembre de 2006.
  22. ↑ Saltzer, Jerome H. (1965-03-15). "Notas técnicas de CTSS" . DSpace@MIT Home . págs. 40–41 . Recuperado el 28 de febrero de 2026 . 
  23. ↑ "Máximo de ventana deslizante" . GeeksForGeeks . 27 de mayo de 2011. Archivado del original el 3 de agosto de 2025.
  24. ↑ Yi, Richard. "1D1D DP: Optimización de programación dinámica" . Archivado del original el 16 de enero de 2024.
  25. ↑ Hirschberg, Daniel S.; Larmore, Lawrence L. (1985), El problema de la subsecuencia de menor peso , UC Irvine: Escuela de Ciencias de la Información e Informática Donald Bren{{citation}}: CS1 mantenimiento: ubicación del editor ( enlace )
  26. ↑ Melkman, Avraham A. (1987). "Construcción en línea de la envoltura convexa de una polilínea simple" . Information Processing Letters . 25 (1): 11– 12. doi : 10.1016/0020-0190(87)90086-X . MR 0896397 . 
  27. ↑ Li, Fajie; Klette, Reinhard (2011). "Envolventes convexas en el plano". Caminos euclidianos más cortos . Londres: Springer London. doi : 10.1007/978-1-4471-2256-2_4 . ISBN 978-1-4471-2255-5. Consultado el 10 de febrero de 2026 .
  28. ↑ Aloupis, Greg. "Historia de algoritmos de envolvente convexa en tiempo lineal para polígonos simples" . Laboratorio de Geometría Computacional de McGill . Universidad McGill . Consultado el 10 de febrero de 2026 .
  29. ↑ Blumofe, Robert D.; Leiserson, Charles E. (1999). "Programación de cálculos multihilo mediante robo de trabajo". J ACM . 46 (5): 720– 748. doi : 10.1145/324133.324234 . S2CID 5428476 . 
  30. ↑ Crespi-Reghizzi, Stefano; San Pietro, Pierluigi (2020). "Autómatas de deque, lenguajes y representaciones de grafos planares". Theoretical Computer Science . 834 : 43–59 . doi : 10.1016/j.tcs.2020.02.029 .
  • Implementación de deque de código abierto con tipado seguro en Comprehensive C Archive Network.
  • Documentación SGI STL: 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 en VBScript de pila, cola, doble cola y árbol rojo-negro
  • Múltiples implementaciones de deques no concatenables en Haskell