Esta guía complementa la práctica de Colas. Cubre el TAD abstracto, las tres implementaciones de la cátedra (arreglos, punteros y cola circular), y casos de uso con análisis de complejidad.
Una cola es una estructura FIFO (First In, First Out): el primer elemento en entrar es el primero en salir.
Ejemplo intuitivo: una fila de personas en una ventanilla. Los nuevos elementos entran al final, y las salidas ocurren por el frente.
El TAD define qué operaciones se pueden hacer con una cola, sin imponer cómo se guarda internamente.
| Operación | Firma | Intención |
|---|---|---|
| Crear | Cola c_crear() |
Devuelve una cola vacía lista para usar. |
| Encolar | bool c_encolar(Cola, TipoElemento) |
Inserta un elemento al final. Devuelve false si la operación no puede realizarse. |
| Desencolar | TipoElemento c_desencolar(Cola) |
Quita y devuelve el elemento del frente, o NULL si la cola está vacía. |
| Frente | TipoElemento c_frente(Cola) |
Devuelve el elemento del frente sin eliminarlo, o NULL si la cola está vacía. |
| ¿Vacía? | bool c_es_vacia(Cola) |
Indica si la cola no contiene elementos. |
colas_arreglos.c)struct ColaRep {
TipoElemento *valores;
unsigned int cantidad;
};
valores apunta a un arreglo contiguo en heap de tamaño fijo TAMANIO_MAXIMO.cantidad indica cuántos elementos válidos hay.valores[0].índice: [0] [1] [2] [3] ...
valores: e1 e2 e3 --
^
frente
cantidad = 3
c_crear, se reserva todo el arreglo con calloc(TAMANIO_MAXIMO, ...).c_encolar escribe en valores[cantidad] y luego incrementa cantidad.c_desencolar devuelve valores[0] y luego desplaza todos los elementos una posición hacia la izquierda.c_frente accede a valores[0] sin modificar la cola.c_encolar y c_frente son O(1).TAMANIO_MAXIMO = 1000).c_desencolar es O(n) por el corrimiento de elementos.colas_punteros.c)struct Nodo {
TipoElemento datos;
struct Nodo *siguiente;
};
struct ColaRep {
struct Nodo *frente;
struct Nodo *final;
};
Cada elemento se guarda en un nodo independiente. frente apunta al primer nodo y final al último.
frente final
| |
v v
[e1|*] -> [e2|*] -> [e3|NULL]
c_encolar crea un nodo con malloc, lo enlaza después de final y actualiza final.c_desencolar toma el nodo del frente, mueve frente al siguiente y libera el nodo.frente como final.c_frente devuelve los datos del primer nodo sin modificar la cola.c_encolar, c_desencolar y c_frente son O(1).siguiente).colas_arreglos_circular.c)struct ColaRep {
TipoElemento *valores;
unsigned int frente;
unsigned int final;
};
Es una implementación con arreglo circular. frente y final avanzan sobre el arreglo, y cuando llegan al final vuelven al comienzo.
índice: [1] [2] [3] [4] [5] [6]
valores: -- e2 e3 -- -- e1
^ ^
frente = 2 final = 6
c_encolar hace avanzar final y escribe allí el nuevo elemento.c_desencolar devuelve valores[frente] y luego hace avanzar frente.paso(final) con frente.c_encolar, c_desencolar y c_frente son O(1).TAMANIO_MAXIMO = 1000).$n$ = cantidad de elementos actuales de la cola.
$N$ = capacidad máxima fija (TAMANIO_MAXIMO = 1000).
| Operación | Arreglo | Punteros | Circular | Notas |
|---|---|---|---|---|
c_crear |
$O(N)$ | $O(1)$ | $O(N)$ | Arreglo y circular reservan el arreglo; punteros solo cabecera. |
c_es_vacia |
$O(1)$ | $O(1)$ | $O(1)$ | Compara frente <= 0, frente == NULL o paso(final) == frente. |
c_encolar |
$O(1)$ | $O(1)$ | $O(1)$ | En punteros y circular se inserta directamente al final. |
c_desencolar |
$O(n)$ | $O(1)$ | $O(1)$ | En arreglo hay corrimiento de elementos. |
c_frente |
$O(1)$ | $O(1)$ | $O(1)$ | Lectura del frente sin quitar. |
Cola c = c_crear();
c_encolar(c, te_crear(10));
c_encolar(c, te_crear(20));
c_encolar(c, te_crear(30));
TipoElemento a = c_desencolar(c); // 10
TipoElemento b = c_frente(c); // 20 (queda en la cola)
Objetivo: desencolar hasta que quede vacía.
void vaciar_e_imprimir(Cola c) {
while (!c_es_vacia(c)) {
TipoElemento e = c_desencolar(c);
printf("%d\n", e->clave);
}
}
Complejidad:
| Implementación | Complejidad |
|---|---|
| Arreglo | $O(n^2)$ |
| Punteros | $O(n)$ |
| Circular | $O(n)$ |
En arreglo, cada c_desencolar desplaza elementos. En punteros y cola circular, cada iteración hace operaciones O(1).
Objetivo: construir una copia sin perder el contenido ni el orden de la cola original.
Estrategia común: usar una cola auxiliar temporal.
Cola copiar_cola(Cola origen) {
Cola aux = c_crear();
Cola copia = c_crear();
while (!c_es_vacia(origen)) {
TipoElemento e = c_desencolar(origen);
c_encolar(aux, e);
c_encolar(copia, e);
}
while (!c_es_vacia(aux)) {
c_encolar(origen, c_desencolar(aux));
}
return copia;
}
Complejidad:
| Implementación | Complejidad |
|---|---|
| Arreglo | $O(n^2)$ |
| Punteros | $O(n)$ |
| Circular | $O(n)$ |
Objetivo: obtener otra cola con los elementos en orden inverso.
Como una cola por sí sola conserva el orden FIFO, una forma simple de invertirla es apoyarse en una pila auxiliar.
Cola invertir_cola(Cola origen) {
Cola aux = c_crear();
Cola invertida = c_crear();
Pila pila = p_crear();
while (!c_es_vacia(origen)) {
TipoElemento e = c_desencolar(origen);
c_encolar(aux, e);
p_apilar(pila, e);
}
while (!c_es_vacia(aux)) {
c_encolar(origen, c_desencolar(aux));
}
while (!p_es_vacia(pila)) {
c_encolar(invertida, p_desapilar(pila));
}
return invertida;
}
Complejidad:
| Implementación | Complejidad |
|---|---|
| Arreglo | $O(n^2)$ |
| Punteros | $O(n)$ |
| Circular | $O(n)$ |
La pila auxiliar agrega operaciones O(1); la diferencia principal vuelve a estar en cómo cada cola resuelve c_encolar y c_desencolar.