Una cola es una estructura de datos lineal especial donde la inserción de elementos ocurre en un extremo (llamado cola) y la eliminación en el otro (llamado frente). Sigue el principio de Primero en Entrar, Primero en Salir (FIFO).

Implementación de la Cola

Las colas se pueden implementar utilizando arreglos o listas enlazadas. La implementación con listas enlazadas es generalmente preferible. Si se utiliza un arreglo, la eliminación de elementos del principio puede ser ineficiente. Una implementación basada en listas enlazadas, que mantiene punteros al nodo principal (frente) y al nodo final (cola), permite operaciones con una complejidad de tiempo de O(1).

Definición de la Estructura de la Cola (queue.h)

typedef int DataType; // Tipo de dato que almacenará la cola

// Estructura para un nodo de la cola
typedef struct QueueNode {
   DataType data;
   struct QueueNode* next;
} QueueNode;

// Estructura principal de la cola
typedef struct Queue {
   QueueNode* front; // Puntero al frente de la cola
   QueueNode* rear;  // Puntero a la cola de la cola
   // int size;      // Contador opcional para el número de elementos
} Queue;
   

Declaraciones de Funciones (queue.h)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// Inicializa una cola vacía
void QueueInit(Queue* pq);

// Libera la memoria ocupada por la cola
void QueueDestroy(Queue* pq);

// Añade un elemento al final de la cola
void QueueEnqueue(Queue* pq, DataType x);

// Elimina el elemento del frente de la cola
void QueueDequeue(Queue* pq);

// Devuelve el elemento del frente de la cola sin eliminarlo
DataType QueueFront(Queue* pq);

// Devuelve el último elemento añadido a la cola sin eliminarlo
DataType QueueRear(Queue* pq);

// Comprueba si la cola está vacía
bool QueueIsEmpty(Queue* pq);

// Devuelve el número de elementos en la cola
int QueueSize(Queue* pq);
   

Implementación de las Funciones (queue.c)

Inicialización de la Cola

void QueueInit(Queue* pq) {
   assert(pq != NULL);
   pq->front = pq->rear = NULL;
   // pq->size = 0; // Si se usa el contador de tamaño
}
   

Añadir un Elemento (QueueEnqueue)

Se crea un nuevo nodo y se añade al final de la cola. Se maneja el caso especial de una cola vacía.

void QueueEnqueue(Queue* pq, DataType x) {
   assert(pq != NULL);
   QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
   if (newNode == NULL) {
       perror("Error de asignación de memoria");
       exit(EXIT_FAILURE);
   }
   newNode->data = x;
   newNode->next = NULL;

   if (pq->front == NULL) { // Si la cola está vacía
       pq->front = pq->rear = newNode;
   } else {
       pq->rear->next = newNode;
       pq->rear = newNode;
   }
   // pq->size++; // Si se usa el contador de tamaño
}
   

Comprobar si la Cola está Vacía

bool QueueIsEmpty(Queue* pq) {
   assert(pq != NULL);
   return pq->front == NULL;
}
   

Eliminar un Elemento (QueueDequeue)

Se elimina el nodo del frente. Se maneja el caso especial de una cola con un solo elemento.

void QueueDequeue(Queue* pq) {
   assert(!QueueIsEmpty(pq));

   QueueNode* temp = pq->front;
   if (pq->front == pq->rear) { // Si solo hay un elemento
       pq->front = pq->rear = NULL;
   } else {
       pq->front = pq->front->next;
   }
   free(temp);
   // pq->size--; // Si se usa el contador de tamaño
}
   

Obtener el Elemento del Frente

DataType QueueFront(Queue* pq) {
   assert(!QueueIsEmpty(pq));
   return pq->front->data;
}
   

Obtener el Elemento de la Cola (QueueRear)

DataType QueueRear(Queue* pq) {
   assert(!QueueIsEmpty(pq));
   return pq->rear->data;
}
   

Obtener el Tamaño de la Cola

Implemetnación directa iterando sobre los nodos.

int QueueSize(Queue* pq) {
   assert(pq != NULL);
   int count = 0;
   QueueNode* current = pq->front;
   while (current != NULL) {
       count++;
       current = current->next;
   }
   return count;
   // Alternativa si se mantiene el contador 'size': return pq->size;
}
   

Destrucción de la Cola

Libera toda la memoria asignada para los nodos de la cola.

void QueueDestroy(Queue* pq) {
   assert(pq != NULL);
   QueueNode* current = pq->front;
   while (current != NULL) {
       QueueNode* nextNode = current->next;
       free(current);
       current = nextNode;
   }
   pq->front = pq->rear = NULL;
   // pq->size = 0; // Si se usa el contador de tamaño
}
   

Ejemplo de Uso: Implementar una Pila usando Colas

Se puede implementar una pila (LIFO) utilizando dos colas. La estrategia común es mantener los elementos en una cola y transferirlos a la otra para simular las operaciones de pila.

Estructura de la Pila Implementada con Colas

// Estructura para la pila usando dos colas
typedef struct {
   Queue q1;
   Queue q2;
} MyStack;
   

Creación de la Pila

MyStack* MyStackCreate() {
   MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
   if (stack == NULL) {
       perror("Error de asignación de memoria");
       exit(EXIT_FAILURE);
   }
   QueueInit(&stack->q1);
   QueueInit(&stack->q2);
   return stack;
}
   

Operación de Apilar (Push)

Se añade el nuevo elemento a la cola que no está vacía.

void MyStackPush(MyStack* obj, int x) {
   assert(obj != NULL);
   if (!QueueIsEmpty(&obj->q1)) {
       QueueEnqueue(&obj->q1, x);
   } else {
       QueueEnqueue(&obj->q2, x);
   }
}
   

Operación de Despailar (Pop)

Para desapilar, se transfieren todos los elementos excepto el último de la cola no vacía a la cola vacía. El último elemento es el que se desapila.

int MyStackPop(MyStack* obj) {
   assert(obj != NULL);
   Queue* activeQueue = &obj->q1;
   Queue* emptyQueue = &obj->q2;

   if (QueueIsEmpty(&obj->q1)) {
       activeQueue = &obj->q2;
       emptyQueue = &obj->q1;
   }

   // Transferir elementos hasta que solo quede uno en la cola activa
   while (QueueSize(activeQueue) > 1) {
       QueueEnqueue(emptyQueue, QueueFront(activeQueue));
       QueueDequeue(activeQueue);
   }

   int topElement = QueueFront(activeQueue);
   QueueDequeue(activeQueue);
   return topElement;
}
   

Obtener el Elemento Superior de la Pila (Top)

Se devuelve el último elemetno de la cola que no está vacía.

int MyStackTop(MyStack* obj) {
   assert(obj != NULL);
   if (!QueueIsEmpty(&obj->q1)) {
       return QueueRear(&obj->q1);
   } else {
       return QueueRear(&obj->q2);
   }
}
   

Comprobar si la Pila está Vacía

La pila está vacía si ambas colas están vacías.

bool MyStackIsEmpty(MyStack* obj) {
   assert(obj != NULL);
   return QueueIsEmpty(&obj->q1) && QueueIsEmpty(&obj->q2);
}
   

Liberar la Memoria de la Pila

void MyStackFree(MyStack* obj) {
   assert(obj != NULL);
   QueueDestroy(&obj->q1);
   QueueDestroy(&obj->q2);
   free(obj);
   obj = NULL;
}