Implementare una coda in Python¶

Ancora una volta, creiamo una nuova classe per l’implementazione. Come prima, useremo le liste per fare la rappresentazione interna dell’oggetto coda.

Dobbiamo decidere quale capo della lista usare come testa e quale come fine della coda. La seguente implementazione in Listing 1 assume che la fine sia in posizione 0 della lista. Questo ci permette di usare la funzione insert su liste per aggiungere nuovi elementi. L’operazione pop può essere usata per rimuovere l’elemento dalla testa della coda (l’ultimo elemento della lista).

Listing 1

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

CodeLens 1 mostra la classe Queue in azione se facciamo le operazioni in Tabella 1.

Ulteriori manipolazioni di questa coda potrebbero dare i seguenti risultati:

>>> q.size()
3
>>> q.isEmpty()
False
>>> q.enqueue(8.4)
>>> q.dequeue()
4
>>> q.dequeue()
'dog'
>>> q.size()
2

Per come abbiamo implementato la coda, l’accodamento costa O(n) e l’estrazione costa O(1). E’ possibile dare una implementazione, usando le Linked List in cui sia accodamento che estrazione costano O(1): https://runestone.academy/runestone/books/published/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

Una coda può essere usata per esempio per mantenere e gestire le richieste che arrivano a una stampante: https://runestone.academy/runestone/books/published/pythonds/BasicDS/SimulationPrintingTasks.html