La Estructura Pila

Descripción

Luego de la Lista, que ya vimos, la Pila es otra estructura básica e importante en los lenguajes de programación. Aunque lenguajes como C no tienen definido este TDA como "built-in", es decir parte del lenguaje.

Una pila es una estructura para almacenar información en la misma forma en la que nosotros apilamos físicamente objetos, por ejemplo "cajas" o papeles. Es decir, uno "encima" del otro.

Apilar un elemento es ponerlo arriba de la "pila", en el tope.

En cualquier momento el elemento disponible para ver o retirar es el tope. Si bien físicamente en una pila de libros podríamos sacar uno del "medio" o hasta el de abajo de todo, esa no es una característica del TDA pila.

Usos

Vemos acá algunos usos de la Pila:

• El historial de visitas del browser (botón "volver), va apilando las paginas que visitamos.
• Igual que la lista de acciones de un programa, para poder hacer "undo" o deshacer
• En lenguajes de programación, se utiliza para el manejo de contextos de funciones (ya vimos algo de esto en la Unidad 1 de manejo de memoria)
• Evaluación de operaciones matemáticas con pilas.

Tipo de Dato Abstracto

Vamos a definir entonces el TDA Pila a través de sus operaciones:

tipo abstracto Pila<E>

operacion crearPila() -> Pila

operacion liberarPila(Pila)

// inserta un nuevo elemento en el tope de la pila

operacion apilar(Pila p, E elemento)

// "saca" el elemento del tope de la pila

operacion desapilar(Pila p) -> E

// devuelve el elememento en el tope (sin sacarlo)

operacion tope(Pila p) -> E

// indica si la pila está vacía

operacion vacia(Pila p) -> boolean

Como vemos acá, en realidad es una estructura bastante más simple que las listas. Simplemente necesitamos las 4 operaciones (apilar, desapilar, tope, vacia) para operarla.

Apilar

Inserta el nuevo elemento en el tope de la pila.

Luego del apilar, la función "tope" debería devolver el elemento que acabamos de apilar. Y vacia() debería devolver false.

A esto se le suele llamar post condiciones de una operación del TDA. Define el contrato del TDA sin exponer los detalles internos.

Desapilar

Devuelve el elemento en el tope, pero retirándolo de la estructura.

Implementacion

La pila se puede implementar, como la lista, tanto con arrays como con nodos enlazados. Aunque, a diferencia de la lista, la pila no necesariamente es indexada, y de hecho solo podemos acceder al tope de los elementos.

Con lo cual, las desventajas de una lista enlazada (costo alto de tiempo para ubicar un elemento arbitrario -acceso aleatorio-) no aplicarían aqui.

Pila basada en nodos enlazados

Vamos a ver acá una implementación basada en nodos enlazados.

Es "similar" a la lista enlazada. Vamos a necesitar definir:

• NodoPila: una estructura para modelar los nodos. Cada nodo tendrá:
  • el dato que aloja
  • una referencia al próximo elemento (que sería el que está más abajo en la pila)
• Pila: por otro lado, con los nodos no nos alcanza, necesitamos tener una estructura para la pila con:
  • tope: una referencia al tope actual de la pila.

Acá vemos un diagrama:

// TODO: mostrar implementación en C de la pila y analizar complejidad de las operaciones