9.2. Una pila

Una de las estructuras dinámicas más sencillas, y, por tanto, más fáciles de entender y de programar, es lo que se conoce como "una pila". Podemos compararla con una pila de libros: si queremos añadir un nuevo libro, lo ponemos encima de los que ya existen; si queremos tomar libros, debemos empezar por la parte superior (así, para llegar al tercer libro deberíamos retirar antes los dos primeros).

En informática, una "pila" es una estructura de datos que se comporta de forma similar: contiene una colección de datos, y se puede añadir un nuevo elemento mediante la operación "Apilar" (y quedará en la "cima" de la pila), o retirar el elemento de la cima (y sólo ese) con la operación "Desapilar".

Como primera aproximación, vamos a crear una pila, que almacenará números enteros, y lo haremos usando memoria estática (un array), de modo que tendrá un tamaño limitado y que será fácil desbordar (y, en ese caso, nuestro programa fallará). Eso nos ayudará a ver las ideas básicas, para luego intentar aplicarlas a una estructura dinámica.

(* PILA1.PAS, Ejemplo de pila estatica  *)
(* Parte de CUPAS5, por Nacho Cabanes   *) 

program pilaEstatica;

var
    datos: array[1..10] of integer;
    cima: integer;
    
procedure InicializarPila;
begin
    cima := 0;
end;

procedure Apilar(nuevoDato: integer);
begin
    cima := cima + 1;
    datos[cima] := nuevoDato;
end;    

function Desapilar: integer;
begin
    Desapilar := datos[cima];
    cima := cima - 1;
end; 

function CantidadDatos: integer;
begin
    CantidadDatos := cima;
end;

{ --- Programa de prueba --- }

var
    n: integer;

begin
    InicializarPila;
    WriteLn('Guardando 3 y 2...');
    Apilar(3);
    Apilar(2);
    WriteLn('Los datos eran:');
    WriteLn( Desapilar );
    WriteLn( Desapilar );
    
    WriteLn('Ahora introduce datos, 0 para terminar...');
    repeat
        Write('Dato? ');
        ReadLn( n );
        if n <> 0 then
            Apilar(n);
    until n = 0;
    
    WriteLn('Los datos eran:');
    while CantidadDatos > 0 do
        WriteLn( Desapilar );
end.

Debería resultar fácil de seguir. Pero no es eficiente: si intentamos guardar más de 10 datos, el programa fallará. Si "sobredimensionamos", reservando espacio para (por ejemplo) 1000 datos, estaremos desperdiciando memoria en la gran mayoría de las ocasiones.

Si queremos crear esta pila usando memoria dinámica, de modo que pueda crecer tanto como sea necesario, necesitaremos varias ideas nuevas y un par de órdenes nuevas.

• Por una parte, deberemos pensar en una serie de "nodos". Cada "nodo" contendrá el dato que realmente queremos guardar, pero también tendrá un "enlace" que nos permita saber dónde buscar el siguiente nodo.
• Necesitaremos una orden que nos permita "reservar memoria" para un nuevo nodo cada vez que lo necesitemos. Será la orden "new".
• Necesitaremos otra orden que nos permita "liberar memoria", cada vez que queramos eliminar un nodo. Será la orden "dispose".

Ese "enlace" entre nodos será lo que llamaremos un "puntero" o "apuntador" (en inglés, "pointer"), la dirección de memoria en la que se encuentra el siguiente dato. Así, la apariencia de un "nodo" será la siguiente:

type
    nodo = record
        dato: integer;
        siguiente:  puntero
    end; 

Donde ese tipo de datos "puntero" sería un "puntero a nodo", es decir, una dirección de memoria en la que habrá otro nodo, algo que se escribe así:

type
    puntero = ^ nodo;

Ahora sólo falta tener en cuenta que cuando "apilemos" un dato, deberemos reservar memoria para él, con la orden "new", y cuando "desapilemos" deberemos liberar esa memoria, con la orden "dispose", de forma que el programa completo podría ser así:

(* PILA2.PAS, Ejemplo de pila dinamica *)
(* Parte de CUPAS5, por Nacho Cabanes  *) 

program pilaDinamica;

type
    puntero = ^ nodo;

    nodo = record
        dato: integer;
        siguiente:  puntero
    end; 

var
    cima: puntero;
    contadorDeDatos: integer;
    
procedure InicializarPila;
begin
    cima := nil;
    contadorDeDatos := 0;
end;

procedure Apilar(nuevoDato: integer);
var
    nuevoNodo: puntero;
begin
    { Reservamos espacio para un nuevo nodo }
    new(nuevoNodo);
    { Guardamos el dato en él }
    nuevoNodo^.dato := nuevoDato;
    { Lo ponemos "encima" de la cima actual }
    nuevoNodo^.siguiente := cima;
    { Y hacemos que éste sea la nueva cima }
    cima := nuevoNodo;
    { Y anotamos que tenemos un dato más }
    contadorDeDatos := contadorDeDatos + 1;
end;    

function Desapilar: integer;
var
    nuevaCima: puntero;
begin
    { Tomamos el dato de la cima }
    Desapilar := cima^.dato;
    { Anotamos el siguiente, que será la nueva cima }
    nuevaCima := cima^.siguiente;
    { Liberamos el espacio que ocupaba este nodo }
    dispose(cima);
    { Y finalmente "movemos" la cima a su nueva posición }
    cima := nuevaCima;
    { Y anotamos que tenemos un dato menos }
    contadorDeDatos := contadorDeDatos - 1;
end; 

function CantidadDatos: integer;
begin
    CantidadDatos := contadorDeDatos;
end;

{ --- Programa de prueba --- }

var
    n: integer;

begin
    InicializarPila;
    WriteLn('Guardando 3 y 2...');
    Apilar(3);
    Apilar(2);
    WriteLn('Los datos eran:');
    WriteLn( Desapilar );
    WriteLn( Desapilar );
    
    WriteLn('Ahora introduce datos, 0 para terminar...');
    repeat
        Write('Dato? ');
        ReadLn( n );
        if n <> 0 then
            Apilar(n);
    until n = 0;
    
    WriteLn('Los datos eran:');
    while CantidadDatos > 0 do
        WriteLn( Desapilar );
end.

El cuerpo del programa no ha cambiado, se sigue manejando exactamente igual. Pero esta vez podemos almacenar tantos datos como queramos, sin tener que preocuparnos del tamaño del array, porque se reserva espacio para cada nuevo dato (con "new") cuando es necesario, y se libera espacio de cada dato (con "dispose") cuando ya no hace falta.

Ejercicio propuesto 9.2.1: Crea un programa que permita guardar una pila de "puntos". Cada punto tendrá dos coordenadas, llamadas X e Y. Ambas serán números reales. El programa pedirá datos de puntos al usuario, tanto como éste desee. Terminará cuando tanto la X como la Y valgan -1000. En ese momento, se mostrarán las coordenadas X e Y de todos los puntos almacenados.

Ejercicio propuesto 9.2.2: Crea una "pila de cadenas de texto". Utilízala para mostrar el contenido de un fichero de texto al revés (de la última línea a la primera).