PILAS Y COLAS
PILA O STACKS
Una PILA es una estructuras en donde cada elemento es insertado y retirado
del tope de la misma, y debido a esto el comportamiento de un una pila se
conoce como LIFO (último enentrar, primero en salir ).
Un ejemplo de pila o stack se puede observar en el mismo procesador, es decir, cada vez que en los programas aparece una llamada a una función el microprocesador guarda el estado de ciertos registros en un segmento de memoria conocido como Stack Segment, mismos que serán recuperados al regreso de la función.
Pila en arreglo estático
Para la implementación de la clase Stack se han elegido los métodos:
put(), poner un elemento en la pila
get(), retirar un elemento de la pila
empty(), regresa 1 (TRUE) si la pila esta vacia
size(), número de elementos en la pila
El atributo SP de la clase Stack es el puntero de lectura/escritura, es decir, el SP
indica la posición dentro de la pila en donde la función put() insertará el siguiente
dato, y la posición dentro de la pila de donde la función get() leerá el siguiente dato.
Cada vez que put() inserta un elemento el SP se decrementa.
Cada vez que get() retira un elemento el SP se incrementa.
En el siguente ejemplo se analiza lo que sucede con el SP (puntero de pila) cuando se guardan en la pila uno por uno los caracteres 'A', 'B', 'C' y 'D'. Observe que al principio el SP es igual al tamaño de la pila.
Llenando la pila.
SP
|
+---+---+---+---+---+
| | | | | | al principio (lista vacia)
+---+---+---+---+---+
SP
|
+---+---+---+---+---+ push('A');
| | | | | A | después de haber agregado el primer elemento
+---+---+---+---+---+
...
SP
|
+---+---+---+---+---+
| | D | C | B | A | después de haber agregado cuatro elementos
+---+---+---+---+---+
Vaciando la pila.
SP
|
+---+---+---+---+---+ pop();
| | D | C | B | A | después de haber retirado un elemento
+---+---+---+---+---+
...
SP
|
+---+---+---+---+---+
| | D | C | B | A | después de haber retirado todos los elementos
+---+---+---+---+---+
Nota: observe que al final la lista está vacia, y que dicho estado se debe a que
el puntero está al final de la pila y no al hecho de borrar físicamente cada elemento
de la pila.
Ejemplo: Pila basada en un arreglo estático
#include <iostream>
using namespace std;
#define STACK_SIZE 256 /* capacidad máxima */
typedef char arreglo[STACK_SIZE];
class Stack {
int sp; /* puntero de lectura/escritura */
int items; /* número de elementos en lista */
int itemsize; /* tamaño del elemento */
arreglo pila; /* el arreglo */
public:
// constructor
Stack() {
sp = STACK_SIZE-1;
items = 0;
itemsize = 1;
}
// destructor
~Stack() {};
/* regresa el número de elementos en lista */
int size() { return items; }
/* regresa 1 si no hay elementos en la lista, o sea, si la lista está vacia */
int empty() { return items == 0; }
/* insertar elemento a la lista */
int put(char d)
{
if ( sp >= 0) {
pila[sp] = d;
sp --;
items ++;
}
return d;
}
/* retirar elemento de la lista */
int get()
{
if ( ! empty() ) {
sp ++;
items --;
}
return pila[sp];
}
}; // fin de clase Stack
// probando la pila.
// Nota: obseve cómo los elementos se ingresan en orden desde la A hasta la Z,
// y como los mismos se recuperán en orden inverso.
int main()
{
int d;
Stack s; // s es un objeto (instancia) de la clase Stack
// llenando la pila
for (d='A'; d<='Z'; d++) s.put(d);
cout << "Items =" << s.size() << endl;
// vaciando la pila
while ( s.size() ) cout << (char)s.get() << " ";
cout << "\nPara terminar oprima <Enter>...";
cin.get();
return 0;
}
}
Colas o Queues
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 carácter ingresado es trasladado y depositado en una área de memoria intermedia conocida como "el buffer del teclado", para esto el microprocedador llama a una rutina específica. Luego, para leer el carácter depositado en el buffer existe otra función, es decir, hay una rutina para escribir 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 */
typedef char 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();
return 0;
}
