Lic. Carlos Enrique Loria Beeche.
Cuarto artículo técnico de la saga “Estructuras de datos: cuando la memoria se convierte en inteligencia”
Este artículo forma parte de la saga que inicié con Estructuras de datos: cuando la memoria se convierte en inteligencia, donde presenté las ocho estructuras de datos fundamentales que iremos recorriendo paso a paso.
En las entregas anteriores estudiamos el array, el estacionamiento numerado de la memoria, la linked list, la búsqueda del tesoro en la memoria, y la stack, la pila y el recuerdo del último paso.
Ahora vamos a estudiar una estructura que parece muy cotidiana, porque todos la hemos vivido: la queue, o cola.
Una cola funciona como la fila de un banco, una fila en el supermercado o una cola de impresión: quien llega primero debe ser atendido primero.
Una cola nos enseña que también en el software hay turnos, esperas y procesos que deben avanzar con orden.
¿Qué es una queue?
Una queue, o cola, es una estructura de datos que organiza sus elementos bajo una regla muy simple:
El primer elemento en entrar es el primero en salir.
En inglés, esta regla se conoce como FIFO: First In, First Out.
La analogía más natural es una fila. Si tres personas llegan en este orden:
A, B, C
La primera persona atendida debe ser A, luego B, y finalmente C.
En una cola, los elementos entran por el final y salen por el frente.
ENTRA POR AQUÍ SALE POR AQUÍ
| |
v v
+-----+ +-----+ +-----+ +-----+
| D | --> | C | --> | B | --> | A |
+-----+ +-----+ +-----+ +-----+
FINAL FRENTE
En este ejemplo, A está al frente de la cola. Aunque D haya entrado de último, debe esperar su turno.
La regla FIFO
La regla FIFO es el corazón de la cola.
Si insertamos elementos en este orden:
A, B, C, D
El orden de salida será el mismo:
A, B, C, D
Esto la diferencia claramente de la pila.
En una stack, el último elemento en entrar es el primero en salir. En una queue, el primero en entrar es el primero en salir.
La pila recuerda lo último. La cola respeta lo primero.
Operaciones básicas: enqueue, dequeue y peek
Las colas suelen tener tres operaciones fundamentales:
- enqueue: agregar un elemento al final de la cola.
- dequeue: retirar el elemento que está al frente de la cola.
- peek: consultar el elemento del frente sin retirarlo.
Enqueue: agregar al final
La operación enqueue inserta un nuevo elemento al final de la cola.
Cola inicial:
A -> B -> C
enqueue(D)
Resultado:
A -> B -> C -> D
El nuevo elemento D queda al final, esperando su turno.
Dequeue: retirar del frente
La operación dequeue elimina y devuelve el elemento que está al frente.
Cola inicial:
A -> B -> C -> D
dequeue()
Resultado:
B -> C -> D
Elemento retirado: A
No se retira cualquier elemento. Siempre sale el que llegó primero.
Peek: mirar sin quitar
La operación peek permite consultar el elemento que está al frente de la cola sin retirarlo.
Cola:
A -> B -> C -> D
peek() devuelve: A
La cola sigue igual:
A -> B -> C -> D
Esta operación es útil cuando necesitamos saber cuál será el próximo elemento atendido, pero todavía no queremos sacarlo de la cola.
Fila de banco y cola de impresión
La cola es una de las estructuras más fáciles de explicar porque todos conocemos su lógica.
En una fila de banco, lo justo es que quien llegó primero sea atendido primero. En una cola de impresión, lo normal es que el primer documento enviado sea el primero que se imprima. En un sistema de atención al cliente, las solicitudes suelen procesarse en el orden en que llegan.
El software usa colas constantemente porque muchas tareas no pueden resolverse todas al mismo tiempo. Algunas deben esperar. Otras deben procesarse una por una. Y muchas veces el criterio más razonable es respetar el orden de llegada.
La cola permite organizar la espera sin perder el orden.
Diferencia entre stack y queue
La diferencia entre una pila y una cola es fundamental.
| Estructura | Regla | Ejemplo cotidiano |
|---|---|---|
| Stack / Pila | LIFO: último en entrar, primero en salir | Control Z, pila de platos, pila de llamadas |
| Queue / Cola | FIFO: primero en entrar, primero en salir | Fila de banco, cola de impresión, procesamiento de tareas |
La pila se usa cuando lo último debe resolverse primero. La cola se usa cuando el orden de llegada debe respetarse.
Operaciones básicas de una queue
| Operación | Descripción | Costo típico |
|---|---|---|
| enqueue | Agregar un elemento al final de la cola | O(1) |
| dequeue | Retirar el elemento del frente | O(1) |
| peek | Consultar el elemento del frente sin retirarlo | O(1) |
| isEmpty | Verificar si la cola está vacía | O(1) |
| recorrer | Visitar todos los elementos | O(n) |
En una implementación eficiente, agregar al final y retirar del frente puede hacerse en tiempo constante.
Colas simples, circulares y de prioridad
La idea básica de una cola puede extenderse en varias direcciones.
Cola simple
Es la cola tradicional: los elementos entran por el final y salen por el frente.
A -> B -> C -> D
Cola circular
Una cola circular reutiliza posiciones disponibles, especialmente cuando se implementa sobre un array de tamaño fijo. Al llegar al final del espacio reservado, puede volver al inicio si hay lugar disponible.
Esta idea es útil en buffers, transmisión de datos y sistemas donde se necesita aprovechar memoria limitada.
Cola de prioridad
Una cola de prioridad no atiende necesariamente al primero que llegó, sino al elemento con mayor prioridad.
Una sala de urgencias es una buena analogía: no siempre se atiende primero a quien llegó primero, sino a quien necesita atención más inmediata.
Más adelante, cuando estudiemos heap, veremos una estructura especialmente útil para implementar colas de prioridad.
Ejemplo en C++
En C++, podemos usar la clase estándar queue, incluida en la biblioteca estándar.
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> cola;
cola.push(10);
cola.push(20);
cola.push(30);
cout << "Elemento al frente: " << cola.front() << endl;
cout << "Elemento al final: " << cola.back() << endl;
cola.pop();
cout << "Después de retirar un elemento, nuevo frente: "
<< cola.front() << endl;
while (!cola.empty()) {
cout << "Atendiendo: " << cola.front() << endl;
cola.pop();
}
return 0;
}
En este ejemplo, insertamos tres elementos: 10, 20 y 30. El primero en salir será 10, porque fue el primero en entrar.
Ejemplo en C#
En C#, podemos usar la clase genérica Queue<T>.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<int> cola = new Queue<int>();
cola.Enqueue(10);
cola.Enqueue(20);
cola.Enqueue(30);
Console.WriteLine("Elemento al frente: " + cola.Peek());
int atendido = cola.Dequeue();
Console.WriteLine("Elemento atendido: " + atendido);
Console.WriteLine("Nuevo elemento al frente: " + cola.Peek());
while (cola.Count > 0)
{
Console.WriteLine("Atendiendo: " + cola.Dequeue());
}
}
}
En C#, Enqueue agrega al final, Dequeue retira del frente y Peek permite consultar el próximo elemento sin retirarlo.
Ejemplo en Python
En Python, una forma eficiente de implementar una cola es usar deque, disponible en el módulo collections.
from collections import deque
cola = deque()
cola.append(10)
cola.append(20)
cola.append(30)
print("Elemento al frente:", cola[0])
atendido = cola.popleft()
print("Elemento atendido:", atendido)
print("Nuevo elemento al frente:", cola[0])
while len(cola) > 0:
print("Atendiendo:", cola.popleft())
En este ejemplo, append agrega al final de la cola y popleft retira del frente.
Aunque una lista de Python puede usarse de forma sencilla, deque es más apropiado para colas porque está diseñado para insertar y retirar eficientemente en ambos extremos.
¿Cuándo conviene usar una queue?
Una cola conviene cuando necesitamos procesar elementos en el mismo orden en que llegaron.
Algunos casos típicos son:
- Colas de impresión.
- Solicitudes a un servidor.
- Mensajes pendientes.
- Procesamiento de tareas en segundo plano.
- Sistemas de atención por turno.
- Eventos que deben procesarse en orden.
- Algoritmos de búsqueda en anchura.
- Buffers de comunicación.
La cola es útil cuando el orden de llegada importa y queremos evitar que una tarea recién llegada pase por encima de las anteriores.
Aplicación clásica: búsqueda en anchura
Una aplicación clásica de las colas aparece en los algoritmos de búsqueda, especialmente en la búsqueda en anchura, conocida en inglés como Breadth-First Search o BFS.
La idea es visitar primero los elementos más cercanos al punto de partida antes de avanzar hacia niveles más lejanos.
Por ejemplo, si queremos explorar una red de conexiones, una cola permite guardar los nodos pendientes y procesarlos en el orden en que fueron descubiertos.
1. Visito el nodo inicial.
2. Agrego sus vecinos a la cola.
3. Atiendo el primer vecino.
4. Agrego los vecinos de ese vecino.
5. Continúo respetando el orden de descubrimiento.
Esto permite recorrer estructuras como árboles y grafos de manera ordenada por niveles.
La cola permite explorar primero lo más cercano antes de avanzar hacia lo más lejano.
La lección de la cola
La cola es una estructura sencilla, pero muy poderosa. Enseña que el orden de llegada puede ser una regla de justicia y organización dentro del software.
El array nos enseñó el poder del índice. La lista enlazada nos enseñó el valor del enlace. La pila nos enseñó el valor del retorno. La cola nos enseña el valor del turno.
En sistemas reales, no todo puede resolverse de inmediato. Muchas tareas deben esperar, y la cola nos da una forma clara de administrar esa espera.
La cola nos recuerda que, en programación, atender bien también significa respetar el orden correcto.
Próxima entrega
En el próximo artículo de esta saga estudiaremos la hash table, o tabla hash. Allí veremos una estructura diseñada para encontrar información con gran rapidez a partir de una clave.
Pasaremos de la fila ordenada al acceso veloz mediante una función hash.
Referencias para profundizar
- Carlos Enrique Loría Beeche — Estructuras de datos: cuando la memoria se convierte en inteligencia
- Carlos Enrique Loría Beeche — Array: el estacionamiento numerado de la memoria
- Carlos Enrique Loría Beeche — Linked List: la búsqueda del tesoro en la memoria
- Carlos Enrique Loría Beeche — Stack: la pila y el recuerdo del último paso