Bicola

La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.

Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.

Todas las operaciones de este tipo de datos tienen coste constante.

## Especificación de colas dobles en maude

[editar]

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

[editar]

// 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++

[editar]

// 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

[editar]

* Cola doblemente terminada
* Cola de prioridad (estructura de datos)
* Colas circulares (anillos)
* Cola (estructura de datos)

## Enlaces externos

[editar]

-Historia de las estructuras de datos -

Control de autoridades|

* Proyectos Wikimedia
* Datos: Q5728179

|

* Datos: Q5728179