Una cola sencilla es una estructura en donde cada elemento es insertado
inmediatamente después del último elemento insertado; y donde los elementos
se retiran siempre por el frente de la misma, debido a esto el comportamiento
de un una cola se conoce como FIFO (primero en entrar, primero en salir).
Un ejemplo a citar de cola es el comportamiento del buffer del teclado.Cuando en el teclado se oprime una tecla, el código del caracter ingresado es trasladado y depositado en una aréa de memoria intermedia conocida como "el buffer del teclado", para esto el microprocedador llama a una rutina específica. Luego, para leer el caracter depositado en el buffer existe otra función, es decir, hay una rutina para excribir y otra para leer los caracteres del buffer cada una de las cuales posee un puntero; uno para saber en donde dentro del buffer se escribirá el siguiente c¢digo y otro para saber de donde dentro del buffer se leerá el siguiente código.
- Cola en un arreglo estático
En el programa que se ve en seguida, se simula el comportamiento de una estructura de cola simple. Aunque en el mismo se usa un arreglo estático de tamañoo fijo se debe mencionar que normalmente las implementaciones hechas por fabricantes y/o terceras personas se basan en listas dinámicas o dinamicamente enlazadas.
Para la implementación de la clase Queue se han elegido los métodos:
put(), poner un elemento en la cola
get(), retirar un elemento de la cola
empty(), regresa 1 (TRUE) si la cola est vacia
size(), n£mero de elementos en la cola
El atributo cabeza de la clase Queue es el puntero de lectura.
El atributo cola de la clase Queue es el puntero de escritura.
Es decir, la cola indica la posici¢n dentro de la lista en donde la función put() insertará el siguiente dato, y la cabeza indica la posición dentro de la lista de donde la función get() leerá el siguiente dato.
Cada vez que put() inserta un elemento la cola se incrementa.
Cada vez que get() retira un elemento la cabeza se incrementa.
En el siguente ejemplo se analiza lo que sucede con la cola y la cabeza (punteros de escritura y de lectura de la Lista) cuando se guardan en la cola uno por uno los caracteres 'A', 'B', 'C' y 'D'. Observe que al principio: cola = cabeza = cero.
Llenando la cola.
cola
|
+---+---+---+---+---+
| | | | | | al principio
+---+---+---+---+---+
|
cabeza
cola
|
+---+---+---+---+---+ put('A');
| A | | | | | después de haber agregado el primer elemento
+---+---+---+---+---+
|
cabeza
...
cola
|
+---+---+---+---+---+
| A | B | C | D | | después de haber agregado cuatro elementos
+---+---+---+---+---+
|
cabeza
Vaciando la cola.
cabeza
|
+---+---+---+---+---+
| A | B | C | D | | antes de haber retirado elementos
+---+---+---+---+---+
cabeza
|
+---+---+---+---+---+ get();
| A | B | C | D | | después de haber retirado un elemento
+---+---+---+---+---+
...
cabeza
|
+---+---+---+---+---+ al final
| A | B | C | D | | después de haber retirado todos los elementos
+---+---+---+---+---+
|
cola
Observese que al final el cabeza apunta hacia el mismo elemento que la cola, es decir, la cola vuelve a estar vacia. Puesto que la cola que estamos proyectando reside en un arreglo estático los componentes del arreglo aún están dentro de la misma, salvo que para su recuperación se debería escribir otro método. En una cola dinámica (como se demostrará más adelante) los elementos retirados de la misma se eliminan de la memoria y podría no ser posible su recuperación posterior.
Nota: En el programa que aparece en seguida, al tipo de lista implementado por la clase Queue se le conoce como "lista circular" debido al comportamiento de sus punteros. Es decir si los métodos para escribir o leer detectan que el puntero correspondiente ha sobrepasado el tamaño máximo de elementos permitidos dentro de la cola, éste es puesto a cero.
Ejemplo: cola en un arreglo estático
/*---------------------------------------------------------------+
+ ejemplo de una cola (QUEUE) basada en un arreglo estático +
+ +
+ Autor: Oscar E. Palacios +
+ email: oscarpalacios1@yahoo.com.mx +
+ +
+ Manifiesto: +
+ Este programa puede distribuirse, copiarse y modificarse de +
+ forma libre. +
+---------------------------------------------------------------*/
#include <iostream.h>
#define MAX_SIZE 256 /* capacidad máxima */
typedefchar almacen[MAX_SIZE];
class Queue {
int cabeza;/* puntero de lectura */
int cola;/* puntero de escritura */
int ITEMS;/* número de elementos en la lista */
int ITEMSIZE;/* tamaño de cada elemento */
almacen alma;/* el almacen */
public:
// constructor
Queue(){
cabeza=0;
cola=0;
ITEMS =0;
ITEMSIZE =1;
}
// destructor
~Queue(){}
// regresa 1 (true) si la lista está vacia
int empty(){return ITEMS ==0;}
// insertar elemento a la lista
int put(int d)
{
if( ITEMS == MAX_SIZE)return-1;
if( cola >= MAX_SIZE){ cola =0;}
alma[cola]= d;
cola++;
ITEMS ++;
return d;
}
// retirar elemento de la lista
int get()
{
char d;
if( empty())return-1;
if( cabeza >= MAX_SIZE ){ cabeza =0;}
d =alma[cabeza];
cabeza++;
ITEMS --;
return d;
}
// regresa el n£mero de elementos en lista
int size(){return ITEMS;}
};// fin de la clase Queue
// probando la cola
int main()
{
int d;
Queue q;
for(d='A'; d<='Z'; d++) q.put(d);
cout<<"Items = "<< q.size()<< endl;
while( q.size()){
cout<<(char)q.get()<<" ";
}
cout<<"\nPara terminar oprima <Enter> ...";
cin .get();
return0;
}
Ejemplo: cola en un arreglo dinámico
/*---------------------------------------------------------------+
+ ejemplo de una cola (QUEUE) basada en un arreglo dinámico +
+ +
+ Autor: Oscar E. Palacios +
+ email: oscarpalacios1@yahoo.com.mx +
+ +
+ Manifiesto: +
+ Este programa puede distribuirse, copiarse y modificarse de +
+ forma libre. +
+---------------------------------------------------------------*/
#include <iostream>
usingnamespace std;
typedefchar DATA_TYPE;
struct nodo {
DATA_TYPE data;
nodo*next;
};
class QueueDin {
// atributos
int ITEMS, ITEMSIZE;
nodo*cola, *cabeza;
public:
// constructor
QueueDin(): cola(NULL), cabeza(NULL), ITEMS(0), ITEMSIZE(sizeof(DATA_TYPE)){}
// destructor
~QueueDin(){}
/* agregar componente a la lista */
DATA_TYPE put(DATA_TYPE valor)
{
nodo*temp;
temp=new nodo;
if(temp ==NULL)return-1;
ITEMS ++;
temp->data = valor;
temp->next =NULL;
if(cabeza ==NULL)
{
cabeza= temp;
cola= temp;
}else
{
cola->next = temp;
cola= temp;
}
return valor;
}
// regresa 1 (true) si la lista está vacia
int empty(){return ITEMS ==0;}
/* retirar elemento de la lista */
DATA_TYPE get()
{
nodo*temp;
DATA_TYPE d;
if( empty())return-1;
d = cabeza->data;
temp= cabeza->next;
if(cabeza)delete cabeza;
cabeza= temp;
ITEMS --;
return d;
}
};// fin de la clase QueueDin
/* punto de prueba */
int main()
{
QueueDin s;
DATA_TYPE d;
// llenando la cola
for(d='A'; d<='Z'; d++){
s.put(d);
cout<< d <<" ";
}
cout<< endl;
// vaciando la cola
while(! s.empty())
cout<<(DATA_TYPE)s.get()<<" ";
cout<<"\nPara terminar presione <Enter>...";
cin.get();
return0;
}
No hay comentarios:
Publicar un comentario