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) 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).