* Definición
* Implementación mediante array
* Implementación mediante lista enlazada
* Otras consideraciones

Definición

Una pila es una estructura de datos de acceso restrictivo a sus elementos. Se puede entender como una pila de libros que se amontonan de abajo hacia arriba. En principio no hay libros; después ponemos uno, y otro encima de éste, y así sucesivamente. Posteriormente los solemos retirar empezando desde la cima de la pila de libros, es decir, desde el último que pusimos, y terminaríamos por retirar el primero que pusimos, posiblemente ya cubierto de polvo.

En los programas estas estructuras suelen ser fundamentales. La recursividad se simula en un computador con la ayuda de una pila. Asimismo muchos algoritmos emplean las pilas como estructura de datos fundamental, por ejemplo para mantener una lista de tareas pendientes que se van acumulando.

Las pilas ofrecen dos operaciones fundamentales, que son apilar y desapilar sobre la cima. El uso que se les de a las pilas es independiente de su implementación interna. Es decir, se hace un encapsulamiento. Por eso se considera a la pila como un tipo abstracto de datos.

Es una estructra de tipo LIFO (Last In First Out), es decir, último en entrar, primero en salir.

A continuación se expone la implementación de pilas mediante arrays y mediante listas enlazadas. En ambos casos se cubren cuatro operaciones básicas: Inicializar, Apilar, Desapilar, y Vacía (nos indica si la pila está vacía). Las claves que contendrán serán simplemente números enteros, aunque esto puede cambiarse a voluntad y no supone ningún inconveniente.

Implementación mediante array

Esta implementación es estática, es decir, da un tamaño máximo fijo a la pila, y si se sobrepasa dicho límite se produce un error. La comprobación de apilado en una pila llena o desapilado en una pila vacía no se han hecho, pero sí las funciones de comprobación, que el lector puede modificar según las necesidades de su programa.

- Declaración:

type
    tpila = Record
          Cima : Integer;
          Elementos : Array[1..MAX_PILA] of Integer;
    End;

Nota: MAX_PILA debe ser mayor o igual que 1.

- Procedimiento de Creación:

Procedure crear(Var pila : tpila);
begin
     pila.cima := 0
end;

- Función que devuelve verdadero si la pila está vacía:

Function vacia(Var pila : tpila) : Boolean;
begin
     vacia := pila.cima = 0
end;

- Función que devuelve verdadero si la pila está llena:

Function llena(Var pila : tpila) : Boolean;
begin
     llena := pila.cima = MAX_PILA
end;

- Procedimiento de apilado:

Procedure apilar(Var pila : tpila; elem : integer);
begin
     Inc(pila.cima);
     pila.elementos[pila.cima] := elem
end;

- Procedimiento de desapilado:

Procedure desapilar(Var pila : tpila; Var elem : integer);
begin
     elem := pila.elementos[pila.cima];
     dec(pila.cima)
end;

Programa de prueba:

Var
   pila : tpila;
   elem : Integer;
Begin
     crear(pila);
     if (vacia(pila)) then writeln('Pila vacia');
     apilar(pila, 0);
     desapilar(pila, elem)
end.

Puesto que son muy sencillos, el usuario puede decidir implementar una pila 'inline', es decir, sin usar procedimientos ni funciones, lo cual aumentará el rendimiento a costa de una cierta legibilidad. Es más, los problemas que aparecen resueltos en esta web en general utilizan las pilas con arrays de forma 'inline'. Además, esta implementación es algo más rápida que con listas enlazadas, pero tiene un tamaño estático.

Implementación mediante lista enlazada

Para hacer la implementación se utiliza una lista con cabecera ficticia (ver apartado de listas). Dado el carácter dinámico de esta implementación no existe una función que determine si la pila está llena. Si el usuario lo desea puede implementar un análisis del código devuelto por la función de asignación de memoria.

- Declaración:

Type
    tpila = ^Rec;
    Rec = Record
        clave : Integer;
        sig : tpila;
    End;

- Procedimiento de creación:

Procedure crear(Var pila : tpila);
begin
  new(pila);
  pila^.sig := NIL
end;

- Función que devuelve verdadero si la pila está vacía:

Function vacia(pila : tpila) : boolean;
begin
  vacia := pila^.sig = NIL
end;

- Procedimiento de apilado (apila al comienzo de la lista):

Procedure apilar(pila : tpila; elem : Integer);
Var
  nuevo : tpila;
Begin
  New(nuevo);
  nuevo^.clave := elem;
  nuevo^.sig := pila^.sig;
  pila^.sig := nuevo
End;

- Procedimiento de desapilado (desapila del comienzo de la lista):

Procedure desapilar(pila : tpila; Var elem : Integer);
Var
  aux : tpila;
Begin
  aux := pila^.sig;
  elem := aux^.clave;
  pila^.sig := aux^.sig;
  dispose(aux)
End;

Programa de prueba:

Var
  pila : tpila;
  elem : Integer;
Begin
  crear(pila);
  if (vacia(pila)) then writeln('Pila vacia!');
  apilar(pila, 1);
  desapilar(pila, elem)
end.

Ver pilasle.pas para tener una implementación completa con lista enlazada.

En este caso, hacerlo 'inline' puede afectar seriamente la legibilidad del programa.

Otras consideraciones

- ¿Cuantos elementos hay apilados?

En algunos casos puede ser interesante implementar una función para contar el número de elementos que hay sobre la pila. En la implementación con arrays esto es directo. Si se hace sobre listas enlazadas entonces hay que hacer alguna pequeña modificación sobre la declaración e implementación:

Lista = ^Rec;
Rec = Record
    clave : Integer;
    sig : Lista;
End;
tPila = Record
    numero_elems : Integer;
    cima : Lista;
End;

Los detalles de la implementación no se incluyen, pues es sencilla.

- ¿Cómo vaciar la pila?

En el caso de la implementación con array es directo, basta con inicializar la cima al valor de vacío. Si es una lista enlazada hay que ir borrando elemento a elemento (o desapilarlos todos). Los detalles se dejan para el lector.

Elegir entre implementación con listas o con arrays.

El uso del array es idóneo cuando se conoce de antemano el número máximo de elementos que van a ser apilados y el compilador admite una región contigua de memoria para el array. En otro caso sería más recomendable usar la implementación por listas enlazadas, también si el número de elementos llegase a ser excesivamente grande.

La implementación por array es ligeramente más rápida. En especial, es mucho más rápido a la hora de eliminar los elementos que hayan quedado en la pila. Por lista enlazada esto no es tan rápido. Por ejemplo, piénsese en un algoritmo que emplea una pila y que en algunos casos al terminar éste su ejecución deja algunos elementos sobre la pila. Si se implementa la pila mediante una lista enlazada entonces quedarían en memoria una serie de elementos que es necesario borrar. La única manera de borrarlos es liberar todas las posiciones de memoria que le han sido asignadas a cada elemento, esto es, desapilar todos los elementos. En el caso de una implementación con array esto no es necesario, salvo que quiera liberarse la región de memoria ocupada por éste.