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