Deque es un tipo de cola en la que la inserción y la eliminación se pueden realizar desde la parte delantera o trasera . No sigue la regla FIFO. También se conoce como cola de dos extremos.
Operaciones en Deque:
El deque consta principalmente de las siguientes operaciones:
- Insertar frente
- Insertar trasero
- Eliminar frente
- Eliminar trasero
1. Insertar al frente: Esta operación se utiliza para agregar un elemento al frente. Si el número de elementos no excede el tamaño del deque, solo se realiza la inserción.
2. Insertar en la parte trasera: si el deque no está lleno, esta función inserta el elemento al final de la cola.
3. Eliminar desde el frente: esta operación se utiliza para eliminar un elemento del deque. Si el deque no está vacío, esta operación eliminará un elemento del extremo frontal del deque.
4. Eliminar desde la parte posterior: esta operación se utiliza para eliminar un elemento de la parte posterior del deque si el deque no está vacío.
Para obtener más detalles sobre la operación y su implementación usando una array circular o una lista doblemente enlazada, siga los artículos sobre » Implementación de Deque usando una array circular » e » Implementación de Deque usando una lista doblemente enlazada «.
Propiedades de Deque:
- Deque es una versión generalizada de la cola que nos permite insertar y eliminar el elemento en ambos extremos.
- No sigue la regla FIFO (first in first out).
Aplicaciones de Deque:
- Se utiliza en algoritmos de programación de trabajos.
- Si admite operaciones de pila y cola.
- Las operaciones de rotación en sentido horario y antihorario en deque se realizan en tiempo O(1), lo que es útil en muchos problemas.
Aplicación en tiempo real de Deque:
- En el historial de un navegador web, las URL visitadas recientemente se agregan al frente del deque y la URL en la parte posterior del deque se elimina después de un número específico de operaciones de inserciones en el frente.
- Almacenamiento de la lista de operaciones de deshacer de una aplicación de software.
Ventajas de Deque:
- Puede agregar y eliminar elementos de la parte delantera y trasera de la cola.
- Los deques son más rápidos a la hora de añadir y quitar elementos al final o al principio.
- Las operaciones de rotación en sentido horario y antihorario son más rápidas en un deque.
Desventajas de Deque:
- Deque no tiene limitaciones fijas en cuanto al número de elementos que pueden contener. Esta interfaz admite deques con capacidad restringida, así como deques sin límite de tamaño fijo.
- Son menos eficientes con la memoria que una cola normal.