Tipos Abstractos de datos
(Pilas)

Definición

Una pila es una secuencia de ceri o más elementos de un mismo tipo, que solamente puede crecer y decrecer por uno de sus extremos. Se puede ver, como un caso particular de una lista, en la cual las operaciones posibles se restringen, permitiendo el acceso a la estructura únicamente por un extremo.

Diariamente vemos muchas situaciones que se pueden modelar mediante una pila. Por ejemplo, en un restaurante donde se colocan los platos unos encima de otros. Cuando llega un plato nuevo lo colocan sobre todos los existentes y cada vez que se necesita utilizar uno, toman el que se encuentra de primero(el ultimo que fue colocado).

Las Pilas se denominan tambien estructuras LIFO (Last-In-First-Out) debido a que la característica báasica es que el último en llegar es el primero en salir. Son muy utilizadas en programación, principalmente para evaluar expresiones, reconocer lenguajes, recorrer árboles y simularprocesos recursivos.

En todo momento , el unico elemento "visible " de la estructura es el último que se colocó. Se define entonces el Tope de la Pila como el punto donde se encuentra dicho elemento.

De la misma manera se define la Base de la Pila como el punto donse se encuentra el primer elemento incluido en la estructura.

Si una pila no tiene ningún elemento se dice que se encuentra vacía y no tiene sentido hablar, ni de su Tope ni de su Base. Por último se define la longitud de una Pila como el número de elementos que la conforman.

Una Pila es una lista lineal en la cual todas las inserciones y supresiones se hacen sólo en un extremo de la lista, esto es, una estructura de datos donde el último elemento almacenado es el primero que puede ser removido. Tambien puede ser ilustrada por un conjunto de libros en el piso. Solo el libro que esta arriba de la pila es el más accesible; nuevos libros solo pueden ser colocados en la parte de arriba.

Operaciones

De acuerdo con la descripción, se puede identificar la necesidad de una operación Inicializadora(crea pilas vacias), una Constructura(agrega un elemento a una pila), una Simplificadora(saca el primero de la pila) y dos Analizadoras(una, informa quién es el primero y la otra si la pila esta vacia).

---

Uso de las Pilas

Expresiones aritmeticas , como las permitidas en Pascal, estan en notación infija. Poe ejemplo: A*B+(C-D/E) es una expresion infija. Tales expresiones generalmente son convertidas por un compilador a una forma intermedia antes de generar el código objeto. Una de estas formas es la representación postfija. En la cual un operador aparece directamente después de sus operandos. Por ejemplo: la expresión A*(B+C) es ABC+* significando que es la multiplicación de dos operandos, donde el primero es A y el segundo es el resultado de la suma de B y C. La notación postfija muestra el orden en el cual las operaciones van a ser ejecutadas. Los parentesis no aparecen ya que el orden de evaluación de los resultados intermedios está decifrado en la expresión.

Para hacer la conversión de una expresión a su forma postfija es importanrte considerar la prioridad de sus operadores:

Utilizando el simbolo # para marcar el fin de la expresión.
Laexpresión infija es analizada carácter por carácter, considerando que las variables están formadas por uno de estos. Las variables se mueven directamente de la notación infija a la que será su representación postfija, los operadores se iran almacenando en un pila. Para ello es necesario comparar la prioridad del nuevo operador con el que está en la cabeza de la pila, y si este operador tiene mayor preferencia se coloca en la pila. En caso contrario, todos los operadores de la pila con mayor o igual prioridad a la del nuevo son sacados de ésta y puestos en la notación postfija, hasta encontrar un operador de menor prioridad. Entonces, el nuevo operador es guardado en la pila.

El paréntesis derecho ")" nunca se guarda en la pila, pero provoca quesalgan todos los operadores de la pila hasta encontrar un paréntesis izquierdo "(". El simbolo "#" es inicialmente puesto en la base de la pila. Su baja prioridad ( 0 ) es usada para forzar el proceso de la entrada de la expresión infija.

En la siguiente tabla se tiene el estado de la pila y de la representación postfija de la expresion : A*B+(C-D/E)# siguiendo este método:

Tomado del libro:

"Estructuras de datos (Un enfoque desde tipos abstractos)"
Jorge Villalobos, Alejandro Quintero, Mario Otero
Ediciones Uniandes