Estructura de Datos : Colas Enlazadas

Definiciones

• La representación de colas secuenciales es eficiente si se procesara solamente una cola. La representación de colas enlazadas es la adecuada cuando se desean representar múltiples colas.
• Las ventajas de la representación enlazada de colas son :
  • No hay necesidad de reubicar información al insertar nuevos elementos o eliminar los existentes.
  • El programa corre hasta que haya nodos libres en el storage pool.
  • En el mismo storage pool se pueden representar pilas y cualquier otra estructura de datos con la misma estructura de nodo.
  • Tiempo de computacion menor que colas secuenciales.
  • Esta estructura de datos se conoce como Linked Queue en la literatura inglesa.

Representaciones

Representación Grafica ( Graphic Representation )

                   front                                                               rear
                     .                                                                   .                         +---+
                     .                                                                   .                       F |   | Variable con el frente de la cola
                     .                                                                   .                         +---+
                DATA V LINK        DATA   LINK        DATA   LINK                   DATA V LINK
              +-------------+    +-------------+    +-------------+               +-------------+                  +---+
 delete <---- |      |   *..|...>|      |   *..|...>|      |   *..|...> ..... ...>|      |   0  | <---- add      R |   | Variable con el fondo de la cola
              +-------------+    +-------------+    +-------------+               +-------------+                  +---+

Representación Conjunto ( Pool Representation )

• Pool de colas
  • F(i) = Front de la cola i, para 1 =< i =< n
  • R(i) = Rear de la cola i, para 1 =< i =< n
• Condiciones iniciales
  • F(i) = 0, para 1 =< i =< n
• Condiciones de borde
  • F(i) = 0, si y solo si la cola está vacia

     +---+         +---------+    +---------+    +---------+                   +---------+                        +---+
  F1 |   |........>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |               <........|   | R1
     +---+         +---------+    +---------+    +---------+                   +---------+                        +---+
     +---+         +---------+                   +---------+                                                      +---+
  F2 |   |........>|     | *.|...> ......... ...>|     | 0 |                                             <........|   | R2
     +---+         +---------+                   +---------+                                                      +---+
     +---+                                                                                                        +---+
  F3 | 0 |                                                                                               <........| 0 | R3
     +---+                                                                                                        +---+
     +---+         +---------+    +---------+                   +---------+                                       +---+
  F4 |   |........>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |                              <........|   | R4
     +---+         +---------+    +---------+                   +---------+                                       +---+
       .                                                                                                            .
       .                                                                                                            .
       .                                                                                                            .
       .                                                                                                            .
       .                                                                                                            .
     +---+         +---------+    +---------+    +---------+    +---------+                   +---------+         +---+
  Fn |   |........>|     | *.|...>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |<........|   | Rn
     +---+         +---------+    +---------+    +---------+    +---------+                   +---------+         +---+

Funciones

Inserciones ( Inserts )

Agrega el elemento o contenido C en la parte trasera de la queue i. Las variables i e C son de entrada.

• procedure ADDQ(i,C)
  • call GETNODE(Y)
  • DATA(Y) <---- C
  • LINK(Y) <---- 0
  • if F(i) = 0
    • then
      • R(i) <---- Y
      • F(i) <---- R(i)
    • else
      • R(i) <---- Y
      • LINK(R(i)) <---- Y
• end ADDQ

Eliminaciones ( Deletes )

Elimina el elemento que está al frente de la queue i y los datos del elemento eliminado se deja en C. La variable i es de entrada. La variable C es de salida.

• procedure DELETEQ(i,C)
  • if F(i) = 0
    • then
      • call QUEUE_EMPTY
    • else
      • X <---- F(i)
      • F(i) <---- LINK(X)
      • C <---- DATA(X)
      • call RETNODE(X)
• end DELETEQ