Una cola es una estructura de datos lineal con restricciones específicas en cuanto a cómo se pueden añadir y eliminar elementos. Piensa en las colas de la vida real, como una fila de personas esperando su turno.

Las colas se caracterizan por el principio de "primero en entrar, primero en salir" (FIFO - First In, First Out). Esto significa que el primer elemento que se añade a la cola es el primero en ser eliminado.

Definición Formal de una Cola

• Nombre del Tipo: Cola (Queue)
• Conjunto de Datos: Una lista lineal finita con cero o más elementos.
• Conjunto de Operaciones: Para una cola Q de longitud máxima MaxSize y un elemento item de tipo ElementType:
  • Queue CreateQueue(int MaxSize): Crea una cola vacía de tamaño máximo MaxSize.
  • int IsFullQ(Queue Q, int MaxSize): Comprueba si la cola está llena.
  • void AddQ(Queue Q, ElementType item): Inserta el elemento item en la cola Q.
  • int IsEmptyQ(Queue Q): Comprueba si la cola está vacía.
  • ElementType DeleteQ(Queue Q): Elimina y devuelve el elemento del frente de la cola Q.

Implementación de Colas

1. Implementación Secuencial (Usando un Arreglo)

Una implementación secuencial de una cola generalmente utiliza un arreglo unidimensional y dos índices: front para apuntar al primer elemento y rear para apuntar a la posición del último elemento.

   #define MAX_SIZE 100 // Tamaño máximo de la cola

   typedef struct {
       ElementType data[MAX_SIZE]; // Arreglo para almacenar los elementos
       int rear;                   // Índice del último elemento
       int front;                  // Índice del primer elemento
   } Queue;
   

El Problema del Arreglo Circular

Al insertar y eliminar elementos repetidamente, podemos encontrarnos en una situación donde hay espacio disponible en el arreglo, pero la cola parece estar llena. Esto ocurre porque rear puede "adelantar" a front.

Para resolver este problema, se utiliza un enfoque de "arreglo circular". Cuando rear o front llegan al final del arreglo, se "envuelven" al principio.

¿Por qué el último espacio queda inutilizado?

Si utilizamos la diferencia entre rear y front para contar los elementos, solo podemos representar MaxSize - 1 estados distintos, lo cual es insuficiente para representar los MaxSize estados posibles (de completamente vacío a completamente lleno).

Soluciones para el Espacio Inutilizado:

1. Reducir el tamaño útil: Solo usar MaxSize - 1 espacios del arreglo.
2. Usar una marca adicional: Mantener una variable extra (como size o tag) para rastrear el número de elementos o el estado de la cola.

Código de Inserción (AddQ)

Este código implementa la adición de un elemento a la cola usando un arreglo circular.

   void AddQ(Queue *q, ElementType item) {
       // Comprobar si la cola está llena (usando el principio del arreglo circular)
       if ((q->rear + 1) % MAX_SIZE == q->front) {
           printf("Error: La cola está llena.\n");
           return;
       }
       // Avanzar el puntero 'rear' y añadir el elemento
       q->rear = (q->rear + 1) % MAX_SIZE;
       q->data[q->rear] = item;
   }
   

Código de Eliminación (DeleteQ)

Este código implementa la eliminación de un elemento del frente de la cola.

   ElementType DeleteQ(Queue *q) {
       // Comprobar si la cola está vacía
       if (q->rear == q->front) {
           printf("Error: La cola está vacía.\n");
           // En una implementación real, deberías manejar este error de forma más robusta,
           // quizás devolviendo un valor especial o lanzando una excepción.
           return -1; // Asumiendo que ElementType es int y -1 es un valor de error
       }
       // Avanzar el puntero 'front' y devolver el elemento eliminado
       q->front = (q->front + 1) % MAX_SIZE;
       return q->data[q->front];
   }