Bicola

De Wikipedia, la enciclopedia libre
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[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]

#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
   };                                    //Si no se quiere usar una estructura se debera 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[editar]

Enlaces externos[editar]

-Historia de las estructuras de datos -