Implementare una pila in Python¶

Adesso che abbiamo definito la pila come un tipo di dato astratto, possiamo focalizzarci sulla sua implementazione.

A questo proposito dobbiamo creare una nuova classe. Le operazioni della pila sono implementate come metodi. Inoltre, per farlo conviene utilizzare la semplicità delle collezioni primitive di Python. Useremo per questo una semplice lista.

Ricordiamo che la classe delle liste in Python fornisce un meccanismo per collezionare elementi e un insieme di metodi. Per esempio, se abbiamo la lista [2,5,3,6,7,4], dobbiamo solo decidere quale capo della lista deve essere considerato come cima della pila. Una volta che abbiamo deciso ciò, le operazioni possono essere implementate usando i metodi delle liste come append e pop.

La seguente implementazione (ActiveCode 1) assume che la fine della lista contiene gli elementi in cima alla pila. Dal momento che la pila cresce (chiamando push), nuovi elementi verrano aggiunti alla fine della lista. Dunque pop manipola la fine della lista.

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

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

     def push(self, item):
         self.items.append(item)

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

     def peek(self):
         return self.items[len(self.items)-1]

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

Implementare una classe Stack usando le liste (stack_1ac)

Ricordiamoci che non succede nulla se clicchiamo run, in quanto il codice definisce solo la classe. Dobbiamo invece creare un oggetto Stack e usarlo, come mostrato in ActiveCode 2, che effettua le operazioni in Tabella 1. Nota che la definizione di Stack è importata dal modulo pythonds.

Note

Il modulo pythonds contiene implementazioni di tutte le strutture dati discusse nel libro originale, e può essere scaricato da pythonworks.org.

from pythonds.basic.stack import Stack

s=Stack()

print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

(stack_ex_1)

E’ importante notare che potremmo aver scelto di implementare ula pila usando una lista dove la cima è l’inizio. In questo caso, i metodi pop e append non funzionano e dovremmo indicizzare la posizione 0 (il primo elemento della lista) esplicitamente usando pop e insert. L’implementazione è mostrato nel seguente CodeLens 1.

Implementazione alternativa della classe Stack (stack_cl_1)

Questa abilità di cambiare l’implementazione del tipo di dato astratto mantenendo le caratteristiche logiche è un esempio di astrazione.

Tuttavia, anche se entrambi le classi fanno il loro mestiere ci sono importanti differenze. Ricordiamo che append e pop() hanno entrambi costo O(1). Questo significa che la prima implementazione esegue push e pop in tempo costante indipendentemente dal numero di elementi che ci sono nella pila. Le prestazioni della seconda implementazione soffrono del fatto che insert(0) e pop(0) richiedono entrambi O(n) per una pila che già contiene n elementi. Chiaramente, anche se entrambi le implementazioni restituiscono le stesse cose, si comportano molto diversamente in fatto di tempo di esecuzione.

Next Section - Parentesi Bilanciate