Deque
Hasta ahora habiamos considerado los conceptos de FIFO (First in, First Out - Queue) y LIFO (Last in, First out - Stack) por separado, sin embargo, ¿Qué pasa si consideramos los dos a la vez?. Bueno, pues obtenemos una nueva estructura de datos llamada Deque.
# Operaciones
Una vez descrito lo que es un Deque podemos imaginar las cuatro operaciones basicas que tiene:
- insert_front
- insert_back
- remove_front
- remove_back Todas estas operaciones se realizan en O(1).
Adicionalmente tenemos otras operaciones que tambien toman O(1).
- peek_front
- peek_back
- check_if_full
Usualmente las implementaciones de esta estructura de datos no soportan indices.
# Usos
Las deque son constantemente usadas en el software, algunos ejemplos de sus usos e implementaciones podrian ser:
- El uso del CTRL-Z, este guarda la ultima operacion y la operacion actual, al ser presionada se devuelve la ultima operacion realizada.
- Procesamiento multi-threading. Cuando un thread termina todas sus tareas puede quitar tareas que esten ultimas en el deque de otro thread.
- Historial de un buscador. Al principio se tienen los links a los ultimos sitios visitados y hasta al final los mas viejos, sin embargo, si visitamos un sitio viejo nuevamente, podemos traerlo hasta adelante junto con los ultimos visitados.
Siguiente: [[]]