Cola

7.1 Definición de una cola y sus propiedades

Cola — es una estructura de datos abstracta que representa una colección ordenada de elementos, organizada bajo el principio "el primero en entrar es el primero en salir" (First In, First Out, FIFO). Puedes imaginarte una cola como una fila de personas en una tienda: la primera persona en la fila es la primera en ser atendida.

Propiedades de la cola:

• FIFO (First In, First Out): El primer elemento añadido será el primer elemento eliminado.
• Operaciones limitadas: La cola soporta un conjunto limitado de operaciones — añadir (enqueue), eliminar (dequeue) y ver (peek) el elemento en la posición delantera.
• Acceso unidireccional: El acceso a los elementos solo es posible desde los lados delantero (front) y trasero (rear).
• Facilidad de implementación: Una cola puede implementarse fácilmente usando un array o una lista enlazada.

Principio de trabajo FIFO:

• Añadir elemento (enqueue): Un nuevo elemento se añade al final de la cola.
• Eliminar elemento (dequeue): El primer elemento añadido se elimina del inicio de la cola.
• Ver elemento delantero (peek): Permite ver el elemento en la posición delantera de la cola sin eliminarlo.

Los elementos de la cola se añaden desde un extremo (parte trasera) y se eliminan desde el otro extremo (parte delantera). De esta forma, el primer elemento añadido es el primero en ser eliminado.

7.2 Operaciones principales

Operaciones principales: enqueue, dequeue, peek

Operación enqueue: Añade un nuevo elemento al final de la cola.

Complejidad temporal: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Salida: deque([10, 20])

Operación dequeue: Elimina y devuelve el elemento desde el inicio de la cola.

Complejidad temporal: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Salida: deque([10, 20])

front_element = queue.popleft()  # dequeue
print(front_element)  # Salida: 10
print(queue)  # Salida: deque([20])

Operación peek: Devuelve el elemento en la posición delantera de la cola sin eliminarlo.

Complejidad temporal: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Salida: deque([10, 20])

front_element = queue[0]  # peek
print(front_element)  # Salida: 10

7.3 Ejemplos de uso de la cola

Vamos a ver algunos ejemplos de uso de la cola.

1 Gestión de trabajos en la impresora

La cola se utiliza para gestionar los trabajos en la impresora, donde los documentos se añaden a la cola y se imprimen en el orden en que llegaron.

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_job(self, job):
        self.queue.append(job)

    def print_job(self):
        if self.queue:
            job = self.queue.popleft()
            print(f"Printing: {job}")

# Ejemplo de uso:
printer_queue = PrinterQueue()
printer_queue.add_job("Documento1.pdf")
printer_queue.add_job("Documento2.pdf")
printer_queue.print_job()  # Salida: Printing: Documento1.pdf
printer_queue.print_job()  # Salida: Printing: Documento2.pdf

2 Procesamiento de solicitudes en un servidor web

La cola se utiliza para gestionar las solicitudes de los clientes que llegan al servidor web. Las solicitudes se procesan en el orden en que llegaron.

class RequestQueue:
    def __init__(self):
        self.queue = deque()

    def add_request(self, request):
        self.queue.append(request)

    def process_request(self):
        if self.queue:
            request = self.queue.popleft()
            print(f"Processing request: {request}")

# Ejemplo de uso:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # Salida: Processing request: GET /index.html
request_queue.process_request()  # Salida: Processing request: POST /submit-form

3 Cola de mensajes en sistemas de mensajería

La cola se utiliza para gestionar los mensajes en sistemas de intercambio de información (por ejemplo, en brokers de mensajes). Los mensajes se procesan en el orden en que llegaron.

class MessageQueue:
    def __init__(self):
        self.queue = deque()

    def send_message(self, message):
        self.queue.append(message)

    def receive_message(self):
        if self.queue:
            message = self.queue.popleft()
            print(f"Received message: {message}")

# Ejemplo de uso:
message_queue = MessageQueue()
message_queue.send_message("Hola")
message_queue.send_message("Mundo")
message_queue.receive_message()  # Salida: Received message: Hola
message_queue.receive_message()  # Salida: Received message: Mundo