Capítulo 7

.
Pila o LIFO (Last In First Out)

Esta es una estructura de orden restrictivo. Los datos se agregan en un único orden y se sacan exactamente en el orden inverso al que fueron agregados.

Imaginemos una "pila de libros". Tenemos los libros A, B y C. Tomamos el libro A y lo colocamos en una mesa. Luego tomamos el libro B y lo colocamos sobre el libro A. Luego tomamos el libro C y lo colocamos sobre el libro B. Así conformamos una "pila de libros".

Para desapilar nuestra "pila de libros" tomamos el primer libro de la pila (el que quedó más arriba, o sea el libro C), luego tomamos el próximo (el B) y por último el libro A (que fue el primer libro colocado en la pila).

Esto demuestra que "el primer elemento que ingresa a la pila será el último elemento en salir". Por eso también este tipo de estructuras se llaman LIFO: "Last In First Out" o "Ultimo Entrado, Primero Salido".

Consideraremos una pila de números enteros por lo tanto seguiremos utilizando nuestro registro tipo Nodo y el tipo PNodo para apuntarlo.


La siguiente imagen muestra como quedaría una pila de enteros al agregarle un valor 3, luego un 2 y luego un 1.

Vemos que el puntero p apunta al nodo con valor 3. Luego agregamos un nuevo nodo con valor 2 pero el lugar de agregarlo al final lo agregamos al principio haciendo que p apunte al nuevo nodo y que el valor siguiente (sig) del nuevo nodo apunte al anterior valor de p.

El puntero p siempre apunta al elemento que está en la "cima" de la pila. Por lo tanto, si queremos tomar (y luego eliminar) un elemento de la pila tomaremos el elemento cuyo nodo está siendo apuntado por p.

Asignamos a una variable aux el valor de p y hacemos que p apunte al próximo nodo. Para liberar el nodo con valor 1 haremos dispose(aux). El puntero p ya está apuntando al próximo valor que debe salir de la pila.

Las operaciones asociadas a la pila son 2:

• poner - apila un elemento
• sacar - saca un elemento de la pila

Veamos entonces el código de la unidad (unit) untPilas donde definiremos estas operaciones.

untPilas.pas

   1:
   2:unit untPilas;
   3:
   4:interface
   5:
   6:type
   7:
   8:   PNodo = ^Nodo;
   9:   Nodo = record
  10:      info:integer;
  11:      sig:PNodo;
  12:   end;
  13:
  14:   procedure poner(var p:PNodo; valor: integer);
  15:   function sacar(var p:PNodo):integer;
  16:
  17:implementation
  18:// : 
  19:// la seccion implementation se define mas abajo
  20:// :
  21:

procedure poner(var p:PNodo;valor:integer)

Basicamente este procedimiento hace lo siguiente: crea un nuevo nodo y asigna en su campo siguiente (sig) el valor de p. Luego asigna a p la dirección del nuevo nodo.

El código Pascal es:

untPilas.pas (implementación: procedure poner)

   1:
   2:procedure poner(var p:PNodo; valor: integer);
   3:var nuevo:PNodo;
   4:begin
   5:   new(nuevo);
   6:   nuevo^.info:=valor;
   7:   nuevo^.sig:=p;
   8:
   9:   // modifica el comienzo de la pila,
  10:   // ahora comienza desde el nuevo nodo
  11:   p:=nuevo;
  12:end;
  13:

function sacar(var p:PNodo):integer

Sacar lo implementaremos como función. El objetivo será retornar el valor que corresponda, modificar el puntero p haciéndolo apuntar al próximo valor en la pila y liberar la memoria del nodo que acabamos de eliminar.

Para resolver la función utilizamos dos variables auxiliares: ret y aux. En ret asignamos el valor de p (p^.info) y a aux le asignamos p. Necesitamos guardar esos dos valores (valor y dirección) porque a continuación avanzamos p asignándole p^.sig. Luego liberamos aux y retornamos ret.

untPilas.pas (implementación: function sacar)

   1:
   2:function sacar(var p:PNodo):integer;
   3:var aux:PNodo;
   4:begin
   5:   sacar:=p^.info;
   6:   aux:=p;
   7:   p:=p^.sig;
   8:   dispose(aux);
   9:end;
  10:
  11:end.
  12:

Con la funcionalidad de la pila ya creada podemos desarrollar un pequeño programa que permita ingresar un conjunto de valores numéricos para luego mostrarlos en orden inverso, cargándolos en una pila.

testPila.pas

   1:
   2:uses untPilas;
   3:
   4:var p:PNodo;n:integer;
   5:begin
   6:
   7:   // leo un valor x teclado
   8:   write('Ingrese Valor:');
   9:   readln(n);
  10:  
  11:   while( n<>0 ) do begin
  12:      // meto el valor en la pila
  13:      poner(p,n);
  14:     
  15:      // leo el siguiente valor
  16:      write('Ingrese Valor:');
  17:      readln(n);
  18:   end;
  19:  
  20:   // muestro los valores de la pila
  21:   while(p<>NIL) do begin
  22:      writeln( sacar(p) );
  23:   end;
  24:
  25:end.
  26:

.........................,...................

Algoritmos y Estructuras de Datos UTN - UBA.