Cola doblemente terminada
Una cola doblemente terminada o deque (del inglés double ended queue) es una estructura de datos lineal que permite insertar y eliminar elementos por ambos extremos, podría verse como un mecanismo que permite aunar en una única estructura las funcionalidades de las pilas (estructuras LIFO) y las colas (estructuras FIFO), en otras palabras, estas estructuras (pilas y colas) podrían implementarse fácilmente con una deque.
Operaciones
Las operaciones que se pueden realizar con una cola doblemente terminada son:
| operación | C++ | Java | Perl | Python | Ruby |
|---|---|---|---|---|---|
| Insertar elemento al final | push_back | offerLast | push | append | push |
| Insertar elemento al principio | push_front | offerFirst | unshift | appendleft | unshift |
| Eliminar el último elemento | pop_back | pollLast | pop | pop | pop |
| Eliminar el primer elemento | pop_front | pollFirst | shift | popleft | shift |
| Examinar el último elemento | back | peekLast | $_[-1] | <obj>[-1] | last |
| Examinar el primer elemento | front | peekFirst | $_[0] | <obj>[0] | first |
Implementaciones
Hay al menos dos formas eficientes de implementar una cola doblemente terminada: Con un vector dinámico modificado o con una lista doblemente enlazada (ver Lista (estructura de datos)).
Implementación con vector dinámico
La cola doblemente terminada se puede implementar utilizando una variante del vector dinámico que pueda crecer por ambos extremos. Este vector tiene todas las propiedades de un vector dinámico, como el acceso en tiempo constante a cualquiera de sus elementos, buena identificación de referencias, y una ineficiente forma de insertar o eliminar elementos por en medio de la estructura. A estas características se añade la de que el tiempo de inserción y borrado de elementos en los dos extremos de la estructura es constante (en vez de sólo uno de los extremos). Esta implementación requiere:
- Almacenar los elementos de la cola doblemente terminada en un buffer circular, este sólo se debe redimensionar cuando se encuentre completamente lleno, de este modo se reduce la frecuencia de redimensionamientos. Este sistema requiere de un mecanismo de indexación más elaborado.
- Asignar los contenidos de la pila desde el centro del vector subyacente y redimensionarlo cuando se llegue a cualquiera de los extremos. Esta aproximación también requiere redimensionamientos muy frecuentes y genera residuos de espacio en la memoria, particularmente cuando sólo se están insertando elementos por un solo extremo.
Soporte
La Librería Estándar de Plantillas de C++ proporciona las clases genéricas std::deque y std::list, donde ambas ofrecen las operaciones de colas doblemente terminadas.
El Collections Framework de Java incluye una nueva interfaz Deque que proporciona la funcionalidad para insertar y eliminar en ambos extremos. Está implementada por clases como ArrayDeque y LinkedList, las implementaciones con array dinámico y lista enlazada respectivamente.
Python 2.4 introduce el módulo collections con soporte para objetos "cola doblemente terminada".
Complejidad
- En una implementación realizada con una lista doblemente enlazada la complejidad de todas las iteraciones es "O(1)", excepto para acceder a un elemento que no se encuentre en uno de los extremos de la estructura, que la complejidad será "O(n)".
- Si se implementa mediante un vector, la complejidad de las operaciones de la cola doblemente terminada coincide con la de la implementación con una lista.
Referencias
- Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
Véase también
- Estructura de datos
- Estructuras de datos lineales
Enlaces externos
- Implementación en C++ (Universidad de granada)