Curso de Estructuras de Datos y Algoritmos / Colas

Colas en C

Las colas son un tipo de estructura dinámica denominada es:FIFO (first in, first out; el primero que entra es el primero que sale). Es un tipo de lista dinámica la cual la podemos imaginar de este modo: cuando realizamos una fila o cola para ir al cine, siempre nos ponemos de último en la fila y el primero que llegó es el primero en ser atendido, cuando este es atendido sale de la fila y avanza la fila.

Con este sencillo ejemplo podemos darnos la idea de lo que realmente es una cola, pero ahora hablando en términos informáticos: una cola es una lista dinámica en la cual las peticiones son acogidas o realizadas en el orden en que entran, ejemplo de esto es una impresora que imprime los documentos en el orden que se le envíen a la misma.

En este artículo, realizaremos todos los ejemplos en lenguaje C, para comprender los ejemplos las personas deben de tener cierto conocimiento en listas dinámicas y de punteros en el lenguaje C.

Declaración de una cola

---

Para declarar una cola en C, declaramos un nodo que servirá para crear los demás:

  struct nodo {
      int dato;
      struct nodo *puntero;
  };

Para mayor comodidad creamos con typedef un alias "Nodo" para "struct nodo":

  typedef struct nodo Nodo;

Esto nos crea un tipo de dato, no una variable ni otra cosa parecida para declarar una variable podemos realizar lo siguiente:

  int main() {
      Nodo *primero = malloc(sizeof(Nodo));
      Nodo *ultimo = malloc(sizeof(Nodo));

      /*Esto es incorrecto: ¡se pierde el nodo recién reservado! */
      primero = NULL;
      ultimo = NULL;

      return;
  }

Con lo anterior creamos dos punteros de las colas el primero y el último y usamos la función malloc() para reservar para el nodo tanto espacio como necesite (sizeof(Nodo))

Al declarar la cola, lo que realmente creamos es un puntero a esta y como esta está vacía la declaramos con NULL, para que el puntero no apunte a "nada".

En este momento tenemos una cola vacía, y ahora definiremos las dos operaciones básicas de una cola: insertar y leer (procesar).

Insertar

Como habíamos hablado antes para insertar nodos en una cola, ésta tiene un orden específico, todos los nodos se posicionan al final de la cola, a excepción del primero. lllplp

Insertar un nodo en una cola vacía

Para insertar un nodo en una cola vacía debemos de declarar un nodo

  Nodo *nodo;

Después de esto supongamos la existencia de una variable dato, la cual tiene el valor del nodo a insertar:

  nodo->dato = dato;

Ahora debemos de inicializar el puntero del nodo a NULL, porque a este no le seguirá otro.

  nodo->puntero = NULL;

En este momento viene la parte que involucra la cola debemos de hacer que la cola apunte al nuevo nodo, para esto hacemos que primero y último (anteriormente declarados apunten al nuevo nodo).

  
     primero=nodo;
     ultimo=nodo;

Insertar un nodo en una cola no vacía

En este caso como hablamos antes debemos de insertar los nodos en un orden específico en este caso la cola se supone no vacía y debemos de desarrollar un algoritmo que funcione sea que la cola solo tenga un nodo o tenga n nodos. En este momento ahora se puede explicar porqué la creación de un puntero primero y otro último. Como la cola tiene un orden específico necesitamos saber cuál es la cabeza de la cola, que es el primer nodo insertado en la cola; luego el puntero ultimo es el que nos permitirá movilizarnos por la cola ya que este siempre apuntará al último nodo ingresado en la cola. Entonces lo primero que debemos de hacer para insertar un nodo en una cola no vacía es llevar a ultimo al último nodo en la cola:

    while(ultimo->puntero != NULL)
         ultimo=ultimo->siguiente;

Habiendo hecho este bucle desplazamos a ultimo hasta el último nodo ingresado en la cola, ahora debemos de declarar el nodo a insertar:

 
    Nodo *nodo;
    nodo->dato=dato;
    nodo->puntero=NULL;

Ahora debemos de hacer que ultimo->puntero apunte a nodo:

  
   ultimo->siguiente=nodo;

Y por último actualizamos ultimo:

  ultimo=nodo;