PILAS

Las pilas y las colas son dos de las estructuras de datos más utilizadas. Se trata de dos casos particulares de las estructuras lineales generales (secuencias o listas) que, debido a su amplio ámbito de aplicación, conviene ser estudiadas de manera independiente.

PILAS. FUNDAMENTOS

La pila es una lista de elementos caracterizada porque las operaciones de inserción y eliminación se realizan solamente en un extremo de la estructura. El extremo donde se realizan estas operaciones se denomina habitualmente 'cima' (top en nomenclatura inglesa).

Dada una pila P=(a,b,c,...k), se dice que a, que es el elemento más inaccesible de la pila, está en el fondo de la pila (bottom) y que k, por el contrario, el más accesible, está en la cima.

Las restricciones definidas para la pila implican que si una serie de elementos A,B,C,D,E se añaden, en este orden a una pila, entonces el primer elemento que se borre de la estructura deberá ser el E. Por tanto, resulta que el último elemento que se inserta en una pila es el primero que se borra. Por esta razón, se dice que una pila es una lista LIFO (Last In First Out, es decir, el último que entra es el primero que sale).

Un ejemplo típico de pila lo constituye un montón de platos, cuando se quiere introducir un nuevo plato, éste se pone en la posición más accesible, encima del último plato. Cuando se coge un nuevo plato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido.

Otro ejemplo natural de la aplicación de la estructura pila aparece durante la ejecución de un programa de ordenador, en la forma en que la máquina procesa las llamadas a los procedimientos. Cada llamada a un procedimiento (o función) hace que el sistema almacene toda la información asociada con ese procedimiento (parámetros, variables, constantes, dirección de retorno, etc..) de forma independiente a otros procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y que toda esa información almacenada pueda ser recuperada convenientemente cuando corresponda. Como en un procesador sólo se puede estar ejecutando un procedimiento, esto quiere decir que sólo es necesario que sean accesibles los datos de un procedimiento (el último activado que está en la cima). De ahí que la estructura pila sea muy apropiada para este fin.

Como en cualquier estructura de datos, asociadas con la estructura pila existen una serie de operaciones necesarias para su manipulación, éstas son:

• Crear la pila.
• Comprobar si la pila está vacia. Es necesaria para saber si es posible eliminar elementos.
• Acceder al elemento situado en la cima.
• Añadir elementos a la cima.
• Eliminar elementos de la cima.

La especificación correcta de todas estas operaciones permitirá definir adecuadamente una pila.

Representacion de las pilas

Los lenguajes de programación de alto nivel no suelen disponer de un tipo de datos pila. Aunque por el contrario, en lenguajes de bajo nivel (ensamblador) es posible manipular directamente alguna estructura pila propia del sistema. Por lo tanto, en general, es necesario representar la estructura pila a partir de otros tipos de datos existentes en el lenguaje.

La forma más simple, y habitual, de representar una pila es mediante un vector unidimensional. Este tipo de datos permite definir una secuencia de elementos (de cualquier tipo) y posee un eficiente mecanismo de acceso a la información contenida en él.

Al definir un array hay que determinar el número de índices válidos y, por lo tanto, el número de componentes definidos. Entonces, la estructura pila representada por un array tendrá limitado el número de posibles elementos.

Se puede definir una pila como una variable:

donde T es el tipo que representa la información contenida en la pila (enteros, registros,etc.)

El primer elemento de la pila se almacenará en Pila[1], será el fondo de la pila, el segundo elemento en Pila[2] y así sucesivamente. En general, el elemento i-úsimo estará almacenado en Pila[i].

Como todas las operaciones se realizan sobre la cima de la pila, es necesario tener correctamente localizada en todo instante esta posición. Es necesaria una variable, cima, que apunte al último elemento (ocupado) de la pila.

Con estas consideraciones prácticas, se puede pasar a definir las operaciones que definen la pila.

Crear pila:

Es necesario definir el array que permitirá almacenar la información y la variable que indica la posición de la cima. Además tendremos que inicializar cima al valor 0, indicando que la creación implica que la pila está vacía.

(1) Variables

   Pila: array [1..n] de T

   cima: 0..n 

(2) Asignación de pila vacía

   cima <-- 0 

Comprobar si la pila está vacía:

Esta operación permitirá determinar si es posible eliminar elementos.

Algoritmo Pila_vacia

   Entrada

    cima: 0..n

   Salida (cierto, falso)

   Inicio

     si cima=0 entonces devolver(cierto)

     sino devolver(falso)

   Fin 

Operación de inserción

La operación de inserción normalmente se conoce por su nombre inglés push. La operación aplicada sobre una pila y un valor x, inserta x en la cima de la pila. Esta operación está restringida por el tipo de representación escogido. En este caso, la utilización de un array implica que se tiene un numero máximo de posibles elementos en la pila, por lo tanto, es necesario comprobar, previamente a la inserción, que realmente hay espacio en la estructura para almacenar un nuevo elemento. Con esta consideración el algoritmo de inserción sería:

Algoritmo Apilar

   Entradas

    x: T (* elemento que se desea insertar *)

    Pila: array [1..n] de T

   Salidas

    Pila, cima

   Inicio

    si cima=n entonces "Pila llena"

    sino

       cima       <-- cima+1

       Pila[cima] <-- x

    fin_sino

   Fin 

Operación de eliminación

La operación de borrado elimina de la estructura el elemento situado en la cima. Normalmente recibe el nombre de pop en la bibliografía inglesa. El algoritmo de borrado sería:

Algoritmo Desapilar

   Entradas

    Pila: array [1..n] de T

   Salidas

    Pila, cima, x

   Inicio

    si NO(Pila_vacia) entonces

       x    <-- Pila[cima]

       cima <-- cima-1

   Fin 

(recordemos que la función Pila_vacia nos devuelve un valor lógico (cierto o falso) que en este caso nos sirve como condición para el si)

En todos los algoritmos se podría suponer que las variables Pila y cima, lo mismo que n, son globales y, por lo tanto, no sería necesario declararlas como entradas o salidas.

APLICACIONES DE LAS PILAS

Evaluación de expresiones aritméticas

Sabemos que, para evitar ambigüedad y saber en qué orden se deben evaluar las expresiones, se define en los lenguajes de programación una prioridad para cada posible operador. Además, si dos operadores tienen la misma prioridad se evita el conflicto evaluando éstos de izquierda a derecha. También está permitido el uso de paréntesis para establecer un orden concreto de evaluación, independientemente de la precedencia de los operadores. Todos estos condicionamientos son debidos al tipo de notación empleada, la llamada notación infija, donde los operadores se situan entre los operandos sobre los que actua. De manera que, según sabemos, la siguiente expresión:

se evaluaría como sigue:

El problema es cómo genera el compilador el código necesario para calcular esta expresión. La solución se facilita si se modifica el tipo de notación empleada para representar la expresión. Es conveniente pasar a notación posfija (el operador se situa detrás de los operandos sobre los que actua) durante el proceso de compilación. Las ventajas de la notación posfija son varias: no hace falta paréntesis, no hace falta definir prioridad de operadores y la evaluación final de la expresión se realiza fácilmente con un simple recorrido de izquierda a derecha de la expresión.

Siguiendo la notación posfija, la expresión del ejemplo anterior se podría escribir como:

Para realizar el cálculo de las expresiones en notación posfija, hay que tener en cuenta que al leerlas de izquierda a derecha, lo primero que se lee son los operandos y despues el operador. Por ello, es necesario almacenar la información leida hasta que se determine que operador hace uso de ella. Además, los operadores actuan sobre los últimos operandos leidos. De manera que, conviene recuperar la información en sentido inverso a como se almacena. Por esa razón, parece natural emplear una pila como estructura de almacenamiento de información.

El esquema algorítmico para la evaluación de expresiones dadas en notación posfija consistirá en ir analizando secuencialmente la expresión. Si se detecta un operando, se inserta en la pila y si se detecta un operador, éste se evalua utilizando los operandos necesarios de la pila y situando, de nuevo, el resultado en la pila, puesto que será un operando para otro operador posterior. Este proceso es mucho más simple que intentar la evaluación directa a partir de la expresión en notación infija.

Algoritmo para evaluar expresiones

  Inicio

   leer expresion

   mientras (hay elementos en la expresion) hacer:

      si elemento = operando entonces apilar(elemento)

         sino:

            op <-- numero de operandos del operador

     repetir op veces

     desapilar y almacenar

     aplicar el operador sobre los operandos desapilados

     apilar(resultado)

         fin_sino

   fin_mientras

  Fin 

Asociado con el problema de las expresiones, ya comentado, estaría el problema de cambiar de notación la expresión. Cómo pasar de la notación infija empleada durante la escritura del programa (que es cómoda y habitual para el usuario) a la notación posfija, más conveniente para automatizar los procesos de cálculo. Para realizar este proceso, de nuevo resulta adecuada la utilización de una pila.

Para el proceso de traducción de la expresión hay que tener en cuenta una serie de aspectos: los operandos aparecen en el mismo orden en la notación infija y en la posfija, con lo que no hay que realizar ningún tipo de acción específica cuando, al leer la expresión, se detecta un operando, simplemente proporcionarlo como salida; los operadores, por su parte, sí que cambian de posición al cambiar de notación. En la notación infija, el operador se situa antes que uno de los operandos, mientras que en la notación posfija siempre va detrás. Por esa razón, ahora es conveniente almacenar los operadores, no los operandos, hasta el momento en que halla que proporcionarlos como salida. Además, hay que tener en cuenta que la entrada de datos es una expresión en la que los operadores tienen asignadas distintas prioridades, estas prioridades también se deben tener en cuenta en el momento de la traducción.

El siguiente algoritmo permite traducir una expresión escrita en notación infija a notación posfija. Para simplificar la tarea, se ha supuesto que la expresión de entrada no tiene paréntesis (lo que complicaría ligeramente el proceso) y que tenemos un proceso paralelo que permite extraer cada uno de los elementos de la expresión (identificadores de variable, constantes, funciones, etc...):

Algoritmo Infija_Posfija

  Entrada

   expresion: cadena

  Variables

   x, y: caracteres

   fin : (cierto, falso)

   P   : Pila

  Inicio

   P <-- Crear() (* inicializar pila *)

   x <-- sig_elemento(expresion)

   mientras no_final(expresion) hacer

      si x es operando entonces salida(x)

      sino

         fin <-- falso

         (* analizamos prioridades de operadores *)

         mientras (no Vacia(P)) y (no fin) hacer

         si (prioridad(x) <= prioridad(Cima(P)) entonces

            y <-- Desapilar(P)

            salida(y)

         fin_si

         sino

            fin <-- cierto

         fin_mientras

         Apilar(P,x)

      fin_sino

      x <-- sig_elemento(expresion)

   fin_mientras

   (* se ha terminado la expresion, vaciar la pila *)

   mientras (no Vacia(P)) hacer

      y <-- Desapilar(P)

      salida(y)

   fin_mientras

  Fin 

Pilas múltiples

   Hasta ahora se ha tratado solamente con la representación en memoria y manipulación de una única pila o cola. Se han visto dos representaciones secuenciales eficientes para dichas estructuras. Sin embargo, en ocasiones, es preciso representar varias estructuras utilizando el mismo espacio de memoria.

   Supongamos que seguimos transformando las estructuras de datos en representaciones secuenciales, tipo array. Si sólo hay que representar dos pilas sobre un mismo array A[1..n], la solución puede resultar simple. Se puede hacer crecer las dos pilas partiendo desde los extremos opuestos del array, de forma que A[1] será el elemento situado en el fondo de la primera pila y A[n] el correspondiente para la segunda pila. Entonces, la pila 1 crecerá incrementando los índices hacia A[n] y la pila 2 lo hará decrementando los índices hacia A[1]. De esta manera, es posible utilizar eficientemente todo el espacio disponible.

   Si se plantea representar más de dos pilas sobre ese mismo array A, no es posible seguir la misma estrategia, ya que un array unidimensional sólo tiene dos puntos fijos, A[1] y A[n], y cada pila requiere un punto fijo para representar el elemento más profundo.

   Cuando se requiere representar secuencialmente más de dos pilas, por ejemplo m pilas, es necesario dividir en m segmentos la memoria disponible, A[1..n], y asignar a cada uno de los segmentos a una pila. La división inicial de A[1..n] en segmentos se puede hacer en base al tamaño esperado de cada una de las estructuras. Si no es posible conocer esa información, el array A se puede dividir en segmentos de igual tamaño. Para cada pila i, se utilizará un índice f(i) para representar el fondo de la pila i y un índice c(i) para indicar dónde está su cima. En general, se hace que f(i) esté una posición por debajo del fondo real de la pila, de forma que se cumpla la condición f(i)=c(i) si y solamente si la pila i está vacía.

   La discusión realizada para el caso de pilas múltiples sirve de base para poder establecer estrategias de manipulación de varias colas en un mismo array, incluso la combinación de estructuras pilas y colas sobre la misma localización secuencial