- 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.
Contenido
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_backofferLastpushappendpushInsertar elemento al principio push_frontofferFirstunshiftappendleftunshiftEliminar el último elemento pop_backpollLastpoppoppopEliminar el primer elemento pop_frontpollFirstshiftpopleftshiftExaminar el último elemento backpeekLast$_[-1]<obj>[-1]lastExaminar el primer elemento frontpeekFirst$_[0]<obj>[0]firstImplementaciones
Hay al menos de 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 can 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 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 sólo extremo.
Soporte
La Librería Estándar de Plantillas de C++ proporciona las clases genéricas std::deque y std::list, para las implemteaciones con vector dinámico y lista enlazada respectivamente.
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
- Vector
- Pila
- Cola
- Cola de prioridades
- Lista enlazada
- Estructuras de datos lineales
Enlaces externos
- Implementación en C++ (Universidad de granada)
Wikimedia foundation. 2010.
