Deque | Conjunto 1 (Introducción y Aplicaciones)

Deque o Double Ended Queue es una versión generalizada de la estructura de datos de Queue que permite insertar y eliminar en ambos extremos.

Operaciones en Deque: Principalmente, las siguientes cuatro operaciones básicas se realizan en la cola:
insertFront() : Agrega un elemento al frente de Deque.
insertLast() : agrega un elemento en la parte posterior de Deque.
deleteFront() : Elimina un elemento del frente de Deque.
deleteLast() : Elimina un elemento de la parte posterior de Deque. Además de las operaciones anteriores, también se admiten las siguientes operaciones.
getFront() : Obtiene el elemento frontal de la cola.
getRear() : Obtiene el último elemento de la cola.
isEmpty() : Comprueba si Deque está vacío o no.
isFull() : Comprueba si Deque está lleno o no.

Aplicaciones de Deque: dado que Deque admite operaciones de pila y cola, se puede usar como ambas. La estructura de datos de Deque admite rotaciones en el sentido de las agujas del reloj y en el sentido contrario a las agujas del reloj en tiempo O(1), lo que puede ser útil en determinadas aplicaciones. Además, los problemas en los que es necesario eliminar o agregar elementos en ambos extremos se pueden resolver de manera eficiente con Deque. Por ejemplo, vea el problema Máximo de todos los subarreglos de tamaño k. , 0-1 BFS y Encuentre el primer recorrido circular que visita todas las bombas de gasolina . Consulte la página wiki para ver otro ejemplo del algoritmo de programación de trabajos A-Steal donde se usa Deque ya que se requiere una operación de eliminación en ambos extremos. 

Algunas aplicaciones prácticas de Deque :

• Se aplica como pila y cola, ya que admite ambas operaciones.

Soporte de lenguaje: C++ STL proporciona una implementación de Deque como std::deque y Java proporciona la interfaz Deque . Vea esto para más detalles. Deque en Java Implementación de Deque en Python
: un Deque se puede implementar usando una lista doblemente enlazada o una array circular. En ambas implementaciones, podemos implementar todas las operaciones en tiempo O(1). Pronto discutiremos la implementación C/C++ de la estructura Deque Data. Implementación de Deque utilizando una array circular Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra otras formas de resolver el mismo problema.