* 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:

struct tpila
{
  int cima;
  int elementos[MAX_PILA];
};

Nota: MAX_PILA debe ser mayor o igual que 1.

- Procedimiento de Creación:

void crear(struct tpila *pila)
{
  pila->cima = -1;
}

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

int vacia(struct tpila *pila)
{
  return (pila->cima == -1);
}

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

int llena(struct tpila *pila)
{
  return (pila->cima == MAX_PILA);
}

- Procedimiento de apilado:

void apilar(struct tpila *pila, int elem)
{
  pila->elementos[++pila->cima] = elem;
}

- Procedimiento de desapilado:

void desapilar(struct tpila *pila, int *elem)
{
  *elem = pila->elementos[pila->cima--];
}

Programa de prueba:

#include <stdio.h>

int main(void)
{
  struct tpila pila;
  int elem;

  crear(&pila);
  if (vacia(&pila)) printf("\nPila vacia.");
  if (llena(&pila)) printf("\nPila llena.");
  apilar(&pila, 1);
  desapilar(&pila, &elem);
  return 0;
}

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.

En C y en algún otro lenguaje de programación puede modificarse el tamaño de un array si éste se define como un puntero al que se le reserva una dirección de memoria de forma explícita (mediante malloc en C). Sin embargo, a la hora de alterar dinámicamente esa región de memoria, puede ocurrir que no haya una región en la que reubicar el nuevo array (mediante realloc en C) impidiendo su crecimiento.

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:

struct tpila
{
  int clave;
  struct tpila *sig;
};

- Procedimiento de creación:

void crear(struct tpila **pila)
{
  *pila = (struct tpila *) malloc(sizeof(struct tpila));
  (*pila)->sig = NULL;
}

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

int vacia(struct tpila *pila)
{
  return (pila->sig == NULL);
}

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

void apilar(struct tpila *pila, int elem)
{
  struct tpila *nuevo;

  nuevo = (struct tpila *) malloc(sizeof(struct tpila));
  nuevo->clave = elem;
  nuevo->sig = pila->sig;
  pila->sig = nuevo;
}

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

void desapilar(struct tpila *pila, int *elem)
{
  struct tpila *aux;

  aux = pila->sig;
  *elem = aux->clave;
  pila->sig = aux->sig;
  free(aux);
}

Programa de prueba:

int main(void)
{
  struct tpila *pila;
  int elem;

  crear(&pila);
  if (vacia(pila)) printf("\nPila vacia!");
  apilar(pila, 1);
  desapilar(pila, &elem);

  return 0;
}

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

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

Si el usuario desea hacer un programa a prueba de balas puede probar el siguiente procedimiento de apilado, que simplemente comprueba si hay memoria para una asignación de memoria:

void apilar(struct tpila *pila, int elem)
{
  struct tpila *nuevo;


  if ((nuevo = (struct tpila *) malloc(sizeof(struct tpila))) == NULL)
    generar_error();
  else {
    nuevo->clave = elem;
    nuevo->sig = pila->sig;
    pila->sig = nuevo;
  }
}

Es obvio que si se llama al procedimiento generar_error es que el sistema se ha quedado sin memoria, o al menos se ha agotado la región de memoria que el sistema operativo y/o el compilador dedican para almacenar los datos que la ejecución del programa crea.

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:

struct nodo
{
  int clave;
  struct nodo *sig;
};
struct tpila
{
  int numero_elems; /* mantiene el numero de elementos */
  struct nodo *cima;
};

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.