Applicazioni delle Liste in Python

In questa ultima lezione sulle liste in Python vedremo alcune possibili applicazioni.

In particolare vedremo come realizzare due strutture dati molto utili: le code e gli stack. Implementeremo queste strutture dati utilizzando le liste e le funzioni.

Liste come Stack

Una possibile applicazione delle liste in Python è quella di utilizzarle come stack.

Uno stack è una particolare struttura dati che implementa una politica di accesso ai dati secondo il principio LIFO (Last In First Out, i.e. Ultimo dentro Primo Fuori), ovvero l'ultimo elemento inserito è il primo ad essere estratto.

In sostanza, uno stack è un contenitore su cui sono definite le seguenti operazioni:

  • Push: inserisce un elemento in testa allo stack;
  • Pop: estrae l'elemento in testa allo stack;
  • Peek: restituisce l'elemento in testa allo stack senza rimuoverlo;
  • IsEmpty: restituisce True se lo stack è vuoto, False altrimenti.

Per chiarire il funzionamento di uno stack possiamo immaginarlo come una pila di piatti, dove il piatto in cima alla pila sarà il primo ad essere estratto.

Figurativamente, immaginiamo lo stack inizialmente vuoto come segue:

+---------+
|         |
+---------+

Supponiamo di voler inserire un elemento, ad esempio il numero 5, in cima allo stack. Lo stack sarà così:

+---------+
|    5    |
+---------+

Adesso lo stack contiene un solo elemento, il numero 5. Supponiamo di voler inserire un altro elemento, ad esempio il numero 7, in cima allo stack. Lo stack sarà così:

+---------+
|    7    |
+---------+
|    5    |
+---------+

Adesso lo stack contiene due elementi, il numero 7 e il numero 5.

L'operazione di inserimento di un elemento in cima allo stack viene chiamata Push. Aggiungiamo un altro elemento, ad esempio il numero 9, in cima allo stack. Lo stack sarà così:

+---------+
|    9    |
+---------+
|    7    |
+---------+
|    5    |
+---------+

Adesso lo stack contiene tre elementi, il numero 9, il numero 7 e il numero 5.

Volendo, adesso, estrarre un elemento dallo stack, possiamo farlo solo dall'ultimo elemento inserito, ovvero il numero 9. Questo perché se immaginiamo lo stack come una pila di piatti, il piatto in cima alla pila sarà il primo ad essere estratto in quanto non possiamo estrarre i piatti in fondo alla pila senza prima rimuovere quelli in cima.

L'operazione di estrazione di un elemento in cima allo stack viene chiamata Pop. Eseguiamo l'operazione di pop sullo stack:

+---------+
|    7    |
+---------+
|    5    |
+---------+

Risultato: 9

Adesso lo stack contiene due elementi, il numero 7 e il numero 5. L'elemento 9 è stato estratto dallo stack. Se proviamo a eseguire un'altra operazione di pop otterremo:

+---------+
|    5    |
+---------+

Risultato: 7

Adesso lo stack contiene un solo elemento, il numero 5. L'elemento 7 è stato estratto dallo stack.

Le ultime due operazioni possibili su di uno stack sono Peek e IsEmpty.

L'operazione di Peek restituisce l'elemento in cima allo stack senza rimuoverlo. Ad esempio, se eseguiamo l'operazione di peek sullo stack otteniamo:

+---------+
|    5    |
+---------+

Risultato: 5

L'operazione di IsEmpty restituisce True se lo stack è vuoto, False altrimenti. Ad esempio, se eseguiamo l'operazione di IsEmpty sullo stack otteniamo:

+---------+
|    5    |
+---------+

Risultato: False

In Python esistono vari modi per implementare uno stack. Uno di questi è quello di utilizzare le liste. Vediamo come.

Implementazione

Per implementare lo stack possiamo usare le liste, le operazioni che esse mettono a disposizione e le funzioni.

La prima funzione che andremo ad implementare è la funzione create_stack che crea uno stack vuoto:

def create_stack():
    return []

Questa funzione restituisce semplicemente una lista vuota che rappresenta il nostro stack nel suo stato iniziale, ossia senza alcun elemento al proprio interno.

Possiamo utilizzare questa funzione in questo modo:

stack = create_stack()

Le prossime funzioni che andremo ad implementare sono le funzioni push e pop che implementano le operazioni di push e pop sullo stack.

L'idea di base di entrambe le funzioni è quella di aggiungere o rimuovere un elemento in cima allo stack, ossia da una singola estremità della lista.

Per implementare l'operazione di push possiamo usare il metodo append delle liste:

def push(stack, element):
    stack.append(element)

Mentre, per implementare l'operazione di pop possiamo usare il metodo pop delle liste:

def pop(stack):
    return stack.pop()

In questo modo possiamo aggiungere elementi in cima allo stack. Ad esempio, se vogliamo inserire prima 5, poi 7 e poi 9 come nell'esempio di sopra, possiamo fare così:

stack = create_stack()

push(stack, 5)
push(stack, 7)
push(stack, 9)

Se proviamo a stampare lo stack otterremo:

>>> print(stack)
[5, 7, 9]

Successivamente possiamo rimuovere elementi dalla cima dello stack. Ad esempio, se vogliamo rimuovere l'elemento 9 possiamo fare così:

cima = pop(stack)
print(cima)

Otterremo:

9

Se proviamo a stampare lo stack otterremo:

>>> print(stack)
[5, 7]

Quindi l'elemento 9 è stato effettivamente rimosso dalla cima dello stack.

Per implementare l'operazione di peek possiamo banalmente usare l'indicizzazione negativa, usando l'indice -1 per ottenere l'ultimo elemento della lista:

def peek(stack):
    return stack[-1]

Volendolo applicare allo stack otteniamo:

cima = peek(stack)
print(cima)

Otterremo:

7

Se proviamo a stampare lo stack otterremo:

>>> print(stack)
[5, 7]

Quindi l'elemento 7 è rimasto in cima allo stack.

Infine, ci rimane da implementare l'operazione di isEmpty. Per farlo basta controllare se la lunghezza dello stack è uguale a 0:

def isEmpty(stack):
    if len(stack) == 0:
        return True
    else:
        return False

Volendolo applicare allo stack otteniamo:

vuoto = isEmpty(stack)
print(vuoto)

Otterremo:

False

Ricapitolando, l'implementazione di uno stack con le liste in Python è la seguente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def create_stack():
    return []

def push(stack, element):
    stack.append(element)

def pop(stack):
    return stack.pop()

def peek(stack):
    return stack[-1]

def isEmpty(stack):
    if len(stack) == 0:
        return True
    else:
        return False

Liste come Code

Le liste possono essere utilizzate anche per implementare le code. Una coda è una struttura dati che permette di inserire elementi in fondo alla coda e di rimuoverli dall'inizio della coda. Questo tipo di struttura dati utilizza una politica di tipo FIFO (First In First Out, i.e. Primo dentro Primo Fuori), ossia il primo elemento ad essere inserito in coda è anche il primo ad essere estratto dalla coda.

In pratica, una Coda è un contenitore che fornisce le seguenti operazioni:

  • Enqueue: inserisce un elemento in fondo alla coda;
  • Dequeue: estrae un elemento dall'inizio della coda;
  • Peek: restituisce l'elemento in cima alla coda senza rimuoverlo;
  • IsEmpty: restituisce True se la coda è vuota, False altrimenti.

Figurativamente possiamo rappresentare una coda inizialmente vuota in questo modo:

+---------+
|         |
+---------+

Se eseguiamo l'operazione di Enqueue sul valore 5, ossia inseriamo l'elemento 5, otteniamo:

+---------+
|    5    |
+---------+

Se eseguiamo l'operazione di Enqueue sul valore 7 otteniamo:

+---------+---------+
|    7    |    5    |
+---------+---------+

Se eseguiamo l'operazione di Enqueue sul valore 9 otteniamo:

+---------+---------+---------+
|    9    |    7    |    5    |
+---------+---------+---------+

Adesso proviamo ad estrarre un elemento con l'operazione di Dequeue. Otterremo:

+---------+---------+
|    9    |    7    |
+---------+---------+

Risultato: 5

Se proviamo ad estrarre un altro elemento con l'operazione di Dequeue otterremo:

+---------+
|    9    |
+---------+

Risultato: 7

In sostanza, quindi, gli elementi vengono estratti da una coda nello stesso ordine con cui sono stati inseriti.

Anche per le code, così come per gli stack, possiamo utilizzare le liste per implementarle in Python. Vediamo come.

Implementazione di una Coda con le Liste

Per implementare una coda con le liste possiamo utilizzare le stesse funzioni che abbiamo utilizzato per implementare uno stack. Tuttavia, dobbiamo cambiare il modo in cui implementiamo le funzioni push che diventa enqueue e pop che diventa dequeue.

In particolare, per implementare l'operazione di enqueue dobbiamo usare il metodo insert delle liste, che ci permette di inserire un elemento in una posizione specifica della lista. In questo caso, dobbiamo inserire l'elemento in fondo alla lista, ossia nella posizione 0:

def enqueue(queue, element):
    queue.insert(0, element)

Per la funzione dequeue possiamo invece usare il metodo pop delle liste, che ci permette di rimuovere un elemento dalla lista. In questo caso, dobbiamo rimuovere l'elemento in cima alla lista, ossia l'ultimo elemento:

def dequeue(queue):
    return queue.pop()

In sostanza la funzione dequeue è identica alla funzione pop che abbiamo utilizzato per implementare lo stack.

Adesso, volendo utilizzare queste funzioni per implementare una coda, possiamo creare una coda vuota con la funzione create_queue:

queue = create_queue()

Se proviamo a stampare la coda otterremo:

>>> print(queue)
[]

Adesso possiamo inserire un elemento in coda con la funzione enqueue:

enqueue(queue, 5)

Se proviamo a stampare la coda otterremo:

>>> print(queue)
[5]

Proviamo ad inserire altri elementi in coda:

enqueue(queue, 7)
enqueue(queue, 9)

Se proviamo a stampare la coda otterremo:

>>> print(queue)
[9, 7, 5]

Adesso possiamo estrarre un elemento dalla coda con la funzione dequeue:

estratto = dequeue(queue)
print(estratto)

Otterremo:

5

Se proviamo a stampare la coda otterremo:

>>> print(queue)
[9, 7]

Quindi l'elemento 5 è stato estratto dalla coda, cioè il primo elemento che abbiamo inserito.

Possiamo usare, infine, le funzioni peek e isEmpty per ottenere l'elemento in cima alla coda e per verificare se la coda è vuota:

primo = peek(queue)
print(primo)

vuoto = isEmpty(queue)
print(vuoto)

Otterremo:

7
False

Ricapitolando, l'implementazione di una coda con le liste in Python è la seguente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def create_queue():
    return []

def enqueue(queue, element):
    queue.insert(0, element)

def dequeue(queue):
    return queue.pop()

def peek(queue):
    return queue[-1]

def isEmpty(queue):
    if len(queue) == 0:
        return True
    else:
        return False

In Sintesi

In questa lezione conclusiva sulle liste in Python abbiamo visto un'applicazione pratica delle liste, ossia la loro utilità per implementare le strutture dati Stack e Coda.

A partire dal prossimo capitolo inizieremo lo studio di un nuovo tipo di dato molto importante che Python mette a disposizione: Le Tuple.

Lezione Precedente Indice del capitolo