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

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

Enlaces externos

-Historia de las estructuras de datos -

Datos: Q5728179