9.3. Colas
Curso: Programación en Pascal (v5), por Nacho Cabanes
9.3. Colas
Una "cola" es una estructura parecida a una "pila", pero en la que los datos entran por un lado y salen por el otro. Podemos compararla con una cola de un cine: cada persona que llega se coloca al final de la cola, pero se atiende en primer lugar a las que están en el extremo contrario, en la "cabeza", y esas son las primeras que abandonan la cola.
En informática, una "cola" contiene una colección de datos, se puede añadir un nuevo elemento mediante la operación "Encolar" (y quedará al final de la cola), o retirar el elemento del principio de la cola (y sólo ese) con la operación "Desencolar".
Al igual que hicimos con la pila, comenzaremos por crear una cola de números enteros, usando memoria estática (un array), y ése será nuestro punto de partida para crear la cola de forma dinámica.
(* COLA1.PAS, Ejemplo de cola estatica *) (* Parte de CUPAS5, por Nacho Cabanes *) program colaEstatica; var datos: array[1..10] of integer; cantidad: integer; procedure InicializarCola; begin cantidad := 0; end; procedure Encolar(nuevoDato: integer); begin cantidad := cantidad + 1; datos[cantidad] := nuevoDato; end; function Desencolar: integer; var dato, i: integer; begin dato := datos[1]; cantidad := cantidad - 1; for i := 1 to cantidad do datos[i] := datos[i+1]; Desencolar := dato; end; function CantidadDatos: integer; begin CantidadDatos := cantidad; end; { --- Programa de prueba --- } var n: integer; begin InicializarCola; WriteLn('Guardando 3 y 2...'); Encolar(3); Encolar(2); WriteLn('Los datos eran:'); WriteLn( Desencolar ); WriteLn( Desencolar ); WriteLn('Ahora introduce datos, 0 para terminar...'); repeat Write('Dato? '); ReadLn( n ); if n <> 0 then Encolar(n); until n = 0; WriteLn('Los datos eran:'); while CantidadDatos > 0 do WriteLn( Desencolar ); end.
Debería resultar fácil de seguir, aunque en este caso la lectura ("desencolar") es un poco más complicada, al tener que mover todos los datos hacia el principio cada vez que se toma el dato de la "cabeza". Pero además, al igual que ocurría con la pila estática, no es eficiente en cuanto al uso de memoria: si intentamos guardar más de 10 datos, el programa fallará. Si "sobredimensionamos", reservando espacio para (por ejemplo) 1000 datos, estaremos desperdiciando memoria en la gran mayoría de las ocasiones.
Si queremos crear esta cola usando memoria dinámica, de modo que pueda crecer tanto como sea necesario, aprovecharemos alguna de las ideas que ya habíamos visto para la pila, pero algunos detalles cambiarán:
- Seguiremos teniendo una serie de "nodos". Cada uno con un dato y un enlace al siguiente.
- Usaremos "new" para reservar memoria y "dispose" para liberarla.
- Al añadir datos, lo haremos al principio de la cola, así que deberemos cambiar la "cabeza".
- Cuando borramos datos, lo haremos del final, por lo que usaremos un "while" para recorrer toda la cola hasta encontrar el final de ésta (no es la única forma posible: cómo tenemos un contador, también podríamos emplear un "for").
Así, un planteamiento podría ser:
(* COLA2.PAS, Ejemplo de cola dinamica *) (* Parte de CUPAS5, por Nacho Cabanes *) program colaDinamica; type puntero = ^ nodo; nodo = record dato: integer; siguiente: puntero end; var cabeza: puntero; contadorDeDatos: integer; procedure InicializarCola; begin cabeza := nil; contadorDeDatos := 0; end; procedure Encolar(nuevoDato: integer); var nuevoNodo: puntero; posicionActual: puntero; begin { Reservamos espacio para un nuevo nodo } new(nuevoNodo); { Guardamos el dato en el } nuevoNodo^.dato := nuevoDato; { Sera el ultimo, sin "siguiente" } nuevoNodo^.siguiente := nil; { Y hacemos que este sea la nueva cabeza } if (cabeza = nil/span>) then cabeza := nuevoNodo { Puede ser el unico dato } else { O quiza debamos recorrer todos los existentes } begin posicionActual := cabeza; while (posicionActual^.siguiente <> nil) do posicionActual := posicionActual^.siguiente; posicionActual^.siguiente := nuevoNodo; end; { Y finalmente anotamos que tenemos un dato mas } contadorDeDatos := contadorDeDatos + 1; end; function Desencolar: integer; var nuevaCabeza: puntero; dato: integer; begin { Tomamos el dato de la cola } dato := cabeza^.dato; { Anotamos el siguiente, que sera la nueva cola } nuevaCabeza := cabeza^.siguiente; { Liberamos el espacio que ocupaba este nodo } dispose(cabeza); { Y finalmente "movemos" la cola a su nueva posicion } cabeza := nuevaCabeza; { Y anotamos que tenemos un dato menos } contadorDeDatos := contadorDeDatos - 1; { Y devolvemos lo que habiamos memorizado } Desencolar := dato; end; function CantidadDatos: integer; begin CantidadDatos := contadorDeDatos; end; { --- Programa de prueba --- } var n: integer; begin InicializarCola; WriteLn('Guardando 3 y 2...'); Encolar(3); Encolar(2); WriteLn('Los datos eran:'); WriteLn( Desencolar ); WriteLn( Desencolar ); WriteLn('Ahora introduce datos, 0 para terminar...'); repeat Write('Dato? '); ReadLn( n ); if n <> 0 then Encolar(n); until n = 0; WriteLn('Los datos eran:'); while CantidadDatos > 0 do WriteLn( Desencolar ); end.
Ejercicio propuesto 9.3.1: Crea un programa que permita guardar una cola de números reales. El usuario introducirá tantos datos como desee (usando 99999 para terminar), y en ese momento se le mostrará la media de los valores y todos los que están por encima de esa media.
Ejercicio propuesto 9.3.2: Crea una "cola de cadenas de texto". Utilízala para mostrar el contenido de un fichero de texto, paginado (haciendo una pausa tras cada 24 líneas de texto, hasta que el usuario pulse Intro, momento en el que se mostrarán las siguientes 24 líneas).
Actualizado el: 21-07-2014 17:19