DOUG LLOYD: Va bene, quindi da questo punto sei probabilmente abbastanza familiare con array e liste concatenate che è due primario strutture di dati che abbiamo parlato per mantenere gruppi di dati di tipi di dati simili organizzata. Ora stiamo andando a parlare di un paio di variazioni su array e liste concatenate. In questo video andremo per parlare di stack. In particolare stiamo andando a parlare una struttura dati detta pila. Richiamo da precedenti discussioni su puntatori e la memoria, che la pila è anche la il nome per un segmento della memoria dove staticamente dichiarato memoria memory-- che nome, variabili che è il nome, et cetera e funzionali strutture che abbiamo anche Esistono stack frame di chiamata. Quindi questa è una struttura di dati pila Non un segmento di stack di memoria. OK. 

Ma che cosa è una pila? Quindi è praticamente solo un speciale tipo di struttura che mantiene i dati in modo organizzato. E ci sono due molto modi comuni per implementare pile utilizzando due strutture dati che siamo già familiarità con, array e liste concatenate. Che cosa rende una speciale pila è il modo in cui abbiamo messo informazioni nella pila, e il modo in cui rimuovere le informazioni dallo stack. In particolare con pile la regola è solo il più recentemente elemento aggiunto può essere rimosso. 

Quindi pensare come se fosse una pila. Stiamo accumulando informazioni su se stesso, e solo la cosa in alto del palo può essere rimosso. Non possiamo rimuovere la cosa sotto perché tutto il resto sarebbe collasso e cadere. Quindi stiamo davvero costruendo uno stack che abbiamo poi rimuovere pezzo per pezzo. A causa di questo ci riferiamo comunemente uno stack come struttura LIFO, last in, first out. LIFO, durano in, first out. 

Quindi, a causa di questa restrizione come le informazioni possono essere aggiunto e rimosso da una pila, non c'è davvero solo due cose che possiamo fare con uno stack. Siamo in grado di spingere, che è il termine che usiamo per l'aggiunta un nuovo elemento all'inizio della pila, o se la pila non esiste e stiamo creando da zero, creando pila in primo luogo sarebbe spingere. E poi pop, che è il genere di CS termine che usiamo per rimuovere il più recente aggiunto elemento dalla sommità della pila. 

Quindi stiamo andando a guardare sia implementazioni, basata sia di matrice e lista collegata based. E stiamo andando a iniziare con matrice a base. Quindi, ecco l'idea di base di ciò che la struttura di dati pila di allineamenti basato sarebbe simile. Abbiamo una definizione digitato qui. All'interno di che abbiamo due membri o campi della struttura. Abbiamo un array. E di nuovo Sto utilizzando il arbitrario valore di tipo di dati. 

Quindi questo potrebbe essere qualsiasi tipo di dati, int char o altri dati digita creato in precedenza. Quindi abbiamo una vasta gamma di capacità di dimensioni. Capacità di essere un chilo definito costante, forse da qualche altra parte nel nostro file. Così notare già con questo particolare implementazione stiamo delimitazione noi stessi come era tipicamente il caso con gli array, che non siamo in grado di ridimensionare in modo dinamico, dove c'è un certo numero di elementi massima siamo in grado di mettere nel nostro stack. In questo caso è elementi di capacità. 

Teniamo anche traccia di la parte superiore della pila. Quale elemento è il più recentemente aggiunto alla pila? E così teniamo traccia di quel in una parte superiore variabile chiamata. E tutto questo viene avvolto insieme in un nuovo tipo di dati denominato una pila. E una volta che siamo creati questo nuovo tipo di dati siamo in grado di trattarlo come qualsiasi altro tipo di dati. Possiamo dichiarare pila s, proprio come potremmo fare int x, o char a. E quando diciamo impilare s, ben cosa succede è si ottiene una serie di memoria accantonato per noi. 

In questo caso la capacità Ho deciso a quanto pare è 10 perché ho un singola variabile di tipo pila che contiene due campi ricordano. Un array, in questo caso va essere un array di interi come è il caso nella maggior parte dei miei esempi. E un'altra variabile intera in grado di memorizzare l'alto, il più recentemente aggiunto elemento allo stack. Così una sola pila di quello che abbiamo appena definito simile a questa. Si tratta di una scatola contenente una matrice di 10 Come saranno numeri interi in questo caso e un'altra variabile intera lì in verde per indicare la parte superiore della pila. 

Per impostare la parte superiore della pila diciamo solo s.top. Ecco come si accede a campo di una struttura di richiamo. s.top uguale a 0 in modo efficace fa questo per il nostro stack. Così ancora una volta abbiamo due operazioni che possiamo eseguire ora. Siamo in grado di spingere e possiamo pop. Cominciamo con spinta. Ancora una volta, spingendo è l'aggiunta di una nuova elemento in cima alla pila. 

Così che cosa abbiamo bisogno di fare in questo array implementazione basata? Bene in generale funzione push sta andando per necessità di accettare un puntatore alla pila. Ora prendere un secondo e pensarci. Perché vogliamo accettare un puntatore alla pila? Ricordiamo dal video precedenti su scope delle variabili e puntatori, cosa accadrebbe se abbiamo appena inviato pila, s piuttosto come parametro? Che cosa sarebbe effettivamente essere passato lì dentro? Ricordate che stiamo creando una copia quando si passa ad una funzione a meno che non usiamo i puntatori. E così questa funzione premere esigenze accettare un puntatore alla pila così che realmente stiamo cambiando lo stack abbiamo intenzione di cambiare. 

L'altra cosa spinta probabilmente vuole accettare è un dato di valore tipo. In questo caso, ancora una volta, un numero intero che stiamo andando a aggiungere alla cima della pila. Così abbiamo i nostri due parametri. Che cosa stiamo andando a ora fare all'interno di spinta? Beh, semplicemente, stiamo solo andando ad aggiungere tale elemento in cima alla pila e quindi cambiare dove la parte superiore la pila è, che s puntino valore superiore. Quindi questo è quello che una funzione dichiarazione di spinta potrebbe apparire come in un matrice a base di implementazione. 

Anche in questo caso non è una regola ferrea che si potrebbe cambiare questo e hanno essa vari in modi diversi. Forse s è dichiarato a livello globale. E così non è nemmeno necessario passare è come parametro. Anche questo è solo un caso generale per spingere. E ci sono diversi i modi per attuarla. Ma in questo caso il nostro spinta sta andando a prendere due argomenti, un puntatore ad una pila e un dato di valore tipo, integer in questo caso. 

Così abbiamo dichiarato s, abbiamo ha detto s.top è uguale a 0. Ora cerchiamo di spingere la numero 28 nello stack. Beh, che cosa significa? Beh, attualmente il cima alla pila è 0. E così ciò che è fondamentalmente sta per accadere è stiamo andando a bastone il numero 28 in posizione di matrice 0. Piuttosto semplice, giusto, che era la parte superiore e ora siamo pronti per partire. E poi abbiamo bisogno di cambiare ciò che cima alla pila sarà. Così la prossima volta spingiamo un elemento, abbiamo intenzione di conservarlo in posizione matrice, probabilmente non 0. Non vogliamo sovrascrivere quello che abbiamo appena messo lì. E così ci limiteremo a spostare la parte superiore a 1. Che rende probabilmente senso. 

Ora, se vogliamo mettere un altro elemento nello stack, diciamo che vogliamo spingere 33, bene ora stiamo solo andando a prendere 33 e metterlo al numero posizione di matrice 1, e quindi modificare la parte superiore della nostra impilare essere matrice posizione numero due. Quindi, se la prossima volta che vogliamo spingere un elemento nello stack, Sarà messo in ordine di posizione 2. E facciamolo più una volta. Ti spingere 19 al largo delle pile. Metteremo 19 in ordine di posizione 2 e modificare cima della nostra pila per essere luogo di matrice 3 quindi se la prossima volta che bisogno di fare una spinta che siamo a posto. 

OK, così che sta spingendo in poche parole. Che dire di popping? Così popping è il tipo di controparte a spingere. E 'quanto togliamo i dati dallo stack. E nei bisogni pop generali a fare quanto segue. Deve accettare un puntatore pila, sempre nel caso generale. In qualche altro caso si potrebbe hanno dichiarato lo stack a livello globale, nel qual caso non c'è bisogno di passare in quanto ha già accesso ad essa come variabile globale. Ma allora che cosa altro abbiamo bisogno di fare? Bene siamo stati Incremento la parte superiore della pila di spinta, quindi stiamo probabilmente andando a voler decrementare cima alla pila pop, giusto? E poi, naturalmente, stiamo anche andando a voler per restituire il valore di rimuovere. Se stiamo aggiungendo elementi, vogliamo per ottenere elementi di uscire più tardi, probabilmente in realtà desidera memorizzare loro, così abbiamo non solo eliminarli dal impilare e poi non fare nulla con loro. Generalmente se siamo spingendo e popping qui vogliamo conservare questo informazioni in modo significativo e così non fa senso di scartare proprio questo. Quindi, questa funzione dovrebbe probabilmente restituire un valore per noi. 

Quindi questo è quello che una dichiarazione di schiocco potrebbe apparire come lì in alto a sinistra. Questa funzione restituisce Dati di valore di tipo. Ancora una volta siamo stati con interi in tutto. E accetta un puntatore a una pila come l'unico argomento o un parametro unico. Allora, cosa sta pop intenzione di fare? Diciamo che vogliamo ora pop un elemento fuori di s. Così ricordo che ho detto che stack sono scorsa in, first out, strutture dati LIFO. Quale elemento sta per essere rimosso dalla pila? Hai fatto a indovinare 19? Perché avreste ragione. 19 era l'ultimo elemento abbiamo aggiunto alla impilare quando stavamo spingendo elementi su, e così sta andando alla prima elemento che viene rimosso. E 'come se dicessimo 28, e poi abbiamo messo 33 su di esso, e abbiamo messo 19 in cima a quello. L'unico elemento che possiamo decollare è 19. 

Ora, nello schema qui quello che ho fatto è una sorta di cancellata 19 dalla matrice. Questo non è in realtà quello che andremo a fare. Stiamo solo andando a tipo di far finta che non c'è. E 'ancora lì a quella posizione di memoria, ma stiamo solo andando a ignorarlo cambiando all'inizio della nostra pila dall'essere 3 a 2. Quindi, se dovessimo ora spingere un altro elemento nello stack, sarebbe sovrascrivere 19. 

Ma non passare attraverso la briga di cancellazione 19 dalla pila. Possiamo solo far finta che non ci sia. Ai fini della pila è andato se cambiamo la parte superiore per essere 2 invece di 3. Va bene, così che era praticamente. Questo è tutto quello che dobbiamo fare al pop un elemento fuori. Facciamolo ancora. Così ho evidenziato in rosso qui a indicano che stiamo facendo un'altra chiamata. Andiamo a fare la stessa cosa. 

Quindi cosa succederà? Beh, stiamo andando a memorizzare 33 in x e stiamo andando modificare la cima della pila a 1. In modo che se fossimo ora a spingere un elemento nella pila che siamo andando a fare in questo momento, cosa succederà è che andremo sovrascrittura matrice numero di posizione 1. Così che il 33 che è stato una sorta di sinistra dietro che abbiamo appena finto non c'è più, stiamo solo andando per clobber e mettere 40 lì, invece. E poi, naturalmente, da quando abbiamo fatto una spinta, stiamo andando a incrementare il cima alla pila da 1 al 2 in modo che se ora aggiungiamo un altro elemento che sarà andare in array di posizione numero due. 

Ora liste collegate sono un altro modo per implementare stack. E se questa definizione sulla schermo qui sembra familiare a voi, è perché sembra quasi esattamente lo stesso, infatti, è più o meno è esattamente il stessa come una lista concatenata, se vi ricordate dalla nostra discussione di singolarmente concatenata liste in un altro video. L'unica restrizione qui è per noi come i programmatori, non siamo autorizzati a inserire o eliminare in modo casuale dalla lista concatenata che potremmo fare in precedenza. Siamo solo ora in grado di inserire ed eliminare da la parte anteriore o la parte superiore della collegata lista. Questo è davvero l'unico differenza però. Questa è comunque una lista concatenata. E 'solo la restrizione sostituzione su noi stessi come i programmatori che cambia in una pila. 

La regola qui è quello di mantenere sempre un puntatore alla testa di una lista collegata. Questo è ovviamente un genere importante regola prima. Per concatenata lista in ogni caso si solo bisogno di un puntatore alla testa per avere tale catena di essere in grado di fare riferimento ad ogni altro elemento nella lista collegata. Ma è particolarmente importante con uno stack. E così generalmente sei andando a realtà vuole questo puntatore ad una variabile globale. E 'probabilmente andando a ancora più facile in questo modo. Ma quali sono gli analoghi di spinta e pop? Destra. Quindi spingere di nuovo è l'aggiunta di un nuovo elemento allo stack. In una lista collegata che significa che stiamo andando ad avere per creare un nuovo nodo che siamo andando ad aggiungere alla lista linkata, e quindi seguire i passaggi accurati che in precedenza abbiamo delineato nelle liste semplicemente concatenate per aggiungerlo la catena senza rompere la catena e perdere o orfano qualsiasi elementi della lista collegata. E questo è fondamentalmente ciò che piccolo blob di testo ci riassume. E diamo uno sguardo a come un diagramma. 

Quindi, ecco la nostra lista collegata. Esso contiene contemporaneamente quattro elementi. E più perfettamente ecco la nostra impilare contenente quattro elementi. E diciamo ora vogliamo spingere un nuovo elemento su questo stack. E vogliamo spingere una nuova elemento il cui valore dei dati è di 12. Beh, quello che abbiamo intenzione di fare? Ben prima che andremo a spazio malloc, dinamicamente allocare spazio per un nuovo nodo. E, naturalmente, subito dopo facciamo una chiamata a malloc abbiamo sempre assicuratevi di controllare per nulla, perché se abbiamo ottenuto nulla di nuovo c'era qualche tipo di problema. Noi non vogliamo che nulla dereference puntatore o si subiranno un guasto seg. Questo non va bene. Così abbiamo malloced del nodo. Si suppone che abbiamo avuto successo qui. Stiamo andando a mettere in 12 il campo di dati di tale nodo. Ora ti ricordi quale dei nostri puntatori muove prossimo in modo da non rompere la catena? Abbiamo un paio di opzioni qui, ma l'unico che sta per essere sicuri è quello di impostare le notizie accanto puntatore scegliere la vecchia testa della lista o quello che sarà presto il vecchio capo della lista. E ora che tutti i nostri elementi sono incatenati insieme, possiamo solo passare lista per puntare nello stesso posto che fa nuova. Ed ora abbiamo effettivamente spinto un nuovo elemento sulla parte anteriore della pila. 

Pop vogliamo solo eliminare il primo elemento. E così in fondo ciò che dobbiamo fare qui, bene dobbiamo trovare il secondo elemento. Alla fine che diventerà il nuovo testa dopo cancelliamo il primo. Quindi abbiamo solo bisogno di partire da All'inizio, spostare uno avanti. Una volta che abbiamo una stretta su un avanti di dove siamo attualmente siamo possiamo eliminare il primo sicuro e allora possiamo semplicemente spostare la testa per puntare a quello che era il secondo mandato e quindi ora è il primo dopo che nodo è stato eliminato. 

Quindi, di nuovo, dare un'occhiata a come un diagramma noi vuole ora un pop elemento off di questa pila. Allora cosa facciamo? Beh, stiamo andando a creare primo un nuovo puntatore che sta succedendo per puntare allo stesso punto come la testa. Stiamo andando a spostare di una posizione avanti dicendo pari trav trav prossimo ad esempio, che avanzerebbe il puntatore trav uno posizione avanzata. Ora che abbiamo un tenere sul primo elemento attraverso il puntatore chiamato lista, e il secondo elemento tramite un puntatore chiamato trav, possiamo cancellare con sicurezza che primo elemento dalla pila senza perdere il resto della catena perché avere un modo per riferirsi al secondo elemento trasmette attraverso la puntatore chiamato trav. 

Così ora possiamo liberare quel nodo. Possiamo liberare lista. E poi tutto quello che dobbiamo fare ora è passare lista per punto nello stesso posto che trav fa, e siamo sorta di schiena dove siamo partiti prima abbiamo spinto 12 sul in primo luogo, a destra. Questo è esattamente dove eravamo. Abbiamo avuto questo stack quattro elementi. Abbiamo aggiunto un quinto. Abbiamo spinto un quinto elemento, e poi noi spuntato che la maggior parte di recente elemento aggiunto indietro. 

Questo è davvero più o meno tutto quello che c'è a pile. È possibile implementare come array. È possibile implementare come liste collegate. Ci sono, naturalmente, altri le modalità di applicazione pure. Fondamentalmente la ragione useremmo pile è quello di mantenere i dati in modo tale che il più recentemente aggiunto elemento è la prima cosa che siamo andando a voler tornare. Sono Doug Lloyd, questo è CS50.