Strutture dati — Stack

Nella programmazione, dobbiamo lavorare con moltissimi dati. Pertanto abbiamo bisogno di archiviare e organizzare i dati in modo efficiente. Questo è quando le strutture dati tornano utili. Possiamo utilizzare strutture di dati per archiviare, organizzare, elaborare e recuperare dati. Le strutture dei dati possono essere ulteriormente suddivise in 2 categorie a seconda di come sono disposti i dati.

In questo articolo parlerò di strutture lineari ( Stacks ). Rispetto alle strutture non lineari, i concetti alla base delle strutture lineari sono relativamente più facili da comprendere. Alcuni esempi di tali strutture lineari sono Stack, Queues, Deques e Lists. Esamineremo ciascuna di queste strutture di dati una per una. Si può pensare che queste strutture lineari abbiano 2 estremità. (anteriore e posteriore | sinistra e destra | sopra e sotto) Alcune strutture lineari consentono l'inserimento o la rimozione di elementi a una sola estremità, mentre alcune strutture lo consentono a entrambe le estremità.

1. Pile

• Quindi, in sostanza, una pila è una raccolta ordinata di elementi in cui l'inserimento e la rimozione degli elementi avvengono alla stessa estremità. Questa estremità è comunemente nota come "Top". Inoltre, la fine, opposta alla parte superiore è nota come "Bottom"
• Inoltre, gli elementi più recenti sono nella parte superiore, mentre quelli più vecchi sono nella parte inferiore. Pertanto l'ordine di rimozione degli elementi dalla pila sarà inverso rispetto all'ordine di inserimento degli elementi nella pila.
• Ora che abbiamo una buona comprensione del comportamento di uno stack, diamo un'occhiata ad alcune importanti operazioni connesse con la struttura dei dati dello stack.
• push (elemento) — Il metodo push viene utilizzato per inserire un elemento in cima allo stack.
• pop ()- Il metodo pop viene utilizzato per rimuovere l'elemento in cima alla pila
• peek () — Il metodo Peek viene utilizzato per vedere l'attuale elemento più in alto dello stack.
• size () — Restituisce il numero di elementi presenti nello stack
• is_empty () — Questo metodo è utile per verificare se lo stack è vuoto o meno
• Si noti che qui la fine dell'elenco è considerata la parte superiore della pila. (Complessità temporale — O(1)) Possiamo considerare l'inizio dell'elenco come la parte superiore dello stack, tuttavia, non sarebbe molto efficiente poiché la complessità temporale sarebbe O(n) quando inseriamo o estraiamo elementi.
• Quando consideriamo la fine della lista come la cima della pila


• Ora che sappiamo come implementare uno stack, diamo un'occhiata ad alcuni scenari in cui l'uso della struttura dei dati dello stack diventa vitale.
• Conversioni del sistema numerico
• Prima di tutto vediamo come possiamo convertire un numero decimale in binario usando uno stack.

• Ora estendiamo l'algoritmo di cui sopra per convertire un numero decimale in qualsiasi sistema numerico compreso tra 2 e 16.


Quasi tutti i linguaggi di programmazione là fuori usano le parentesi nella sua sintassi. Pertanto se non usiamo le parentesi in maniera bilanciata potrebbe verificarsi un errore di sintassi.

• Nella prima fase di questo problema, prenderò in considerazione solo un tipo di parentesi, diciamo (). Quello che dobbiamo verificare è se l'insieme delle parentesi è bilanciato o meno. Se bilanciato dovremmo restituire vero, altrimenti falso.
• ( ) — equilibrato | ( ( ) ) — equilibrato | ( ( ( )( ) ) ) — equilibrato
• ( ( ) non equilibrato | ( ) ( ) ( — non equilibrato | ( ( ( ) ) ( ) — non equilibrato

• ( [ ] ) — equilibrato | ( ( ) { } ) — equilibrato | ( ( [ { } [ ] ] ) ) — equilibrato
• ( ( ) non bilanciato | ( ) { } ]— non bilanciato | ( ( { } [ [ ) — non bilanciato


3. Invertire una stringa utilizzando uno stack



4. Infisso | Notazione suffisso e prefisso

In informatica, abbiamo a che fare con molte espressioni aritmetiche. Un'espressione è composta da operatori (+, -, *, / etc) operandi (A, B, c, d, 1, 2,… ) e simboli come le parentesi.

• Infix Notation — In questa notazione l'operatore è posto tra gli operandi. (<operando> <operatore> <operando>)
• Se l'espressione è composta da un solo operatore (es: 2 + 3, 4 * 6) possiamo risolvere immediatamente l'espressione. Tuttavia, se l'espressione ha più di un operatore, non possiamo risolverla direttamente a causa dell'ambiguità dell'espressione. Considera questa espressione 1 + 4 * 5. Se eseguiamo prima l'addizione otteniamo la risposta come [ ( 1 + 4 ) * 5 ] = 25 e se eseguiamo prima la moltiplicazione otteniamo la risposta come [1 + (4 * 5 )] = 21. Come puoi vedere c'è qualche ambiguità in questa notazione. Pertanto per risolvere questo usiamo qualcosa chiamato "precedenza dell'operatore". Secondo la precedenza dell'operatore, la moltiplicazione dovrebbe essere eseguita prima dell'addizione. Quindi la risposta corretta dovrebbe essere 21, non 25.
• Fondamentalmente, per risolvere un'espressione scritta in notazione infissa dobbiamo seguire una serie di regole, così come dobbiamo anche aggiungere le parentesi. Quindi questa notazione potrebbe richiedere più memoria durante la risoluzione. Quindi, per superare queste sfide, gli scienziati hanno escogitato altre due notazioni, prefisso e postfisso.
• Nella notazione prefissa, l'operatore è posto prima degli operandi, (<operatore><operando> <operando>) mentre nella notazione postfissa l'operatore è posto dopo gli operandi. (<operando> <operando><operatore>)
• Rispetto alla notazione infissa, le altre due notazioni sono piuttosto difficili da leggere e comprendere per un essere umano. Tuttavia, poiché queste due notazioni non hanno simboli aggiuntivi come le parentesi, e non contengono alcuna ambiguità, le espressioni scritte in questi 2 formati possono essere facilmente lette dai computer.


• Valutazione di un'espressione postfissa : Quando dobbiamo valutare un'espressione postfissa dovremmo iniziare la scansione da sinistra finché non troviamo un operatore. Una volta trovato un operatore dobbiamo eseguire la relativa operazione algebrica sui primi 2 operandi a sinistra dell'operatore.

• Prima di tutto è necessario rimuovere tutti gli spazi nel nostro input. Quindi dobbiamo usare il metodo split. Quindi dobbiamo scansionare la nostra espressione da sinistra a destra. Se incontriamo un numero, dobbiamo inserirlo nella pila. Se incontriamo un operatore, dobbiamo estrarre 2 degli elementi più in alto nel nostro stack. Quindi dobbiamo chiamare la nostra funzione di supporto per eseguire l'operazione aritmetica. Dopodiché inseriremo il risultato nello stack. Una volta terminata la scansione, restituiremo ciò che è rimasto nel nostro stack, che è la risposta per l'espressione postfissa valutata.


• Ora vediamo come possiamo convertire un'espressione in formato infisso in postfisso usando Python.