Doug LLOYD: U redu, tako da po ovom trenutku koji ste vjerojatno prilično upoznat s polja i povezane liste koji je dva primarna strukture podataka koje smo govorio o za čuvanje seta Podaci sličnih tipova podataka u organizaciji. Sada ćemo razgovarati o nekoliko varijacija na polja i povezane liste. U ovom videu ćemo razgovarati o dimnjaka. Naime ćemo razgovarati o struktura podataka naziva stog. Podsjetimo iz prethodnih rasprava O upućuje i memoriju, da je stog je također ime za segment memorije gdje statički proglasio memory-- memorije koja vas ime, varijable koje ime, i cetera i funkcija okviri koje smo također Poziv stoga okviri postoje. Dakle, to je struktura stog podataka Ne snop segment memorije. U REDU. 

No, ono što je stog? Dakle, to je prilično mnogo samo posebna vrsta strukture koji održava podatke na organiziran način. A tu je dvije vrlo uobičajene načine za provedbu hrpe pomoću dvije strukture podataka da smo već upoznati s, polja i povezane liste. Što čini stog posebna je Način na koji smo stavili podatke u stog, a način na koji se ukloniti podatke iz dimnjaka. Posebno s hrpom pravilo je samo najviše Nedavno dodan element može biti uklonjena. 

Dakle, razmišljam o tome kao da je snop. Mi piling podatke na vrhu sebi, a samo stvar na vrhu pilota može biti uklonjena. Ne možemo ukloniti stvar ispod jer sve drugo bi propasti i pasti. Tako smo zapravo gradi stog da ćemo onda morati ukloniti komad po komad. Zbog toga smo često odnose na stog kao LIFO strukture, trajati u, prvi van. LIFO, trajati u, prvi van. 

Dakle, zbog ovog ograničenja Kako informacije mogu se dodati i uklonjen iz dimnjaka, tu je stvarno samo dvije stvari koje možete učiniti s hrpom. Možemo gurnuti, koji je Izraz koji koristimo za dodavanje novi element na vrhu stog, ili ako je stog ne postoji a mi smo ga stvara od nule, stvara snop na prvom mjestu će biti poduzetan. I onda pop, to je vrsta CS Pojam koristimo ukloniti posljednje dodao elementa s vrha dimnjaka. 

Tako ćemo pogledati kako implementacije, i niz temelji i povezani popis temelji. I idemo početi s nizom temelji. Dakle ovdje je osnovna ideja o tome što Niz temelji struktura snop podataka će izgledati. Imamo definiciju upisali ovdje. Unutar da imamo dva člana ili područja strukture. Imamo niz. I opet sam pomoću proizvoljna tip podataka vrijednost. 

Dakle, to može biti bilo koji tip podataka, int char ili neke druge podatke upišite ste prethodno stvorili. Dakle, imamo niz veličine kapaciteta. Kapacitet se funta definirana stalna, možda negdje drugdje u našoj datoteci. Dakle, primijetite već s ovom Provedba smo granični sami kao što je obično slučaj s polja, koji se ne može dinamički mijenjati veličinu, gdje postoji određeni broj elemenata koji najviše možemo staviti u našem stog. U ovom slučaju to je elemente kapaciteta. 

Također smo pratiti na vrhu dimnjaka. Koji element je najviše Nedavno dodani stog? I tako smo pratiti kako u varijablu naziva vrhu. I sve to dobiva zamotan zajedno u novu vrstu podataka naziva stog. I jednom smo stvorili ovaj novi tip podataka možemo ga tretirati kao bilo koje druge vrste podataka. Možemo proglasiti stog s, baš kao i smo mogli učiniti int x, y ili char. A kada kažemo stog e, i što se događa je smo dobili set memorije izdvojiti za nas. 

U ovom slučaju svojstvu Ja očito nisam odlučila 10 jer sam dobio jedna varijabla tipa stog koji sadrži dva polja sjetiti. Niz, u ovom slučaju ide se niz brojeva kao što je slučaj u većini mojih primjera. I još jedna varijabla broj sposoban za pohranu na vrhu, najviše je nedavno dodao element dimnjaka. Dakle, jedan jedini snop što smo Samo definirana izgleda ovako. To je kutija niz od 10 što će biti integers u ovom slučaju i još jedna varijabla ima cijeli zeleno ukazati na vrhu dimnjaka. 

Za postavljanje vrhu stog mi samo reći s.top. Tako ćemo pristupiti Područje opoziva strukture. s.top jednak 0 učinkovito to čini na naše stog. Dakle, opet imamo dvije operacije da možemo obaviti danas. Možemo gurnuti i mi možemo pop. Počnimo s pritiskom. Opet, pritom je dodao novi Element na vrhu snopa. 

Dakle, ono što trebamo učiniti u ovaj niz se temelji primjena? Pa općenito funkcija push ide morati prihvatiti pokazivač na stog. Sada uzmi drugi i razmišljati o tome. Zašto bi želimo prihvatiti pokazivač na stog? Podsjetimo iz prethodnih videa na promjenjiva opseg i naputke, što će se dogoditi ako mi samo poslali stog, s dosta u kao parametar? Što bi zapravo biti donesen tamo? Zapamti mi stvara kopiju kad smo ga proći u funkciji osim ako koristimo naputke. I tako ova funkcija gurnuti potrebama prihvatiti pokazivač na stog tako da smo zapravo mijenja stog namjeravamo mijenjati. 

Druga stvar gurati vjerojatno želi prihvatiti je element podataka tipa vrijednosti. U tom slučaju, jednom, cijeli broj koji ćemo dodati na vrhu dimnjaka. Dakle, imamo naše dvije parametre. Što ćemo Sada to unutar pritiskom? Pa, jednostavno, samo ćemo dodati taj element na vrhu snopa a zatim promijenite gdje vrh snop je da s točke vrh vrijednosti. Dakle, to je ono funkcija prijava za guranje možda izgledati u Niz-based implementacije. 

Opet to nije teško i brzo pravilo koji bi mogao promijeniti ovaj i imaju varira na različite načine. Možda je proglašen na globalnoj razini. I tako da ne morate čak ni proći što je kao parametar. To je opet samo Općenito slučaj za guranje. A tu su i različite načina da ga provede. No, u ovom slučaju naš Pritisni će potrajati dva argumenta, pointer na hrpu i element podataka tipa integer vrijednost, u ovom slučaju. 

Tako smo proglasili S, mi rekao s.top jednak 0. Sada gurnite Broj 28 na stog. Pa što to znači? Pa trenutno vrhu snopa 0. I tako ono što je u osnovi će se dogoditi je ćemo staviti broj 28 u polja položaj 0. Prilično jednostavan, zar ne, da je bio vrh, a sada smo si dobar to ići. I onda moramo promijeniti ono što na vrhu dimnjaka će biti. Tako da sljedeći put guramo element u, ćemo ga pohraniti u Položaj polje, vjerojatno nije 0. Mi ne želite prebrisati što smo upravo tamo stavili. I tako ćemo samo premjestiti na vrh na 1. To vjerojatno ima smisla. 

Sada, ako želimo staviti još jedan element na stog, kažu želimo gurati 33, i sad mi samo uzeti 33 i staviti ga na mjesto broj polja 1, a zatim promijenite vrhu naše stog se niz lokacija broj dva. Dakle, ako sljedeći put želimo gurati element na stog, to će se staviti u položaj 2 polja. I neka je učiniti da se još jednom. Mi ćemo gurnuti 19 off od hrpe. Mi ćemo staviti 19 u polja položaju 2 i promijeniti na vrhu naše stog se niz lokacija 3 pa ako se sljedeći put trebate napraviti poticaj da si dobar to ići. 

U redu, tako da je gura u malom. Što je iskakanje? Dakle iskakanje je vrsta kolega na guranje. To je kako smo ukloniti podatke iz dimnjaka. I općenito pop potrebama učiniti sljedeće. To treba prihvatiti pokazivač do stog, opet u općenitom slučaju. U nekom drugom slučaju možda proglasio stog na globalnoj razini, u tom slučaju ne morate proći u jer već ima pristup do njega kao globalna varijabla. Ali onda što još trebamo napraviti? Pa smo se povećavati vrh dimnjaka u guranje, tako da smo vjerojatno idući u ištanje da dekrementirati vrhu snopa pop, zar ne? I onda, naravno, također ćete želite vratiti vrijednosti koje smo uklonili. Ako ste se dodavanjem elemenata, želimo dobiti elemente iz kasnije, vjerojatno je zapravo želite ih spremiti tako da ne samo ih izbrisati iz stog a zatim učinite ništa s njima. Općenito, ako smo guranje i iskakanje ovdje želimo pohraniti Informacije na smislen način pa to ne čine smisla samo ga odbaciti. Dakle, ova funkcija trebala vjerojatno vratiti vrijednost za nas. 

Dakle, to je ono što je deklaracija za pop Možda izgleda kao da se u gornjem lijevom. Ova funkcija vraća Podaci tipa vrijednosti. Opet smo bili pomoću integers tijekom. I to prihvaća pokazivač na stog kao njezin jedini argument ili jedini parametar. Dakle, ono što je pop učiniti? Recimo da želimo sada pop element off s. Dakle, zapamtite što sam rekao da su prošle hrpe u, prvi van, LIFO strukture podataka. Element koji će ukloniti iz dimnjaka? Jeste li pogoditi 19? Zato što bi u pravu. 19 je bio posljednji element dodali smo na stog kad smo pritom elemente na, pa to će prvi element koji dobiva uklonjen. To je kao da smo rekli 28, a onda smo stavili 33 na vrhu, i stavili smo 19 na vrhu toga. Jedini element koji možemo poletjeti je 19. 

Sada u dijagramu ovdje ono što sam učinio je vrsta izbrisani 19 iz polja. To nije zapravo što ćemo učiniti. Samo ćemo se vrste od pretvarati da ne postoji. To je još uvijek tamo u to mjesto u memoriji, ali mi jednostavno ide ignorirati promjenom vrh našeg dimnjaka od toga 3 na 2. Dakle, ako bismo sada gurnuti još jedan element na stack, to bi više pisati 19. 

Ali nemojmo ići kroz nevolje brisanja 19 iz dimnjaka. Mi samo možemo se pretvarati da ne postoji. Za potrebe stog što je otišao, ako mijenjamo vrh da bude 2 umjesto 3. U redu, tako da je uglavnom to. To je sve što trebamo učiniti pop element off. Idemo to učiniti opet. Pa sam ga istaknute crvenom bojom ovdje da ukazuju činimo drugi poziv. Mi ćemo učiniti istu stvar. 

Dakle, što će se dogoditi? Pa, idemo za pohranu 33 u X i idemo za promjenu vrhu snopa do 1. Tako da, ako smo sada gurne Element u stog što smo učiniti upravo sada, što će se dogoditi se idemo prebrisati Niz položaj broj 1. Tako da 33 koja je vrsta ostavi iza toga smo samo pretvarao ne postoji više, samo mi ide to clobber i staviti 40 tamo umjesto. I onda, naravno, jer smo napravili gurati, ćemo povećajte vrhu snopa 1-2 tako da ako mi sada dodati još jedan element da će ići u polja mjesto broj dva. 

Sada povezani popisi su drugi način provoditi hrpe. A ako ovoj definiciji as Zaslon ovdje izgleda poznato na vas, to je zato što izgleda gotovo isti, u stvari, to prilično mnogo je točno Isto kao popis za pojedinačno povezani, ako sjetiti iz naše rasprave o pojedinačno povezane liste u drugom videu. Jedino ograničenje ovdje je za nas kao programera, nećemo dopustiti da umetanje ili brisanje slučajno Na popisu pojedinačno povezan koje smo prethodno mogli učiniti. Možemo tek sada umetnuti i izbrisati iz prednje ili na vrhu povezani Popis. To je stvarno jedini Razlika ipak. To je inače List pojedinačno povezani. To je samo ograničenje zamijenivši na sebe kao programera koji ga mijenja u stog. 

Pravilo je da se ovdje uvijek održavati pokazivač na glavu popisa povezane. To je, naravno, općenito važno pravilo prvi. Za pojedinačno povezani ionako vam popis samo trebate pokazivač u glavu kako bi se taj lanac moći uputiti na svakom drugom elementu na popisu povezane. Ali to je osobito važno s hrpom. I tako uglavnom si će zapravo žele ovo pokazivač se globalna varijabla. Vjerojatno će biti još lakše na taj način. Pa što su analozi guranje i pop? Tako je. Pa opet gura se dodavanjem novi element na stack. Na popisu povezani da znači da ćemo imati stvoriti novi čvor koji smo će dodati na popis povezani, a zatim slijedite korake pažljive koje smo prethodno navedeno u pojedinačno povezanim popisima biste ga dodali na lanac bez razbijanje lanca i gubitka ili orphaning bilo Elementi popisa povezani. I to je zapravo ono koje Malo blob teksta postoji sažima. I neka je pogledati na to kao dijagram. 

Dakle, ovdje je naš popis povezani. On istodobno sadrži četiri elementa. I više savršeno ovdje je naš stog sadrži četiri elementa. I recimo da sada žele guranje nove stavke na ovu hrpu. I želimo gurati novi Stavka čijim podacima je vrijednost 12. Pa što ćemo učiniti? Pa prvo ćemo malloc prostor, dinamički izdvojiti prostor za novi čvor. I naravno odmah nakon smo uputili poziv da mi se uvijek malloc pobrinite se da provjerite za ništa, jer ako smo null natrag postoji neka vrsta problema. Mi ne želimo dereference tom null pokazivač ili ćete trpjeti grešku SEG. To nije dobro. Tako smo malloced čvora. Mi ćemo pretpostaviti da smo imali uspjeha ovdje. Idemo staviti 12 u polje podataka tog čvora. Sada Sjećate li se koji od naših pokazivača se sada tako da ne razbiti lanac? Imamo nekoliko mogućnosti, ali ovdje jedini koji će se sigurno je postaviti sljedeća vijest pokazivač točka na staru glavu na popis ili što će uskoro biti Stari šef na popisu. I sada da svi naši elementi ulancane, mi samo može kretati popis ukazati na istom mjestu da nova radi. I sada smo uspješno gurnuo Novi element na prednjem dijelu dimnjaka. 

Da mi pop jednostavno želite izbrišite taj prvi element. I tako u osnovi ono moramo učiniti ovdje, i moramo naći drugi element. Na kraju da će postati novi glavu nakon što izbrišete prvi. Dakle, samo mi treba početi od početak, kretati jedan naprijed. Nakon što smo dobili držite na jednom naprijed gdje smo trenutno jesmo možete izbrisati prvi sigurno a onda mi samo možemo pomaknuti glavu ukazati na ono što je bio Drugi pojam, a onda sada je prvi nakon toga čvor je izbrisana. 

Pa opet, uzimajući pogled na to kao dijagram smo želim sada pop Element s ovog stog. Dakle, što nam je činiti? Pa mi smo prvi će stvoriti novi pokazivač što se događa ukazati na istom mjestu kao i glave. Ćemo ga pomaknuti za jedno mjesto naprijed rekavši Trav equals Trav sljedeći primjer, koji će unaprijediti Trav pokazivač jedan Položaj naprijed. Sada kada smo dobili držite na prvom elementu kroz pokazivač naziva liste, a drugi element kroz pokazivač naziva trav, sa sigurnošću možemo izbrisati to Prvi element iz dimnjaka bez gubljenja ostalo lanca, jer mi su način da se odnosi na drugi element proslijediti putem od pokazivač zove Trav. 

Tako sada možemo osloboditi taj čvor. Mi možemo besplatno popis. I onda sve što trebate učiniti je premjestiti popis točku na istom mjestu da trav radi, a mi smo nekako vratiti gdje smo počeli prije gurnuo 12 na prvo mjesto, zar ne. To je točno gdje smo bili. Imali smo četiri elementa stog. Dodali smo petinu. Gurnuo mi petinu Element, a zatim smo ubaci koji je nedavno dodao elemente back off. 

To je stvarno prilično mnogo sve što se gomila. Možete ih implementirati kao polja. Možete ih implementirati kao povezane liste. Postoji, naravno, drugi načine kako ih implementirati kao dobro. Uglavnom je razlog što će koristiti hrpe je održavanje podataka na takav način da je nedavno dodao element je prva stvar smo će htjeti vratiti. Ja sam Doug Lloyd, ovo je cs50.