TAD PILA C++
DEFINICIN
Una pila es una estructura de datos homognea (elementos del mismo tipo), secuencial y de tamao variable.
Slo es posible un modo de acceso a esta estructura: a travs de la cabeza de la pila.
De este modo podemos aadir un elemento a la cabeza de la pila o extraer un elemento de la cabeza de la
pila. Debido a que las operaciones de extraccin e insercin se realizan por el mismo extremo, el ltimo
elemento en ser aadido ser el primero en ser extrado; por ello a estas estructuras se las conoce con el
nombre de LIFO ( last-in, first-out; ltimo en entrar, primero en salir).
La Pila GESTIN DE MEMORIA ESTTICA GESTIN DE MEMORIA DINMICA
Ejemplificaciones
Un ejemplo tpico de pila lo constituye un montn de platos: Cuando se quiere introducir un
nuevo plato, ste se coloca en la posicin ms accesible, encima del ltimo plato. Cuando se toma un plato,
ste se extrae, igualmente, del punto ms accesible, el ltimo que se ha introducido. O, si somos ms
estrictos, otro ejemplo sera una caja llena de libros. Slo podemos ver cul es el libro que est ms arriba en
la caja, y si ponemos o tomamos un libro, slo podremos actuar sobre este primer libro. No podemos
siquiera saber el nmero total de libros guardados en la pila. Slo sabremos el nmero de elementos de la
pila de libros si previamente los sacamos hasta vaciar la caja.
Otro ejemplo natural de la aplicacin de la estructura pila aparece durante la ejecucin de un programa de
ordenador, en la forma en que la mquina procesa las llamadas a los procedimientos. Cada llamada a un
procedimiento (o funcin) hace que el sistema almacene toda la informacin asociada con ese procedimiento
(parmetros, variables, constantes, direccin de retorno, etc...) de forma independiente a otros
procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y
que toda esa informacin almacenada pueda ser recuperada convenientemente cuando corresponda. Como
en un procesador slo se puede estar ejecutando un procedimiento, esto quiere decir que slo es necesario
que sean accesibles los datos de un procedimiento (el ltimo activado, el que est en la cima). De ah que
una estructura muy apropiada para este fin sea la estructura pila.
FUNCIONAMIENTO DE UNA PILA
Inicializacin
Modelo de la funcin:
void inicializacin (Pila *tas);
Esta
Esta
operacin debe ser
hecha
inicializa el puntero inicio con
antes
de cualquier
el puntero NULL, y
otra
operacin sobre
el tamao con el
la pila.
valor 0.
La funcin
void inicializacin (Pila * tas){
B. Insercin de un elemento en la pila
A
continuacin
el
algoritmo
de
insercin
registro
de
los
elementos:
declaracin del elemento a insertar
asignacin de la memoria para el nuevo elemento
rellenar el contenido del campo de datos
actualizar el puntero inicio hacia el 1er elemento (la cabeza de la pila)
Actualizar el tamao de la pila.
Modelo de la funcin:
int apilar (Pila *tas, char *dato);
La primera imagen muestra el inicio de la insercin, por lo tanto la lista de tamao 1 despus de la insercin. La
caracterstica de la pila no es muy apreciada con un solo elemento, ya que es el nico a recuperar.
En
cambio
la
2da
imagen
nos
permite
observar
el
comportamiento
de
la
pila.
Lo que debemos retener es que la insercin siempre se hace en la parte superior de la pila (al inicio de la lista).
La funcin
/* apilar (aadir) un elemento en la pila */
int apilar (Pila * tas, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = tas->inicio;
tas->inicio = nuevo_elemento;
tas->tamao++;
}
C. Eliminar un elemento de la pila
Para eliminar un elemento de la pila, simplemente hay que eliminar el elemento hacia el cual apunta el
puntero inicio.
Esta operacin no permite recuperar el dato en la cabeza de la pila, solo eliminarlo.
Modelo de la funcin:
int desapilar (Pila *tas);
La
Las
funcin
devuelve
-1
en
caso
de
error,
si
no
devuelve
0.
etapas:
el puntero sup_elemento contendr la direccin del 1er elemento
el puntero inicio apuntar hacia el 2do elemento (despus de la eliminacin del 1er elemento, el 2do
elemento estar en la cabeza de la pila)
el tamao de la pila disminuir un elemento.
