Pilas

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íamospor 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 operacionesfundamentales, 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 mediantearrays 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 fijoa 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;
intelem;

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 decidirimplementar 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...