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]

Enlaces externos[editar]

-Historia de las estructuras de datos -

Datos: Q5728179