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]- Cola doblemente terminada
- Cola de prioridad (estructura de datos)
- Colas circulares (anillos)
- Cola (estructura de datos)
Enlaces externos
[editar]-Historia de las estructuras de datos -
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.