Bicola

Bicola

Saltar a navegación, búsqueda

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

#ifndef _CoLaDobLe_
#define _CoLaDobLe_
 
class ColaDoble 
{
  public:
  struct TAnillo{                        //Esta estructura se puede modificar según la conveniencia del progrador k la use
    unsigned int x, y;                   //sin necesidad de modificar el .cpp
   };                                    //Sino se quiere usar una estructura se devera hacer un typedef TAnillo
   enum TExtremo {frente, final};
   ColaDoble();                           //Constructor se llama automaticamente
   ~ColaDoble();                          //Destructor se llama automaticamente
   bool EstaVacia() const;                //Devuelve true si esta vacia la cola
   void Encolar(TAnillo &a, TExtremo ext);//Añade un elemento por el extremo apuntado por ext
   void Desencolar(TExtremo ext);         //Quita un elemento por el extremo apuntado por ext
   void Valor(TAnillo &a, TExtremo ext);  //Devuelve el valor del extremo apuntado por ext, NO ELIMINA NADA DE LA COLA
										 //para eleminar y consultar el siguiente se devera usar Desencolar()
 
  private:
   struct NodoCD 
   {
    TAnillo an; 
    NodoCD *sig;
   }; 
   NodoCD *cabeza;
   NodoCD *cola;
};
#endif
 
#include "coladoble.hpp"
 
ColaDoble::ColaDoble()
{
cabeza = 0;
cola = 0;
}
 
ColaDoble::~ColaDoble()
{
NodoCD *aux;
 
  while (cabeza!=0)
  {
    aux=cabeza->sig;
    delete cabeza;
    cabeza=aux;
  }
}
 
bool ColaDoble::EstaVacia() const
{
return cabeza==0;
} 
 
void ColaDoble::Encolar(TAnillo &a, TExtremo ext=frente)
{
NodoCD *nuevo;
 
  nuevo = new NodoCD;
  nuevo->an=a;
  if (cabeza==0){
    cabeza=nuevo;
    cola=nuevo;
    nuevo->sig=0;
  }
 
  else{
    if(ext==frente){
      nuevo->sig=cabeza->sig;
      cabeza->sig=nuevo;
    }
    else{
      nuevo->sig=0;
      cola->sig=nuevo;
      cola=nuevo;
    }
  }
}
 
void ColaDoble::Desencolar(TExtremo ext=final)
{
NodoCD *aux;
 
  if(!EstaVacia()){
    if (ext==frente){
      aux=cabeza->sig;
      delete cabeza;
      cabeza = aux;
    }
    else{
      aux=cabeza;
      while(aux->sig!=0){
        aux = aux->sig;
      }
      delete cola;
      cola = aux;
    }
  }
}
 
void ColaDoble::Valor(TAnillo &a, TExtremo ext=final) 
{
  if (!EstaVacia()){
    if(ext = frente){
      a=cabeza->an;
    }
    else{
      a=cola->an;
    }
  }
}

Véase también

• Cola de prioridad (estructura de datos)
• Colas circulares (anillos)
• Cola (estructura de datos)

Enlaces externos

-Historia de las estructuras de datos -

Obtenido de "Bicola"