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

editar

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

editar

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

editar

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

editar

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

editar
  • 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

editar

Véase también

editar

Enlaces externos

editar