Deque

En Informática, un deque (generalmente pronunciado como un mazo, es la abreviatura de cola de doble extremo) es una estructura de datos abstracta similar a una lista, también llamada lista concatenada de cabeza-cola porque los elementos solo se pueden agregar o eliminar de la cabeza o cola.

Deque a veces se escribe dequeue, pero esta práctica generalmente se desaconseja en la literatura técnica ya que dequeue es también un verbo inglés que significa "quitar de una cola" . A pesar de esto, algunos autores como Aho, Hopcroft y Ullman en su libro Estructuras de datos y algoritmos, usan la palabra dequeue . Además, DEQ y DQ también se usan para denotar un deque.

Esta estructura de datos difiere de una cola FIFO normal en la que los elementos solo se pueden agregar en un lado y eliminar en el otro. Algunos de los posibles subtipos de esta estructura de datos son: tanto las estructuras de datos más comunes y fundamentales en la informática, la cola y la pila pueden considerarse deques especiales, y por lo tanto son implementables usando un deque.

Una deque soporta las siguientes operaciones:

Hay al menos dos formas de implementar eficientemente un deque: a través de una matriz dinámica modificada o a través de una lista doblemente concatenada. El deque a menudo se implementa utilizando una variante de la matriz dinámica que puede aumentar su capacidad en ambos lados y también se llama la matriz deque. Tienen todas las propiedades de las matrices dinámicas, como el tiempo de acceso constante arbitrario, la buena ubicación y las inserciones y eliminaciones de centro ineficientes con la adición de inserciones y eliminaciones con tiempo amortizado constante en ambos lados, en lugar de en un solo lado. Dos implementaciones comunes son: .

La biblioteca de plantillas estándar de C ++ ofrece la clase std::deque y la clase std::list para implementar matrices dinámicas y lista concatenada, respectivamente. Java 6 ofrece una nueva interfaz Deque que permite la inserción y extracción en ambos lados. Se implementa mediante clases como ArrayDeque (también introducido en Java 6) y LinkedList que proporcionan las implementaciones de la matriz dinámica y la lista concatenada, respectivamente. Acerca de nosotros 4 introdujo el módulo de colecciones con soporte para objetos deque. Nivel de Cifrado WEP 3, la extensión SPL contiene la clase ''SplDoublyLinkedList'' que se puede usar para implementar un deque.

Estructuras de datos

Cola de prioridades

En la teoría de colas, una cola de prioridad es una estructura de datos abstracta, similar a una cola o una pila, pero diferente de estas en que cada elemento i...

Coda (informática)

En Ciencias de la Computación, la cola es una estructura de datos de tipo FIFO, f irst i n f irst o ut (la primera entrada es la primera salida). Un ejemplo prá...

Stub-programación

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad