Introduzione

Le strutture di dati organizzano la memorizzazione nei computer in modo da poter accedere e cambiare i dati in modo efficiente. Le pile e le code sono alcune delle prime strutture di dati definite in informatica.

Semplici da imparare e facili da implementare, i loro usi sono comuni e molto probabilmente vi troverete ad incorporarle nel vostro software per vari compiti.

E’ comune che pile e code siano implementate con un array o una lista collegata. Ci affideremo alla struttura dati List per ospitare sia le pile che le code.

Come funzionano?

Stack

Le pile, come suggerisce il nome, seguono il principio Last-in-First-Out (LIFO). Come se impilassimo le monete una sopra l’altra, l’ultima moneta che mettiamo in cima è quella che sarà la prima ad essere rimossa dalla pila in seguito.

Per implementare uno stack, quindi, abbiamo bisogno di due semplici operazioni:

• push – aggiunge un elemento in cima allo stack:

• pop – rimuove l’elemento in cima allo stack:

Coda

Le code, come suggerisce il nome, seguono il principio First-in-First-Out (FIFO). Come in una coda per i biglietti del cinema, il primo che si mette in fila è il primo a comprare un biglietto e a godersi il film.

Per implementare una coda, quindi, abbiamo bisogno di due semplici operazioni:

• enqueue – aggiunge un elemento alla fine della coda:

• dequeue – toglie l’elemento all’inizio della coda:

Stacchi e code usando le liste

La struttura dati incorporata List di Python è dotata di metodi per simulare entrambe le operazioni di stack e code.

Consideriamo una pila di lettere:

Possiamo usare le stesse funzioni per implementare una coda. La funzione pop opzionalmente prende l’indice dell’elemento che vogliamo recuperare come argomento.

Perciò possiamo usare pop con il primo indice della lista, cioè 0, per ottenere un comportamento simile alla coda.

Considera una “coda” di frutta:

Anche qui usiamo le operazioni append e pop della lista per simulare le operazioni principali di una coda.

Stacchi e code con la libreria Deque

Python ha una libreria deque (pronunciato ‘deck’) che fornisce una sequenza con metodi efficienti per lavorare come uno stack o una coda.

deque è l’abbreviazione di Double Ended Queue – una coda generalizzata che può ottenere il primo o l’ultimo elemento memorizzato:

Se volete saperne di più sulla libreria deque e su altri tipi di collezioni che Python fornisce, potete leggere il nostro articolo Introduzione al modulo delle collezioni di Python.

Implementazioni di Stricter in Python

Se il tuo codice avesse bisogno di uno stack e tu fornissi un List, non c’è nulla che impedisca ad un programmatore di chiamare insert, remove o altre funzioni di lista che influenzino l’ordine del tuo stack! Questo fondamentalmente rovina lo scopo di definire uno stack, poiché non funziona più come dovrebbe.

Ci sono momenti in cui vorremmo assicurarci che solo operazioni valide possano essere eseguite sui nostri dati.

Possiamo creare classi che espongono solo i metodi necessari per ogni struttura dati.

Per fare ciò, creiamo un nuovo file chiamato stack_queue.py e definiamo due classi:

I programmatori che usano le nostre Stack e Queue sono ora incoraggiati ad usare i metodi forniti per manipolare i dati.

Esempi

Immagina di essere uno sviluppatore che lavora su un nuovo elaboratore di testi. Sei incaricato di creare una funzione di annullamento – permettendo agli utenti di ripercorrere le loro azioni fino all’inizio della sessione.

Una pila è ideale per questo scenario. Possiamo registrare ogni azione che l’utente compie spingendola nello stack. Quando l’utente vuole annullare un’azione, la estrae dallo stack. Possiamo simulare rapidamente la funzione in questo modo:

Le code hanno usi diffusi anche nella programmazione. Pensate a giochi come Street Fighter o Super Smash Brothers. I giocatori in questi giochi possono eseguire mosse speciali premendo una combinazione di pulsanti. Queste combinazioni di tasti possono essere memorizzate in una coda.

Ora immagina di essere uno sviluppatore che lavora su un nuovo gioco di combattimento. Nel vostro gioco, ogni volta che viene premuto un pulsante, viene sparato un evento di input. Un tester ha notato che se i pulsanti vengono premuti troppo velocemente il gioco elabora solo il primo e le mosse speciali non funzionano!

Puoi risolvere questo problema con una coda. Possiamo mettere in coda tutti gli eventi di input quando arrivano. In questo modo non importa se gli eventi di input arrivano con poco tempo tra loro, saranno tutti memorizzati e disponibili per l’elaborazione. Quando stiamo elaborando le mosse, possiamo de-cancellarle. Una mossa speciale può essere elaborata in questo modo:

Conclusione

Stack e code sono semplici strutture dati che ci permettono di memorizzare e recuperare dati in modo sequenziale. In una pila, l’ultimo elemento inserito è il primo ad uscire. In una coda, il primo elemento che inseriamo è il primo ad uscire.

Possiamo aggiungere elementi ad uno stack usando l’operazione push e recuperare elementi usando l’operazione pop. Con le code, aggiungiamo elementi usando l’operazione enqueue e recuperiamo elementi usando l’operazione dequeue.

In Python, possiamo implementare pile e code semplicemente usando la struttura dati integrata List. Python ha anche la libreria deque che può fornire in modo efficiente operazioni di stack e code in un unico oggetto. Infine, abbiamo creato le nostre classi di stack e code per un controllo più stretto dei nostri dati.

Ci sono molti casi d’uso nel mondo reale per stack e code, la loro comprensione ci permette di risolvere molti problemi di immagazzinamento dati in modo facile ed efficace.