Con questi importanti metodi spiegati, diamo un’occhiata all’implementazione finale della nostra classe Stack:
I metodi push e pop appaiono esattamente come ci aspettiamo (lines13–32). Possiamo usare il nostro metodo push per creare un inizializzatore personalizzato con alcuni valori variadici (linee 7-11). Inoltre possiamo controllare uno stack vuoto controllando se il nostro rootNode ha un valore (linee 34-36) e avere un metodo di stampa di base che scorre attraverso la nostra lista finché è in grado di accedere ai nodi attraverso la proprietà successiva (linee 38-44).
Un test di base della nostra funzionalità stack è simile a questo:
Sapere come implementare uno stack è una cosa, ma ancora più importante è riconoscere le situazioni per le quali uno stack è adatto. In questa prossima sezione esamineremo tre di questi casi.
Caso d’uso 1: Ordine di inversione
Poiché l’ordine di uno stack è fisso, l’ordine inverso può essere raggiunto molto facilmente facendo scoppiare gli elementi da uno stack e immediatamente su un altro. Non scherzare con gli indici di scambio!
Caso d’uso 2: Test simmetria
Un altro buon caso d’uso per gli stack sta testando la simmetria. Nell’esempio seguente, stiamo testando una stringa di parentesi per garantire che ogni staffa di chiusura sia la controparte corretta di una staffa di apertura precedente.
Iniziamo controllando che il conteggio dei caratteri sia divisibile per due come un numero dispari di caratteri sarebbe immediatamente asimmetrico (riga 6). Successivamente, controlliamo di avere un input valido definendo un set di caratteri di caratteri illegali e quindi controllando che la nostra stringa di input abbia un intervallo nullo di caratteri illegali (righe 7-8). Per verificare che le nostre parentesi di chiusura e apertura corrispondano, le inseriamo in un dizionario come coppie chiave-valore (riga 10). In altre situazioni potresti essere in grado di calcolare il valore inverso senza dover memorizzare le coppie in un dizionario. Quindi abbiamo il nostro stack (linea 11). Lo scopo del nostro stack in questo caso è quello di memorizzare le parentesi di apertura. Mentre iteriamo attraverso la nostra stringa, possiamo verificare se il nostro carattere è una parentesi di apertura testando se è una chiave nel nostro dizionario. Se lo è, lo spingiamo sul nostro stack. Una volta trovata la nostra prima parentesi chiusa, sappiamo che stiamo lavorando attraverso la seconda metà del nostro pattern, quindi impostiamo la nostra prima metà booleana su false (riga 12). Se troviamo altre parentesi di apertura dopo questo punto possiamo controllare il booleano e indicare un test fallito. Per ogni staffa di chiusura, saltiamo fuori l’ultima staffa di apertura e controlliamo se sono una coppia chiave-valore corretta. Ancora una volta, abbiamo solo bisogno di scorrere la stringa una volta, quindi stiamo ottenendo molto valore da un algoritmo lineare.
Caso d’uso 3: Annullare i comandi
Infine, useremo uno stack insieme al modello di comando, per creare una cronologia degli annullamenti. Per iniziare, diamo un’occhiata a un semplice oggetto conto bancario. Ha un saldo e un limite di scoperto e alcuni semplici metodi per depositare e prelevare fondi:
Invece di chiamare direttamente i metodi di deposito e prelievo, possiamo memorizzare le informazioni rilevanti in un comando. Nello snippet sottostante, specifichiamo che tipo di azione vogliamo eseguire con una proprietà enum (deposito o prelievo) e un importo . Memorizziamo anche un booleano per indicare se il comando è stato in grado di essere eseguito (righe 4-11). Si noti che se la richiesta di prelievo supera il limite di scoperto, non accadrà nulla al conto bancario e il booleano riuscito rimarrà falso, altrimenti diventerà vero una volta completato il comando (righe 18-26). Abbiamo due metodi per chiamare o annullare il comando, ognuno prendendo un conto bancario come argomento (righe 18 & 28). Questi metodi prendono il conto bancario e chiamano i suoi metodi di istanza che abbiamo visto nel frammento precedente.
Tornando al conto bancario, possiamo ora introdurre la nostra proprietà commandStack, che è stata inizializzata con il nostro BankAccountType (riga 47). Contrassegniamo i nostri metodi di deposito e prelievo come fileprivate in modo che possano essere accessibili solo dal nostro BankAccountCommand (linee 62 & 66). Ora abbiamo due metodi esposti: process (command:) e undoLastCommand (). Il primo accetta un comando come input, lo esegue con il conto bancario come input e quindi spinge il comando sullo stack. Nel frattempo il metodo undoLastCommand, apre l’ultimo comando fuori dallo stack ed esegue un annullamento (linee 51-60).
Questo è un modello molto semplice e molto potente. Le possibili applicazioni sono infinite e rendono un’esperienza utente soddisfacente.
E ora vediamo il modello in azione:
Wrap Up
In questo articolo, abbiamo esplorato il concetto di stack e comportamento LIFO. Abbiamo implementato il nostro stack utilizzando un elenco doppiamente collegato e dimostrato come alloca e dealloca la memoria al variare della dimensione dello stack. Abbiamo anche esaminato tre casi d’uso comuni per gli stack: inversione, test di simmetria e annullamento. Ognuna di queste tre situazioni venire innumerevoli volte in progetti del mondo reale. Spero che penserai a una pila come una struttura appropriata per gestire tali esigenze. Come sempre, grazie per la lettura!