Capítulo 7

.
Cola o FIFO (First In First Out)
.
Una cola es una estructura de acceso restrictivo con dos operaciones asociadas:

• encolar - pone un elemento en la cola
• desencolar - saca un elemento de la cola

El orden en que entran y salen los elementos de la cola es FIFO: "Primero Entrado, Primero Salido". Al igual que la cola que se forma en la caja del supermercado, el primero que llegue será el primero que salga. Analicemos el código de untColas (unit) para luego explicar la lógica para encolar y desencolar.

untColas.pas

   1:
   2:unit untColas;
   3:
   4:interface
   5:type
   6:   PNodo = ^Nodo;
   7:   Nodo = record
   8:      info:integer;
   9:      sig: PNodo;
  10:   end;
  11:
  12:   procedure encolar(var p:PNodo;v:integer);
  13:   function desencolar(var p:PNodo):integer;
  14:
  15:implementation
  16:
  17:// : 
  18:// la seccion implementation se define mas abajo
  19:// :
  20:

Utilizamos el mismo tipo de nodo. La operación de encolar la definimos como un procedimiento que recibe el puntero a la cola y el valor a encolar. La operación de desencolar la definimos como una función que recibe el puntero a la cola y retorna el valor que (respetando el orden de la cola) corresponde sacar.

La lógica para poder implementar la cola será mantener una "lista circular". Esto implica que "el siguiente del último elemento debe apuntar al primer elemento" de la lista. Y el puntero de la cola siempre debe apuntar al último nodo encolado.

Veamos esto graficamente. La siguiente secuencia encola los valores 3, 4 y luego 5.

Al inicio la cola (p) no tiene elementos. Entonces se crea el nodo (para el valor 3) y se asigna a su siguiente la dirección del mismo nodo. p apunta al último (que en este caso coincide con el primero).

Luego se encola el valor 4. Se crea el nuevo nodo y se lo asigna al siguiente (sig) de p (que todavía apunta al 3). Al siguiente del nuevo nodo se le asigna p (todavía en 3) y por último a p se le asigna la dirección del nuevo nodo para que p apunte al último entrado.

Para encolar el 5 es la misma operatoria.

Viendo el gráfico podemos notar que el siguiente de p siempre es el primer elemento que entró a la cola. Por lo tanto, si queremos desencolar un elemento, el que tiene que salir será el siguiente de p.

Veamos como desencolar:

Esta secuencia muestra como desencolamos un valor (corresponde salir al 3). Antes que nada guardamos el nodo que tiene que salir en una variable aux (lo accedemos como el siguiente de p). Luego al siguiente de p le asignamos el siguiente del siguiente de p (en este caso el 4). Por último liberamos aux.

Para desencolar otro valor (en este caso 4) el procedimiento es el mismo.

Veamos los diagramas.

En el procedimiento encolar recibimos el puntero a la cola (p) y el valor que queremos encolar (v). El puntero p siempre apuntará al último elemento encolado. Creamos el nuevo nodo (nuevo) y le asignamos el valor v. Luego preguntamos si p es NIL para saber si la cola no tiene ningún elemento. Si se verifica entonces al siguiente de nuevo le asignamos nuevo (la cola tiene un único elemento que se apunta a sí mismo). Si no se verifica entonces al siguiente de nuevo le asignamos el siguiente de p, ya que vamos a modificar a p para que apunte al último elemento y (recordemos) el siguiente del último debe apuntar al primero.

En la función desencolar guardamos en ret el valor que tenemos que retornar: el valor del siguiente de p. Luego preguntamos si el siguiente de p es igual a p. En este caso estaremos desencolando el último (y único) elemento de la cola. Si no se verifica entonces guardamos el siguiente de p en aux y al siguiente de p le asignamos el siguiente de aux (lo que es lo mismo: el siguiente del siguiente). Por último libero aux.


Veamos ahora la implementación de untColas.

untColas.pas (implementación)

   1:
   2:procedure encolar(var p:PNodo;v:integer);
   3:var nuevo:PNodo;
   4:begin
   5:
   6:   new(nuevo);
   7:   nuevo^.info:=v;
   8:
   9:
  10:   if( p=NIL ) then begin
  11:      nuevo^.sig:=nuevo;
  12:   end else begin
  13:      nuevo^.sig:=p^.sig;
  14:      p^.sig:=nuevo;
  15:   end;
  16:
  17:   p:=nuevo;
  18:end;
  19:
  20:function desencolar(var p:PNodo):integer;
  21:var ret:integer; aux:PNodo;
  22:begin
  23:   ret:=(p^.sig)^.info;
  24:   if( p = p^.sig ) then begin
  25:      dispose(p);
  26:      p:=NIL;
  27:   end else begin
  28:      aux:=p^.sig;
  29:      p^.sig:=aux^.sig;
  30:      dispose(aux);
  31:   end;
  32:   desencolar:=ret;
  33:end;
  34:
  35:end.
  36:

Algoritmos y Estructuras de Datos UTN - UBA.