Unidad IV: Pilas y Colas

PILA

Una pila (stack en inglés) es una lista ordenada o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.

En cada momento solo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS. Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

·         Evaluación de expresiones en notación postfija (notación polaca inversa).

·         Reconocedores sintácticos de lenguajes independientes del contexto.

·         Implementación de recursividad.

Declaraciones de tipos para manejar pilas en C

Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para manejar listas, tan solo cambiaremos algunos nombres:

typedef struct_nodo {

int dato;

struct_nodo *siguiente;

} tipoNodo;

typedef tipoNodo *pNodo;

typedef tipoNodo *Pila;

tipoNodo es el tipo para declarar nodos, evidentemente.

pNodo es el tipo para declarar punteros a un nodo.

Pila es el tipo para declarar pilas.

           

            Es evidente, a la vista del gráfico, que una pila es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas.        Teniendo en cuenta que las inserciones y borradores en una pila se hacen siempre en un extremo, lo que consideramos como el primer elemento de la lista es en realidad el último elemento de la pila.

OPERACIONES

            Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

·         Crear: se crea la pila vacia (constructor).

·         Tamaño: regresa el número de elementos de la pila (size).

·         Apilar: se añade un elemento a la pila (push).

·         Desapilar: se elimina el elemento frontal de la pila (pop).

·         Cima: devuelve el elemento que está en la cima de la pila (top o peek).

·         Vacía: devuelve cierto si la pila está sin elementos o falso en caso de que contenga uno (empty).

Tipos de Pilas

El tipo base de la estructura FIFO (el primero en entrar es el primero en salir) es la cola y la combinación de las operaciones de la pila y la cola es proporcionado por el de que. Por ejemplo: el cambio de una pila en una cola en un algoritmo de búsqueda puede cambiar el algoritmo de búsqueda en primera profundidad (en inglés, DFS) por una búsqueda en amplitud (en inglés, BFS). Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.

Pilas alojadas en arreglos

Implementación de pilas con arreglos: resulta conveniente el almacenamiento secuencial para el tratamiento de pilas. Podemos tener una variable llamada TOPE que contenga el índice donde está ubicado el tope de la pila. Cuando la pila está vacía, se hace TOPE=0.

Por ejemplo: se puede definir una constante llamada CANTELEMENTOS que tenga el valor máximo de elementos que podrá contener la pila, un tope con la última posición, un valor a ser ingresado y el arreglo mismo:

#define CANTELEMENTOS 10;

int tope= -1; /*inicializamos a la variable tope con el valor -1 para que represente a la pila vacía porque el 1º elemento tiene índice 0.*/

 int pila[CANTELEMENTOS];

int valor;

            Para darte un ejemplo sencillo: supone que tienes una pila de 10 platos. El primer plato de la pila será el último en quitarse y el último plato de la pila será el primero en quitarse.

            Un arreglo constituye el depósito de los elementos de la pila. El rango del arreglo debe ser lo suficientemente amplio para poder contener el máximo previsto de elementos de la pila. Un extremo del arreglo se considera el fondo de la pila, que permanecerá fijo. La parte superior de la pila, tope o cima, estará cambiando dinámicamente durante la ejecución del programa. Además del arreglo, una variable entera nos sirve para tener en todo momento el índice del arreglo que contiene el elemento tope. Las declaraciones, procedimientos y funciones para representar el TAD pila, forman parte de la unidad pila.

·         Max_elem=…(Dependerá de cada realización).

·         Tipo_elem=…(Tipo de los elementos de la pila).

·         Pila= Registro.

·         Elem= arreglo [1…Max_elem] de Tipo_elem;

·         Tope= entero; FinRegistro.

Implementación de Procedimientos Recursivos mediante pilas

Un procedimiento o función contiene tanto variables locales como argumentos ficticios o parámetros. A través de los argumentos se transmiten datos en las llamadas a los subprogramas, o bien, se devuelven valores al programa o subprograma invocante. Además, el subprograma debe guardar la dirección de retorno al programa que realiza la llamada. En el momento en que termina la ejecución de un subprograma el control pasa a la dirección guardada.

Ahora, el subprograma es recursivo, entonces además de la dirección de retorno, los valores actuales de las variables locales y argumentos deben de guardarse ya que se usarán de nuevo cuando el subprograma se reactive. Supongamos que se ha llamado al subprograma P, que tiene llamadas a si mismo, es decir, es recursivo. El funcionamiento del programa recursivo P será: ü se crea una pila para cada argumento. ü se crea una pila para cada variable local. ü se crea una pila para almacenar la dirección de retorno. Cada vez que se hace una llamada recursiva a P, los valores actuales de los argumentos y de las variables locales se meten en sus pilas para ser procesadas posteriormente. Asimismo, cada vez que hay un retorno a P procedente de una llamada recursiva anterior, se restauran los valores de variables locales y argumentos de la simas de la pilas. Para la obtención de la dirección de retorno es de suponer que el procedimiento P contiene una llamada recursiva en la sentencia N. Entonces guarda en optra pila la dirección de retorno, que será la sentencia siguiente, la N+1. De tal forma que cuando el nivel de ejecución del procedimiento P actual termine, o sea, alcance la sentencia end final, usará dicha pila de direcciones para volver al nuevo nivel de ejecución.

COLAS

Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Representación de las Colas

Se las puede representar por listas enlazadas o por arrays

C= Q (1), Q (2),…, Q (n).

En cualquier caso se necesitan dos punteros

frente (f)

final(r)

y la lista o array de n elementos (LONGMAX)

Las operaciones que pueden realizar con una cola son:

·         Acceder al primer elemento de la cola.

·         Añadir un elemento al final de la cola.

·         Eliminar el primer elemento de la cola.

·         Vaciar una cola.

·         Verificar el estado de la cola: vacía o llena.

Operaciones

·         Crear: se crea cola vacía.

·         Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.

·         Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.

·         Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Cola Circulares

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden cosultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

Colas Doblemente Enlazadas

Como ocurre con toda representación estática, una de las principales desventajas es que hay que prever un máximo de elementos, y de ese máximo no se puede pasar. La realización de una cola mediante una lista enlazada permite ajustarse exactamente al número de elementos de la cola. Esta implementación con las listas enlazadas utiliza dos punteros que acceden a la lista, el puntero frente y el puntero final. Cola implementada con listas enlazadas, el puntero final referencia al último nodo que fue añadido. En esta representación no tiene sentido la operación que indica si la cola está llena. Al ser una estructura dinámica crece y decrece según las necesidades. La definición de cola usando listas enlazadas serían:

·         Tipo_elto: (Tipo del campo información de cada nodo).

·         Nodo: Registro.

·         Elto: Tipo_elto;

·         Sig: hNodo;

·         Fregistro; Cola:

·         Registro frente: hNoho;

·         final: hNodo; Fregistro;

Tipos de Colas

a)     Colas Circulares (anillos): en las que el último elemento y el primero están unidos.

b)     Colas de Prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

a.    Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.

b.    Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

c)     Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las Bicolas se puede hacer con un array ciruclar con inicio y fin que apunten a cada uno de los extremos. Hay variantes:

a.    Bicolas de entrada restringida: son aquellas donde la inserción sólo se hace por el final, aunque se puede eliminar al inicio ó al final.

b.    Bicolas de salida restringida: son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

Aplicaciones de Colas

Las colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).

Si esta trabajando en un sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su “cola de trabajo”. Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada / salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.