Qué son y cómo usar las Colas (Queue)

Una COLA, o Queue, es una colección de elementos que se utiliza para organizar y manipular elementos en un orden específico.

Cada vez que se inserta un nuevo elemento en la COLA, este se coloca en la parte posterior. Cuando se retira un elemento, se coge el de la parte anterior.

Esto se logra mediante dos operaciones principales:

• Enqueue: Agrega un elemento al final de la cola.
• Dequeue: Elimina y devuelve el elemento del frente de la cola.

Internamente, una COLA se puede implementar utilizando un simple Array o una lista enlazada, o un ring buffer, entre otras opciones.

Además de estas operaciones básicas, también se pueden realizar otras operaciones en una COLA, como verificar si está vacía o acceder al elemento del frente sin eliminarlo.

Propiedades

Cuando usar una cola

Tiene sentido utilizar una COLA en procesos que contienen esperas y donde es lógico que los que llevan más tiempo esperando deberían ser atendidos primeros.

Una cola se asemeja a una fila de personas esperando su turno en un servicio, por ejemplo para entrar el cine. Es razonable que la persona que ha llegado primero, lleva más tiempo esperando, y sea la primera en ser atendida.

En un ordenador tiene sentido, por ejemplo, en la cola de impresión. Los documentos que están esperando para ser imprimidos en la impresora, deben ser atendidos en el orden de llegada.

Ejemplo de cola

A continuación, se presentan ejemplos de cómo se puede implementar una cola en diferentes lenguajes de programación:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        Queue<int> cola = new Queue<int>();

        cola.Enqueue(5);
        cola.Enqueue(10);
        cola.Enqueue(15);

        int elementoFrente = cola.Dequeue(); // Retorna 5
        Console.WriteLine(elementoFrente);
    }
}

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> cola;

    cola.push(5);
    cola.push(10);
    cola.push(15);

    int elementoFrente = cola.front(); // Retorna 5
    cola.pop();

    cout << elementoFrente << endl;
    return 0;
}

class Cola {
    constructor() {
        this.cola = [];
    }

    enqueue(elemento) {
        this.cola.push(elemento);
    }

    dequeue() {
        return this.cola.shift();
    }

    peek() {
        return this.cola[0];
    }

    isEmpty() {
        return this.cola.length === 0;
    }
}

const cola = new Cola();
cola.enqueue(5);
cola.enqueue(10);
cola.enqueue(15);

const elementoFrente = cola.dequeue(); // Retorna 5
console.log(elementoFrente);

from collections import deque

cola = deque()

cola.append(5)
cola.append(10)
cola.append(15)

elemento_frente = cola.popleft() # Retorna 5
print(elemento_frente)

Eficiencia

La eficiencia de una COLA tendrá que ver con la forma en la que se haya implementado internamente (pero, vamos a considerar que se ha implementado “bien”).

En este caso, la lectura y eliminación de elementos en una cola se realizan en tiempo constante O(1), ya que se accede al primer elemento de la cola.

La inserción en una cola también es eficiente, ya que se agrega al final de la cola en tiempo constante O(1).

El resto de operaciones no tienen sentido ya que solo puedes acceder al elemento en la cima de la cola. No puedes acceder a elementos en posiciones intermedias sin desapilar todos los elementos por encima.