Una bicola o doble cola es una estructura de datos que permite la inserción y el borrado por ambos extremos, el izquierdo y el derecho.
En una de las prácticas que me propusieron hace tiempo, cuando cursé la asignatura de Estructura de Datos, fue precisamente la implementación de una bicola con la particularidad de que ésta tenía que ser circular y estar implementada sobre un array que, a medida que se introdujesen los valores, se fuese redimensionando solicitando más memoria al sistema para poder almacenarlos.
Así que a continuación dejo el código fuente, por si a algún estudiante le sirve de ayuda y para probar de paso la inserción de código fuente en el blog con el plugin SyntaxHighlighter Plus.
Descargar
Breve explicación
- Para hacer circular el array he utilizado dos métodos privados: goLeft() y goRight(), que utilizo para desplazarme para un lado o otro (izquierda o derecha) a partir de un puntero pasado como argumento (pi o pd).
- pi Es un puntero que siempre apunta al elemento de la izquierda.
- pd Es un puntero que siempre apunta al elemento de la derecha.
- p Es un puntero que apunta a la primera posición del array.
- Si intento desplazarme a la derecha y no hay más posiciones, el método goRight() me mandará al principio del array (“p”).
- El método goLeft() hace justo lo contrario: si intento avanzar hacia la izquierda y no hay más posiciones me mandará al último elemento del array.
- Con los métodos goLeft() y goRight() solvento el problema del desplazamiento circular por el array.
- getMem() Es el método encargado de pedir memoria.
- getLeft() Nos devuelve el elemento izquierdo.
- getRight() Nos devuelve el elemento derecho.
- putLeft() Inserta un elemento por la izquierda.
- putRight() Inserta un elemento por la derecha.
Bicola.h
/*
* Programa: Bicola
* Autor: Juan Gestal
* Web: http://www.gestal.es
*/
class Bicola {
int t;
int n;
int *p,*pi,*pd;
void Bicola::goLeft(int **q);
void Bicola::goRight(int **q);
void Bicola::getMem();
public:
Bicola();
~Bicola();
void putLeft(int e);
void putRight(int e);
int getLeft();
int getRight();
};
Bicola.cpp
/*
* Programa: Bicola
* Autor: Juan Gestal
* Web: http://www.gestal.es
*/
#include "bicola.h"
Bicola::Bicola() {
t=5; //tamaño
n=0; //número de elementos
p = new int[t]; //"p" apunta a un nuevo array de enteros de tamaño t
pi=pd=p; //El puntero izquierdo "pi" y el puntero derecho "pd" se inicializan a "p"
}
Bicola::~Bicola() {
delete []p;
}
/*
* putLeft() Introduce un elemento en la Bicola por la izquierda. Si no hay memoria
* llama a la función getMem() para pedirla.
*/
void Bicola::putLeft(int e) {
if (n >= t)
getMem();
if (n == 0) {
p[0]=e;
}
else {
goLeft(&pi);
*pi=e;
}
n++;
}
/*
* putRight() Introduce un elemento en la Bicola por la derecha. Si no hay memoria
* llama a la funciÛn getMem() para pedirla.
*/
void Bicola::putRight(int e) {
if (n >= t)
getMem();
if (n == 0) {
p[0]=e;
}
else {
goRight(&pd);
*pd=e;
}
n++;
}
/*
* getLeft() devuelve el elemento izquiedo de la bicola.
* Si se produce un error por que no hay elementos devuelve -1.
*/
int Bicola::getLeft() {
if (n > 0) {
int i=*pi;
if (n > 1) goRight(&pi);
n--;
return i;
}
else return -1;
}
/*
* getRight() devuelve el elemento de la derecha de la bicola.
* Si se produce un error por que no hay elementos devuelve -1;
*/
int Bicola::getRight(){
if (n > 0) {
int i=*pd;
if (n > 1) goLeft(&pd);
n--;
return i;
}
else return -1;
}
/*
* goLeft() desplaza el puntero recibido como argumento una posición a la izquierda.
* En el caso de que se le pase un argumento que apunte al principio del array "p",
* lo manda a la última posición.
*/
void Bicola::goLeft(int **q) {
if (p == *q)
*q=&p[t-1];
else
(*q)--;
}
/*
* goRight() desplaza el puntero recibido como argumento una posiciÛn a la derecha.
* En el caso de que se le pase un argumento que apunte al final del array "p",
* lo manda a la primera posiciÛn.
*/
void Bicola::goRight(int **q) {
if (&p[t-1] == *q)
*q=p;
else
(*q)++;
}
/*
* getMem() es la funciÛn que pide memoria. Cada vez que se le llama amplia la capacidad del array "p"
* en 5 posiciones.
*/
void Bicola::getMem() {
int i;
int *q = new int[t+5];
for(i=0;pi != pd;i++) {
q[i]=*pi;
goRight(&pi);
}
q[i]=*pi;
delete []p;
pi=p=q;
pd=p+(n-1);
t=t+5;
}