Ciao bentornato sul Gate cookie in questo video andremo a vedere la struttura dati pila la pila è un insieme di elementi caratterizzata dal fatto che le operazioni che faccio avvengono sempre alla stessa estremità come dice la parola stessa si può immaginare una pila come una serie di elementi impilati tra di loro immaginate Ad esempio in un ristorante una serie di piatti posizionati uno sopra l'altro e quando dovrò andare ad aggiungerne uno lo andrò ad aggiungere in cima Quando dovrò toglierne uno andrò sempre a toglierlo dalla cima si dice che la pila segue il criterio lifo
Ovvero la Steam first out E infatti l'ultimo elemento aggiunto è il primo ad essere estratto al contrario di questo criterio lifo che caratterizza la pila troviamo il Fifo ovvero il first in first out di cui parleremo nel prossimo video che riguarda le code Ora qui alla lavagna ho riportato un esempio molto molto semplice abbiamo una pila di elementi 1 2 3 4 e andiamo a fare le operazioni che sono Push e pop dove la Push va ad aggiungere un elemento alla pila la pop ne va ad estrarre uno di conseguenza proviamo a fare la Push
di un elemento 5 questo verrà aggiunto in cima e se successivamente andiamo a fare la pop l'elemento che verrà estratto sarà proprio il 5 ora vediamo come implementare una struttura dati di questo tipo all'interno di un programma c andiamo per comodità a definire la dimensione della nostra pila in questo caso la nostra pila potrà contenere un massimo di 5 elementi esattamente come questa disegnata successivamente andiamo ad implementarla con un Array e qui c'è la prima distinzione che si può fare le pile e in realtà vedremo anche le code possono essere realizzate utilizzando un Array oppure
utilizzando delle liste concatenate Qual è la migliore la migliore probabilmente è quella con le liste concatenati in quanto non abbiamo la limitazione di dover definire un numero di oggetti che possono essere all'interno della nostra pila questo perché andando ad utilizzare gli Array quando si dichiara un Array sapete che bisogna andare a inserire il numero di elementi Massimo che è quella Rei può contenere Se noi facciamo invece una pila con una lista scatenata questa cosa non è necessaria e andremo ad utilizzare la memoria dinamica in questo video noi copriremo il Come realizzare una pila utilizzando un
Array per qualsiasi cosa sulle liste concatenate vi rimando al video un po' corposo ma molto esaustivo che abbiamo realizzato sulle liste concatenate quindi definito il numero di elementi e definito il nostro Array con quel numero di elementi andiamo poi a dichiarare anche un'altra costante che chiamiamo Empty per comodità e andiamo a dire che una variabile intera Top è uguale a denti questa cosa equivale a scrivere top uguale a meno 1 Però come vedremo dopo nelle funzioni è molto più comodo avere una scritta del tipo Empty ora Che cos'è top top è l'indice che mi indica
Dove inserire e dove estrarre un certo elemento quindi top mi indicherà in questo caso 4 e in questo caso 5 iniziamo con la funzione push che è la funzione che ci permette di inserire un elemento all'interno della nostra vita la nostra funzione prende In input un elemento che chiamiamo nuovo elemento che è quello che appunto vogliamo aggiungere Limit è il numero di elementi che il nostro re può avere Quindi 5 gli indici di un Array vanno da 0 a 4 Quindi se top che mi indica Dove inserire un nuovo elemento in questo caso è uguale
a Limit meno 1 quindi a 4 significa che la nostra Pila è piena e quindi quello che facciamo è fare un Return Falls possiamo fare un Return false perché abbiamo dichiarato la nostra funzione come booleana quindi in questo caso dove top è uguale al limite -1 significa che si è verificato over Flow perché stiamo cercando di inserire un elemento anche se la pila è piena e quindi andiamo a dire falso non è stata fatta nessuna Push ora piccolo inciso Io per scelta mia ho deciso di implementarla come booleana in modo che una volta che chiamo
questa funzione so che se mi dice falso c'è stato overflow e non è stato aggiunto un elemento se mi dice è vero invece è stato aggiunto un nuovo elemento nulla vi vieta comunque di andare a dichiarare una funzione di tipo Void e qui andare ad esempio a scrivere un bel printf con overflow che vi indica appunto che c'è stato un over Flow e quindi andare poi qui a scrivere ad esempio l'inserimento avvenuto nessuno vi vieta di fare una cosa di questo tipo io però per scelta mia preferisco avere una funzione booleana ora torniamo a noi
abbiamo capito cosa succede nel caso in cui la pila è piena ma nel caso in cui la pila non è piena c'è spazio per contenere un nuovo elemento cosa succede Beh quello che viene fatto è che viene incrementata la nostra variabile top e successivamente vado a dire instacche di Top metti il nuovo elemento ora perché viene incrementata prima e non dopo viene incrementata prima perché il nostro top lo inizializziamo a meno 1 Questo significa che quando abbiamo la nostra pila vuota il nostro top avrà come valore meno 1 che ci indica appunto che la pila
è vuota come abbiamo definito nella nostra costante quando vado ad aggiungere un elemento quello che faccio è incremento top Quindi porto top a zero e all'indice 0 andiamo ad inserire il nuovo elemento se andiamo a fare un'altra Push cosa succede che top è uguale a zero lo vado ad incrementare quindi top uguale a 1 e quello che faccio è inserire un elemento all'interno del mio Array nell'indice 1 e quindi abbiamo i nostri due elementi e ora continuando così con questi casi arriveremo a un certo punto al nostro caso di overflow una cosa che tengo a
precisare che nessuno vi obbliga ad implementare in questo modo la vostra pila Io ho fatto la scelta di avere una funzione booleana e ho fatto la scelta di partire con top uguale a meno 1 Nessuno vi vieta di partire con top a zero cosa potevo fare potevo partire con top a zero e allora qui andare a dire quando top è uguale a limite E allora qui andare a fare prima l'inserimento del nuovo elemento e successivamente andarlo a incrementare e questo funziona ancora quindi quello che faccio è inserisco il primo elemento Beh top è uguale a
zero Quindi faccio l'inserimento nell'indice 0 in di uno e lì è dove avverrà il secondo inserimento quindi faccio un altro inserimento top è uguale a 1 e inserisco lì e incremento top top è uguale a 2 ed è pronto a fare l'inserimento a quell'indice e questa è comunque una scelta implementativa vediamo ora la funzione Pop Pop mi serve per estrarre un elemento e quindi la prima cosa che vado a verificare è se la pila non è vuota se top è uguale a dempty che è il valore a cui l'abbiamo inizializzato Ovvero -1 se è top
è uguale a -1 ritorna -1 Supponendo di avere un Array con soli valori positivi -1 ci indica appunto che sia verificato nel Flow ovvero stai cercando di togliere elementi dalla pila Ma la pila è vuota nel caso in cui c'è almeno un elemento top sarà maggiore o uguale a zero e di conseguenza cosa faccio decremento top e ritorno lo stack di Top più uno ad esempio abbiamo una pila fatta in questo modo se andiamo a fare una pop quello che succede che andremo ad estrarre 5 in questo momento avremo un top che sarà uguale a
4 in questo caso viene decrementato e avrò top uguale a 3 ovvero top mi punterà il valore 4 Quindi questa cella qui e andiamo a restituire il valore del nostro Stack di Top più uno ovvero top è qui ma andiamo a restituire il valore di Top più 1 ovvero 5 che è proprio quello che noi abbiamo eliminato e ora se su questo Noi andiamo a fare un'altra Push però quello che succede È che il nostro top che è uguale a 3 diventa uguale a 4 e qui dentro andremo ad inserire il nuovo elemento ed ecco
spiegato perché si fa il decremento di Top in modo che tra virgolette Andiamo a tagliare via la testa della nostra pila Dopodiché ritorno lo stack di Top più uno ovvero proprio la testa tagliata della pila successivamente sono andato a creare un invece una funzione che mi va a fare la stampa della nostra pila e questo è nel nostro main Ora andiamo a vedere un po' l'output di questo programmino Innanzitutto facciamo un Print Stack il Print Stack sarà lo stack vuoto Dopodiché andiamo a inserire 15 e quello che succede che viene inserito il nostro 15 e
questo lo vediamo perché appunto ho fatto il Print Stack poi inseriamo 6 e vedete che sei viene messo sopra 15 poi inserisco due 21,77 e in ordine abbiamo due 21 e 77 Dopodiché proviamo un altro Push come vedete in questo caso gli elementi sono 5 quindi come abbiamo visto la limitazione dell'utilizzo di un Array è che non posso andare a sforare in questo caso quindi andiamo a verificare il valore di ritorno di Push e qui capite perché ho deciso appunto di dichiarare Push come funzioni booleana perché con questo punto esclamativo vado a verificare se mi
ritorna falso e se mi ritorna falso cosa che mi aspetto perché non ci stanno se elementi nella qualità vado a fare questa stampa che mi dice con Push di 9 si è verificato overflow e la nostra pila non ha subito cambiamenti proseguiamo e facciamo il nostro primo pop e pop va proprio ad estrarre 77 che qui sparisce Poi facciamo un secondo Pop che va a togliere 21 che qui sparisce Dopodiché con questo simpatico while vado a eliminare tutti gli elementi questo Wild potrebbe confondere alcuni di voi ma andiamo ad analizzarlo lentamente abbiamo Innanzitutto una variabile
intera i che assume il valore di Pop Ricordiamoci che cos'è Pop Pop se va a buon fine restituisce il valore cancellato se non va a buon fine mi restituisce Empty ovvero -1 e qui cosa gli dico a questa variabile i ad ogni interazione assegnami il valore ritornato da pop e quindi l'elemento che stai eliminando ma quando questo valore è ritornato da pop e uguale a debiti hai finito Perché hai svuotato tutta 50.000 se vado a tentare di eliminare un'altra volta un elemento quindi qui richiamo Pop quello che mi aspetto e che ho verificato con questo
if e che con questo Pop si è verificato underflow in quanto la pila è vuota bene il video è finito Spero di esserti stato d'aiuto Se è così ti ricordo di iscriverti al canale e di mettere mi piace e noi ci vediamo nel prossimo video sulle code