Bicola

La ‘’bicola’’ o ‘’doble cola’’ (del inglés: ‘‘deque’’, abreviatura de ‘‘double-ended queue’’) es una cola especial que permite la inserción y eliminación de elementos por ambos extremos.

Este tipo de estructura puede implementarse utilizando un vector y dos índices que delimitan los extremos activos, aunque su representación más habitual es mediante una lista circular doblemente enlazada.

Las operaciones básicas de una bicola —como la inserción o eliminación de elementos en cualquiera de sus extremos— pueden realizarse en tiempo constante (O(1)), dependiendo de la implementación.

Especificación de colas dobles en maude fmod COLA-DOBLE {X :: TRIV} is protecting NAT . sorts ColaDobleNV{X} ColaDoble{X} . subsort ColaDobleNV{X} < ColaDoble{X} . ***generadores op crear : -> ColaDoble{X} [ctor] . op encolarIzq : X$Elt ColaDoble{X} -> ColaDobleNV{X} [ctor] . ***constructores op encolarDch : X$Elt ColaDoble{X} -> ColaDobleNV{X} .¡ op extraerIzq : ColaDoble{X} -> ColaDoble{X} . op extraerDch : ColaDoble{X} -> ColaDoble{X} . ***selectores op frenteIzq : ColaDobleNV{X} -> X$Elt . op frenteDch : ColaDobleNV{X} -> X$Elt .

vars E E1 E2 : X$Elt . vars C : ColaDoble{X} . vars CNV : ColaDobleNV{X} .

eq encolarDch(E, crear) = encolarIzq (E, crear) . eq encolarDch(E1, encolarIzq(E2, C)) = encolarIzq(E2, encolarDch(E1, C)) . eq extraerIzq(crear) = crear . eq extraerIzq(encolarIzq(E, C)) = C . eq extraerDch(crear) = crear . eq extraerDch(encolarIzq(E, crear)) = crear . eq extraerDch(encolarIzq(E, C)) = encolarIzq(E, extraerDch(C)) . eq frenteIzq(encolarIzq(E, C)) = E . eq frenteDch(encolarIzq(E, crear)) = E . eq frenteDch(encolarIzq(E, CNV)) = frenteDch(CNV) . endfm

Especificación de colas dobles en java // ArrayCircularQueue.java

package com.javajeff.cds;

public class ArrayCircularQueue implements Queue { private int front = 0, rear = 0; private Object [] queue;

public ArrayCircularQueue (int maxElements) { queue = new Object [maxElements]; }

public void insert (Object o) { int temp = rear; rear = (rear + 1) % queue.length; if (front == rear) { rear = temp; throw new FullQueueException (); } queue [rear] = o; }

public boolean isEmpty () { return front == rear; }

public boolean isFull () { return ((rear + 1) % queue.length) == front; }

public Object remove () { if (front == rear) throw new EmptyQueueException (); front = (front + 1) % queue.length; return queue [front];

Especificación de colas dobles en C++ // coladoble.hpp #ifndef INCLUIDO_CoLaDobLe_ #define INCLUIDO_CoLaDobLe_

class ColaDoble { public: struct TAnillo{ //Esta estructura se puede modificar según la conveniencia del programador que la use unsigned int x, y; //sin necesidad de modificar el .cpp }; //Si no se quiere usar una estructura se deberá hacer un typedef TAnillo

enum TExtremo {frente, final}; ColaDoble(); //Constructor se llama automáticamente. ~ColaDoble(); //Destructor se llama automáticamente. bool EstaVacia() const; //Devuelve true si esta vacía la cola void Encolar(const TAnillo &a, TExtremo ext=final);//Añade un elemento por el extremo apuntado por ext void Desencolar(TExtremo ext=frente); //Quita un elemento por el extremo apuntado por ext bool Valor(TAnillo &a, TExtremo ext=frente) const; //Devuelve el valor del extremo apuntado por ext, NO ELIMINA NADA DE LA COLA //para eliminar y consultar el siguiente se debera usar Desencolar()

private: struct NodoCD

TAnillo an; NodoCD *sig;

NodoCD *cabeza; NodoCD *cola; }; #endif

// coladoble.cpp #include "coladoble.hpp"

ColaDoble::ColaDoble() : cabeza(0), cola(0)

ColaDoble::~ColaDoble() { NodoCD *aux;

while (cabeza)

aux=cabeza->sig; delete cabeza; cabeza=aux;

bool ColaDoble::EstaVacia() const { return cabeza==0;

void ColaDoble::Encolar(const TAnillo &a, TExtremo ext) { NodoCD *nuevo = new NodoCD; nuevo->an=a;

if (cabeza==0){ cabeza=nuevo; cola=nuevo; nuevo->sig=0;

else if(ext==frente){ nuevo->sig=cabeza; cabeza=nuevo;

else{ nuevo->sig=0; cola->sig=nuevo; cola=nuevo;

void ColaDoble::Desencolar(TExtremo ext) { NodoCD *aux;

if(!EstaVacia()){ if (cabeza==cola){ delete cabeza; cabeza = cola = 0;

else if (ext==frente){ aux = cabeza->sig; delete cabeza; cabeza = aux;

else{ aux = cabeza; while(aux->sig != cola){ aux = aux->sig;

aux->sig = 0; delete cola; cola = aux;

bool ColaDoble::Valor(TAnillo &a, TExtremo ext) const { if (EstaVacia()){ return false;

if(ext == frente){ a=cabeza->an;

else{ a=cola->an;

return true; }

Véase también Cola doblemente terminada Cola de prioridad (estructura de datos) Colas circulares (anillos) Cola (estructura de datos)

Enlaces externos

-Historia de las estructuras de datos -

Categoría:Estructura de datos Categoría:Lingüística computacional Categoría:Algoritmos