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 en entrar, 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áticoEn el programa que se verá en seguida, se simula el comportamiento de una estructura de pila. Aunque en el mismo se usa un arreglo estático de tamaño fijo se debe mencionar que normalmente las implementaciones hechas por fabricantes y/o terceras personas se basan en listas dinámicas o enlazadas.
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>
usingnamespace std;
#define STACK_SIZE 256 /* capacidad máxima */
typedefchar 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();
return0;
}
}
- Pila dinámica
En el siguiente programa se presenta una implementación de una estructura dinámica tipo pila o stack. Es importante hacer notar que, a diferencia de una pila basada en un arreglo estático, una pila enlazadada dinámicamente no posee de forma natural el mecanismo de acceso por índices, en ese sentido, el programador puede crear los algoritmos necesarios para permitir tal comportamiento. En la clase que presentaremos en el ejemplo no se ha implementado el mecanismo de acceso por índices, ya que la misma se presenta como una alternativa para la simulación de una pila o stack.
Uno de los puntos más destacables en cuando al uso de listas enlazadas dinámicamente es el hecho de crear estructuras conocidas como nodos. Un nodo es una especie de eslavon ( similar al de una cadena de bicicleta ), es decir, cada nodo se enlaza con otro a través de un puntero que apunta a una estructura del mismo tipo que el nodo. Por ejemplo, para crear una estructura de nodo para almacenar enteros y a la vez para apuntar a otro posible nodo podemos emplear la sintaxis:
struct nodo {
int data;
nodo*siguiente;
};
observe que con la declaración anterior estamos creando el tipo estructurado nodo, mismo que posee a los miembros: data para guardar valores enteros, y siguiente para apuntar o enlazar a un supuesto siguiente nodo.
Ya que las listas dinámicas inicialmente se encuentran vacias, y más aún, una lista dinámica no posee una dirección establecida en tiempo de compilación ya que las dirección de memoria que ocupará cada uno de los elementos se establecerá en tiempo de ejecución, entonces cómo determinar la condición de vacio ?. En nuestro ejemplo usaremos un contador ( ITEMS ) que dicho sea de paso, si ITEMS = 0, entonces la lista está vacia. ( la condición de vacio también podría determinarse al verificar el SP, es decir, si el SP = NULL, significa que la lista no posee elementos ).
Al hacer un análisis previo de los eventos que acontecerán en la pila y su puntero de lectura y escritura (SP, que en esta ocasión es una estructura tipo nodo), se tiene lo siguiente:
1) Al principio la lista está vacia, en ese caso el SP es igual a NULL y, en consecuencia, el puntero next también es NULL.
SP = NULL
+------+------+
| ???? | next |--> NULL
+------+------+
2) Después de agregar el primer elemento la situación se vería así:
SP = asignado
1
+------+------+
| data | next |--> NULL
+------+------+
3) Después de agregar otro elemento la situación se vería así:
SP = asignado
2 1
+------+------+ +------+------+
| data | next |--> | data | next |--> NULL
+------+------+ +------+------+
Ejemplo: Pila basada en un arreglo dinámico
/*---------------------------------------------------------------+
+ ejemplo de una pila ( STACK ) enlazada dinámicamente +
+ +
+ Autor: Oscar E. Palacios +
+ email: oscarpalacios1@yahoo.com.mx +
+ +
+ Manifiesto: +
+ Este programa puede distribuirse, copiarse y modificarse de +
+ forma libre. +
+---------------------------------------------------------------*/
#include <iostream>
//#include <conio.h>
usingnamespace std;
/* tipo de dato que contendrá la lista */
typedefchar DATA_TYPE;
// declaraci¢n de estructura nodo
struct nodo {
DATA_TYPE data;
nodo*next;
};
class StackDin {
// atributos
int ITEMS;/* número de elementos en la lista */
int ITEMSIZE;/* tamaño de cada elemento */
nodo*SP;/* puntero de lectura/escritura */
public:
// constructor
StackDin(): SP(NULL), ITEMS(0), ITEMSIZE(sizeof(DATA_TYPE)){}
// destructor
~StackDin(){}
/* agregar componente a la lista */
DATA_TYPE put(DATA_TYPE valor)
{
nodo*temp;
temp=new nodo;
if(temp ==NULL)return-1;
temp->data = valor;
temp->next = SP;
SP = temp;
ITEMS ++;
return valor;
}
int empty(){return ITEMS ==0;}
/* retirar elemento de la lista */
DATA_TYPE get()
{
nodo*temp;
DATA_TYPE d;
if( empty())return-1;
d = SP->data;
temp= SP->next;
if(SP)delete SP;
SP = temp;
ITEMS --;
return d;
}
};// fin de la clase StackDin
/* punto de prueba para la clase StackDin */
int main()
{
//clrscr();
StackDin s;
DATA_TYPE d;
for(d='A'; d<='Z'; d++) s.put(d);
while(! s.empty())
cout<<(DATA_TYPE)s.get()<<" ";
cout<<"\nPara terminar presione <Enter>...";
cin.get();
return0;
}
No hay comentarios:
Publicar un comentario