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
    • Vector
    • Pila
    • Cola
    • Cola de prioridades
    • Lista enlazada

Enlaces externos

• Implementación en C++ Archivado el 15 de abril de 2008 en Wayback Machine. (Universidad de granada)

• Datos: Q1192005