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.