Coda

7.1 Definizione di coda e sue proprietà

Coda — è una struttura dati astratta che rappresenta una collezione ordinata di elementi organizzata secondo il principio "primo arrivato — primo uscito" (First In, First Out, FIFO). Una coda si può immaginare come la fila di persone in un negozio: la prima persona in fila viene servita per prima.

Proprietà della coda:

• FIFO (First In, First Out): Il primo elemento aggiunto sarà il primo rimosso.
• Operazioni limitate: La coda supporta un set limitato di operazioni — aggiunta (enqueue), rimozione (dequeue) e visualizzazione (peek) dell'elemento in prima posizione.
• Accesso unidirezionale: Gli elementi possono essere accessibili solo dalla parte anteriore (front) e posteriore (rear).
• Semplicità di implementazione: La coda può essere facilmente implementata usando un array o una lista collegata.

Principio di funzionamento FIFO:

• Aggiunta di un elemento (enqueue): Un nuovo elemento viene aggiunto alla fine della coda.
• Rimozione di un elemento (dequeue): Il primo elemento aggiunto viene rimosso dall'inizio della coda.
• Visualizzazione dell'elemento anteriore (peek): Permette di vedere l'elemento in prima posizione nella coda senza rimuoverlo.

Gli elementi della coda sono aggiunti da un'estremità (parte posteriore) e rimossi dall'altra (parte anteriore). In questo modo, il primo elemento aggiunto è il primo a essere rimosso.

7.2 Operazioni di base

Operazioni di base: enqueue, dequeue, peek

Operazione enqueue: Aggiunge un nuovo elemento alla fine della coda.

Complessità temporale: O(1).

from collections import deque

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

Operazione dequeue: Rimuove e restituisce l'elemento dall'inizio della coda.

Complessità temporale: O(1).

from collections import deque

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

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

Operazione peek: Restituisce l'elemento in prima posizione nella coda senza rimuoverlo.

Complessità temporale: O(1).

from collections import deque

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

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

7.3 Esempi di utilizzo della coda

Esaminiamo alcuni esempi di utilizzo della coda.

1 Gestione dei lavori di stampa

La coda è utilizzata per gestire i lavori di stampa, dove i documenti vengono aggiunti alla coda e stampati nell'ordine di arrivo.

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}")

# Esempio di utilizzo:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # Output: Printing: Document1.pdf
printer_queue.print_job()  # Output: Printing: Document2.pdf

2 Gestione delle richieste su un web server

La coda è utilizzata per gestire le richieste dei clienti che arrivano su un web server. Le richieste vengono elaborate nell'ordine di arrivo.

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}")

# Esempio di utilizzo:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # Output: Processing request: GET /index.html
request_queue.process_request()  # Output: Processing request: POST /submit-form

3 Coda di messaggi nei sistemi di messaggistica

La coda è utilizzata per gestire i messaggi nei sistemi di scambio di informazioni (ad esempio, nei broker di messaggi). I messaggi vengono elaborati nell'ordine di arrivo.

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}")

# Esempio di utilizzo:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # Output: Received message: Hello
message_queue.receive_message()  # Output: Received message: World