ESTRUCTURA DE DATOS PILAS Y COLAS

PILAS Y COLAS

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 en los 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 se conoce 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 se denomina TOPE. Está variable se utiliza para indicar el último elemento que se insertó en la pila.

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áximo establecido. 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 con exactitud el número de elementos a tratar, y siempre existe la posibilidad de que ocurra un error de desbordamiento.

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 una pila 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.

Conclusiones

Finalmente podemos concluir que las pilas son necesarias en este tipo de aplicaciones por lo siguiente;

Permiten guardar la dirección del programa, o subprograma, desde donde se hizo la llamada a otros subprogramas, para regresar posteriormente y seguir ejecutándolo a partir de la instrucción inmediata a la llamada.

Permiten guardar el estado de las variables en el momento en que se hace la llamada, para seguir ocupándolas al regresar del subprograma.

Doble Cola

Una doble cola o bicola es una generalización de una ED tipo cola. En una doble cola, los elementos se pueden insertar o eliminar por cualquiera de los dos extremos. Es decir, se pueden insertar y eliminar valores tanto por FRENTE como por el FINAL de la cola.

Existen dos variantes de las dobles colas:

Doble cola (DC) con entrada restringida

La primera permite hacer eliminaciones por cualquiera de los dos extremos, mientras que las inserciones sólo por el FINAL

...