Rosa

Pilas y Colas
Capítulo 3

Pilas


Una pila representa una estructura lineal de datos en que se puede agregar o quitar elementos únicamente por uno de los dos extremos. En consecuencia, los elementos de una pila se eliminan en el orden inverso al que se insertaron. Debido a está característica, se le conoce como estructura LIFO (last input, first output). Existen muchos casos prácticos enlos que se utiliza la idea de pila: Ejemplo; pila de platos, en el supermercado latas. Las pilas con estructuras lineales como los arreglos, ya que sus componentes ocupan lugares sucesivos en la ED y c/u tienen un único sucesor/predecesor, con excepción del primero/último.






 Definición de Pila  Una colección de datos a los cuales se les puede acceder mediante un extremo, que seconoce generalmente como tope.

Representación de Pilas


 

Las pilas no son estructuras fundamentales de datos; es decir no están definidas como tales en los lenguajes de programación. Para su representación requieren de otras EDs, como: Arreglos Listas



OC/SG utilizan arreglos. Es importante definir el tamaño de la máximo de la pila, así como una variable auxiliar que sedenomina TOPE. Está variable se utiliza para indicar el último elemento que se insertó en la pila. (Figs.)

PILAS

Representación de pilas
 Al utilizar arreglos para implementar pilas se

tiene la limitación de que se debe reservar el espacio en memoria con anticipación. Una vez dado un máximo de capacidad a la pila no es posible insertar un número de elementos mayor que el máximoestablecido. Si esto ocurre, en otras palabras si la pila esta llena y se intenta insertar un nuevo elemento, se producirá un error conocido como desbordamiento –overflow

Posibles soluciones
 Una posible solución a este tipo de

inconvenientes consiste en definir pilas de gran tamaño, pero esto resultará ineficiente y costoso si solo se utilizarán algunos elementos. No siempre es viable saber conexactitud el número de elementos a tratar, y siempre existe la posibilidad de que ocurra un error de desbordamiento.

Otra solución


Consiste en usar espacios compartidos de memoria para la implementación de pilas. Supongamos que se necesitan dos pilas, c/u con un tamaño máximo de N elementos. Se definirá entonces un arreglo unidimensional de 2*N elementos, en lugar de 2 arreglos de Nelementos c/u.

Figura muestra la PILA 1 ocupará desde la posición 1 en adelante, mientras que la PILA 2 ocupará desde la posición 2*N hacias atrás (2*N-1..) Si en algún momento del proceso la PILA 1 necesitará más espacio del que realmente tiene -N- y en ese momento la PILA 2 no tiene ocupados todos sus N lugares entonces sería posible agregar elementos a la PILA1 sin caer en un error dedesbordamiento. Algo similar podría suceder con la PILA 2.

Espacios Compartidos

Error y Operaciones
Otro error que se puede presentar es tratar de eliminar un elemento de un pila vacía. Este tipo de error se le conoce como subdesbordamiento –underflowOperaciones con pilas Insertar un elemento –push- en la pila Eliminar -pop – de la pila Pila_vacía Pila_llena

 Considerando que se tiene unapila con una capacidad para almacenar un núm máximo de elementos –MAX- y que el último de ellos se indica con TOPE, a continuación se presentan los algoritmos de las operaciones mencionadas. Si la pila está vacía, entonces TOPE es igual a 0.

Algoritmo Pila_vacía

Algoritmo Pila_llena

Algoritmo Pone

Algoritmo Quita

Ejemplo Días de la semana

Ejemplo Días de la semana

EjemploDías de la semana

Aplicaciones de Pilas


Las pilas son un EDs muy usadas en la solución de diversos tipos de problemas, en el área de computación. Algunos de los casos más representativos de aplicación de las mismas son:  Llamadas a subprogramas  Recursividad  Tratamiento de expresiones aritméticas  Ordenación

Llamadas a subprogramas
 Cuando se tiene un programa que llama a...