Stack e code in Python

Introduzione

Le strutture dati organizzano l’archiviazione nei computer in modo da poter accedere e modificare in modo efficiente i dati. Stack e code sono alcune delle prime strutture di dati definite in informatica.

Semplice da imparare e facile da implementare, i loro usi sono comuni e molto probabilmente ti ritroverai a incorporarli nel tuo software per varie attività.

È comune per stack e code da implementare con un array o un elenco collegato. Ci baseremo sulla struttura dati List per ospitare sia Stack che code.

Come funzionano?

Stack

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

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

• push – aggiunge un elemento alla parte superiore dello stack:

• pop rimuove l’elemento in cima alla pila:

Coda

Code, come suggerisce il nome, seguire le First-in-First-Out (FIFO) principio. Come se in coda per i biglietti del cinema, il primo a stare in fila è il primo a comprare un biglietto e godersi il film.

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

• enqueue – aggiunge un elemento alla fine della coda:

• dequeue rimuove l’elemento all’inizio della coda:

Pile e Code mediante Liste

Python integrato List struttura dati viene fornito in bundle con metodi per simulare sia la pila e coda di operazioni.

Consideriamo una pila di lettere:

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

Quindi possiamo usarepop con il primo indice della lista cioè0, per ottenere un comportamento simile alla coda.

Considera una” coda”di frutti:

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

Stack e code con la libreria Deque

Python ha una libreriadeque (pronunciata ‘deck’) che fornisce una sequenza con metodi efficienti per lavorare come stack o coda.

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

Se vuoi saperne di più sulla libreria deque e altri tipi di raccolte fornite da Python, puoi leggere la nostra Introduzione all’articolo del modulo Collezioni di Python.

Implementazioni più severe in Python

Se il tuo codice aveva bisogno di uno stack e fornisci unList, non c’è nulla che impedisca a un programmatore di chiamareinsertremove o altre funzioni di elenco che influenzeranno l’ordine del tuo stack! Questo rovina fondamentalmente il punto di definire uno stack, in quanto non funziona più come dovrebbe.

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

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

Per farlo, creiamo un nuovo file chiamato stack_queue.py e definire due classi:

I programmatori che utilizzano il nostro Stack e Queue sono ora incoraggiati a utilizzare i metodi forniti per manipolare i dati, invece.

Esempi

Immagina di essere uno sviluppatore che lavora su un nuovo word processor. Hai il compito di creare una funzione di annullamento, che consente agli utenti di eseguire il backtrack delle loro azioni fino all’inizio della sessione.

Uno stack è la soluzione ideale per questo scenario. Siamo in grado di registrare ogni azione che l’utente prende spingendolo allo stack. Quando l’utente vuole annullare un’azione che faranno pop 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 quei giochi possono eseguire mosse speciali premendo una combinazione di pulsanti. Queste combinazioni di pulsanti possono essere memorizzate in una coda.

Ora immagina di essere uno sviluppatore che lavora a un nuovo gioco di combattimento. Nel tuo gioco, ogni volta che viene premuto un pulsante, viene attivato 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 funzioneranno!

Puoi risolverlo con una coda. Possiamo accodare tutti gli eventi di input man mano che entrano. In questo modo non importa se gli eventi di input hanno poco tempo tra loro, saranno tutti archiviati e disponibili per l’elaborazione. Quando elaboriamo le mosse possiamo eliminarle. Una mossa speciale può essere elaborata in questo modo:

Conclusione

Gli stack e le code sono semplici strutture dati che ci permettono di memorizzare e recuperare i dati in sequenza. In una pila, l’ultimo elemento che entriamo è il primo a uscire. In una coda, il primo elemento che entriamo è il primo uscito.

Possiamo aggiungere elementi a uno stack usando l’operazionepush e recuperare elementi usando l’operazionepop. Con le code, aggiungiamo elementi usando l’operazioneenqueue e recuperiamo elementi usando l’operazionedequeue.

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

Esistono molti casi d’uso reali per stack e code, la loro comprensione ci consente di risolvere molti problemi di archiviazione dei dati in modo facile ed efficace.