DOUG LLOYD: Dobre, takže týmto bodom, ktorú ste asi dosť povedomý s polí a spojových zoznamov čo je dva primárne dátové štruktúry sme hovoril o pre vedenie sád Údaje z podobných typov dátových organizovaný. Teraz budeme hovoriť o niekoľko variantov Na pole a spojových zoznamov. V tomto videu budeme hovoriť o komíny. Konkrétne budeme hovoriť o dátovú štruktúru volal hromadu. Pripomeňme z predchádzajúcich diskusií o ukazovatele a pamäť, že zásobník je tiež menovať segment pamäte kde staticky deklaroval memory-- pamäť, ktorá vám meno, premenné, ktoré si len spomeniete, et cetera a funkcie rámy, ktoré sme tiež zásobník volaní rámce existujú. Takže toto je štruktúra zásobník dát nie je stoh segment pamäte. OK. 

Ale čo je to zásobník? Takže je to do značnej miery len Zvláštny druh konštrukcie ktorý udržuje dáta v organizovaným spôsobom. A tam sú dve veľmi obyčajné spôsoby, ako realizovať komíny pomocou dvoch dátových štruktúr že sme už oboznámení s, poľa a spojové zoznamy. Čo robí balík zvláštne, je spôsob, v ktorom sa vložiť informácie do komína, a spôsob, akým odobrať informácie zo zásobníka. Najmä s komíny pravidlo je len tie pridanie element môžu byť odstránené. 

Takže myslíte, že o tom, ako keby je to hromada. Sme hromadia informácie v hornej časti sama o sebe, a to len vec na vrchole hromady môžu byť odstránené. Nemôžeme odstrániť vec pod pretože všetko ostatné by zrúti a spadnúť. Takže sme vlastne budujeme zväzok, ktorý my potom musieť odstrániť kúsok po kúsku. Z tohto dôvodu sme sa obyčajne sa odvolávajú do komína ako štruktúra LIFO, posledný dnu, prvý von. LIFO, posledný dnu, prvý von. 

Takže kvôli tomuto obmedzeniu ako môžu byť informácie pridané do a odstránil z balíka, je to naozaj len dve veci, čo môžeme urobiť s komínom. Môžeme tlačiť, čo je termín používame pre pridávanie nový prvok v hornej časti stack, alebo ak neexistuje stack a my sme ju vytvárať od nuly, vytváranie zásobníka na prvom mieste bude tlačiť. A potom sa pop, to je druh SK termín používame na odstránenie naposledy pridaný prvok z hornej časti zásobníka. 

Takže budeme pozerať na oboch implementácia, a to ako na báze pole a spájať zoznam založený. A ideme začať s radom báze. Tak tu je základná myšlienka o tom, čo štruktúra zásobníka dátové polia na báze vyzerať. Máme definíciu zadaný tu. Vo vnútri, že máme dvoch členov alebo pole štruktúry. Máme pole. A opäť som pomocou ľubovoľná dátový typ hodnoty. 

Takže to môže byť akýkoľvek typ údajov, int char alebo iné údaje typ ste predtým vytvorili. Takže máme rad veľkosti kapacity. Kapacita je pol kila definovaný konštantný, Možno niekde inde v našej súboru. Takže si všimnúť už s týmto konkrétnym implementácia sme ohraničujúca sami seba ako bol typicky prípad s poli, ktoré nemôžeme dynamicky meniť veľkosť, tam, kde je určitý počet z prvkov, ktoré maxima môžeme dať v našej zásobníku. V tomto prípade je to kapacitné prvkami. 

Tiež sledovať v hornej časti zásobníka. Čo element je najviac nedávno pridal do stohu? A tak sme sa sledovať, že v premennej s názvom vrchole. A to všetko dostane zabalené spolu do nového dátového typu s názvom hromadu. A akonáhle sme vytvorili tento nový dátový typ môžeme liečiť ako akýkoľvek iný typ dát. Môžeme prehlásiť zásobníka s, rovnako ako sme mohli urobiť int x, alebo char y. A keď hovoríme stack s, aj čo sa stane sa dostaneme sadu Pamäť zrušil pre nás. 

V tomto prípade kapacity Som sa zrejme rozhodol, 10 preto, že som dostal single premenná typu zásobníka ktorý obsahuje dve polia obehu. Pole, v tomto prípade bude byť pole celých čísel ako je to v prípade väčšiny svojich príkladov. A ďalšie integer premenná schopný uloženie na vrchol, najnovšie pridané element do stohu. Takže jeden jediný zásobník, čo sme Len definované vyzerá takto. Je to krabička obsahujúca Poľa 10, čo bude celé čísla v tomto prípade, a ďalšie integer premenná tam zelene pre indikáciu v hornej časti zásobníka. 

Ak chcete nastaviť hornú z stack sme len povedať s.top. To je, ako sme prístup k poľa štruktúru odvolanie. s.top rovná 0 účinne robí to na náš stack. Takže znovu máme dve operácie že môžeme hrať teraz. Môžeme tlačiť a môžeme pop. Začnime s Push. Opäť platí, že tlačí je pridanie novej prvok na vrchol zásobníka. 

Takže to, čo potrebujeme urobiť v Toto pole implementácia na báze? No všeobecne Funkcia Push sa deje musieť akceptovať Ukazovateľ na zásobníku. Teraz sa druhý a premýšľať o tom. Prečo by sme chceli prijať ukazovateľ na zásobníku? Pripomeňme z predošlých videí na variabilný rozsah a ukazovatele, čo by sa stalo, keby sme práve poslal zásobník, to skôr ako parameter? Čo by vlastne byť odovzdané tam? Pamätajte si, že sme vytvorenie kópie keď sme to odovzdať funkciu ak nebudeme používať ukazovatele. A tak táto funkcia tlačiť potreby prijať ukazovateľ na stohu takže sme skutočne mení, stoh hodláme zmeniť. 

Ďalšia vec, tlak pravdepodobne chce prijať je dátový prvok z hodnoty typ. V tomto prípade je opäť, celé číslo, ktoré budeme pridávať na vrchol zásobníka. Takže máme naše dva parametre. Čo budeme teraz robiť vnútri tlačiť? No, proste sme len tak pridať že element na vrchol stohu a potom zmeňte kde je horná zásobník je, že s dot najvyššiu hodnotu. Takže toto je to, čo funkcia Vyhlásenie Push by mohla vyzerať An array-založené implementácie. 

Opäť to nie je tvrdé a rýchle pravidlo že by ste mohli zmeniť a majú že sa líši v rôznych smeroch. Možno, že s je deklarovaný globálne. A tak ani nepotrebujete odovzdať je ako parameter. To je opäť len všeobecný prípad Push. A tam sú rôzne spôsoby, ako na jeho vykonanie. Ale v tomto prípade je naša Push bude trvať dva argumenty, ukazovateľ zásobníka a dátový prvok typu hodnoty, celočíselné v tomto prípade. 

Takže sme deklarovali ov, my povedal s.top rovná 0. Teraz poďme tlačiť číslo 28 do zásobníka. Tak čo to znamená? No v súčasnosti stoh papiera je 0. A tak to, čo je v podstate bude diať, je budeme držať číslo 28 do umiestnenia poľa 0. Celkom jednoduché, vpravo, že bol vrchol a teraz sme dobrí ísť. A potom musíme zmeniť to, čo horná časť zásobníka bude. Tak, že nabudúce tlačíme prvok v, budeme ukladať do umiestnenie poľa, pravdepodobne nie 0. Nechceme, aby prepísať čo sme práve tam dal. A tak sme si len presunúť odhora 1. To asi dáva zmysel. 

Teraz, ak chceme dať ďalšie prvok do zásobníka, že chceme, aby sa zasadila 33, No teraz sme len bude trvať 33 a dal ho na pole číslo umiestnenia 1, a potom zmeňte na vrchol nášho stack byť poľa číslo umiestnenia dvoch. Takže ak nabudúce chceme tlačiť prvok do zásobníka, to bude dať v mieste poľa 2. A poďme to urobiť ešte raz. Budeme tlačiť 19 preč z komínov. Dáme 19 v mieste poľa 2 a zmeniť na vrchol nášho stohu byť umiestnenie poľa 3 takže ak nabudúce je potrebné, aby sa tlačiť sme dobrí ísť. 

OK, takže sa tlačí v kocke. A čo objavovať? Takže popping je druh náprotivok tlačiť. Je to, ako sme sa odstrániť dáta zo zásobníka. A v sociálne potreby popových urobiť nasledujúce. Je potrebné prijať ukazovateľ na zásobník, opäť vo všeobecnom prípade. V niektorých opačnom prípade by ste mohli vyhlásili stoh globálne, v takom prípade nemusíte ho prejsť V pretože už má prístup k nemu ako globálne premenné. Ale čo iné robiť, musíme urobiť? Tak sme sa postupne horná časť zásobníka v tlačiť, tak sme pravdepodobne bude chcieť pre zníženie hornú časť stohu v pop, že jo? A potom samozrejme sme tiež bude chcieť vrátiť hodnotu, ktoré sme odstrániť. Ak sme pridať prvky, chceme dostať prvky sa neskôr, tak si pravdepodobne skutočne Chcete ich uložiť, takže sme nie len odstrániť z stack, a potom robiť nič s nimi. Všeobecne platí keď sme tlačenie a praskanie tu chceme uložiť tento Informácie zmysluplne a tak to neznamená, že zmysel len odhodiť to. Takže táto funkcia by mala pravdepodobne vrátiť hodnotu k nám. 

Takže to je to, čo vyhlásenie pre pop môže vyzerať, ako by tam v ľavom hornom rohu. Táto funkcia vracia Dáta typu hodnoty. Opäť sme boli s použitím celé čísla v celom texte. A to prijíma ukazovateľ na stack ako jeho jediným argumentom, alebo jediný parameter. Takže to, čo sa pop robiť? Povedzme, že chceme, aby teraz pop prvok preč s. Takže pamätajte Povedal som, že zásobníky sú posledné in, first out, LIFO dátových štruktúr. Ktorý prvok sa chystá byť odstránená zo zásobníka? Vedeli ste asi 19? Vzhľadom k tomu, že budeš v poriadku. 19 bola posledná element sme pridali do stack, keď sme tlačili na prvky, a tak to bude prvý element, ktorý sa odstráni. Je to, ako keby sme povedali 28, a Potom sme dali 33 na vrchole toho, a kladieme 19 na vrchole to. Jediný prvok môžeme zložiť, je 19. 

Teraz v diagrame tu, čo som urobil je druh vymazaný 19 z poľa. To nie je v skutočnosti to, čo budeme robiť. Sme len tak druhu z predstierať, že tam nie je. Je to stále tam v že pamäťové miesto, ale my sme len tak ignorovať zmenou vrchol nášho stohu toho, že 3 až 2. Takže keby sme teraz tlačiť Ďalším prvkom do zásobníka, že by v priebehu písať 19. 

Ale poďme sa prejsť ťažkostí mazanie 19 zo zásobníka. Môžeme len predstierať, že tam nie je. Na účely stohu je to preč, ak zmeníme hornej byť 2 namiesto 3. Dobre, takže to bolo celkom veľa to. To je všetko, čo potrebujete urobiť, pop prvok off. Urobme to znova. Takže som ho zvýraznené červenou tu naznačujú, robíme ďalšie hovor. Chystáme sa urobiť to isté. 

Takže čo sa stane? No, budeme uchovávať 33 v x a ideme pre zmenu v hornej časti zásobníka 1. Takže keby sme teraz tlačiť prvok do zásobníka, ktorý ktorom sme robiť práve teraz, čo sa bude diať sa ideme prepisovanie array číslo umiestnenia 1. Takže to 33, ktorý bol druh vľavo za ktoré sme pred chvíľou predstieral už tam nie je, sme len tak to naložiť a dal 40 tam miesto. A potom samozrejme, od tej doby sme urobili tlak, ideme pre zvýšenie hodnoty Vrchol zásobníka 1-2 takže ak by sme teraz pridať Ďalším prvkom bude to prejsť do poľa umiestnenie číslo dva. 

Teraz spojové zoznamy sú ďalšie spôsob, ako realizovať komíny. A ak je táto definícia na strane Obrazovka tu vyzerá povedome vám, je to preto, že vyzerá skoro presne rovnaký, v skutočnosti, je to celkom veľa je presne rovnaké ako jednotlivo spájať zoznam, Ak si spomínate z našej diskusie o jednotlivo spojené zoznamy v inom videu. Jediné obmedzenie tu je pre nás ako programátori, nie sme dovolené vloženie alebo odstránenie náhodne zo jednotlivo Google zoznamu ktoré sme mohli skôr urobiť. Môžeme sa len teraz vložiť a odstrániť z prednej alebo hornej časti spojené Zoznam. To je naozaj len rozdiel hoci. To je inak single previazaný zoznam. Je to len obmedzenia nahrádzať sami na seba ako programátori, že zmení ho do zásobníka. 

Pravidlo je tu vždy udržiavať ukazovateľ na hlavu prepojeného zozname. Toto je samozrejme všeobecne Dôležité pravidlo ako prvý. Pre jednotlivo spojené zoznam rovnako sa vám potrebujú iba ukazovateľ na hlave aby sa, že reťazec sa odvolať ku každému druhému prvku v pripojenom zozname. Ale je to obzvlášť dôležité s hromadu. A tak všeobecne, že ste bude skutočne chcieť Tento ukazovateľ byť globálne premenná. Je to pravdepodobne bude byť ešte jednoduchšie, že cesta. Takže aké sú analógy tlačiť a pop? Správne. Takže znovu tlačí je pridanie nový prvok do zásobníka. V zozname, ktorý Google znamená, že budeme mať vytvoriť nový uzol, že sme Pridáme do prepojeného zoznamu, a potom postupujte podľa pokynov starostlivo že sme sa už skôr načrtol v jednotlivo spojových zoznamov pridať do reťaz bez prerušenia reťazca a stráca alebo orphaning akýkoľvek prvky Google zoznamu. A to je v podstate, čo to malá kvapka texte tam zhŕňa. A poďme sa pozrieť sa na to ako diagram. 

Tak tu je náš previazaný zoznam. To súčasne obsahuje štyri prvky. A dokonalejšie Tu je náš stack obsahujúce štyri prvky. A povedzme, že chceme teraz tlačiť nové položky na tomto zásobníku. A my chceme, aby sa zasadila nový položka, ktorej údaje hodnota je 12. Tak čo budeme robiť? Tak po prvé, že budeme malloc priestor, dynamicky prideliť priestor pre nový uzol. A samozrejme okamžite po urobíme volanie sme vždy malloc uistite sa, že pre kontrolu null, pretože ak by sme dostali null staré tam bol nejaký problém. Nechceme, aby dereferencia tomuto null Ukazovateľ alebo budete trpieť poruchu seg. To nie je dobré. Takže sme malloced uzla. Budeme predpokladať, že sme mali úspech tu. Chystáme sa dať do 12 pole dáta tohto uzla. Teraz spomínaš si, ktoré z našich ukazovateľov presunie budúci takže neporušujú reťaz? Máme niekoľko možností, ale tu jediná, ktorá to bude v bezpečí je stanoviť ďalšie ukazovatele na novinky prejdite na starú hlavu zoznamu alebo to, čo bude čoskoro stará hlava zoznamu. A teraz, že všetky naše prvky sú pripútal spolu, môžeme len presunúť zoznam na bod na rovnaké miesto, že nová robí. A my sme teraz skutočne presadzovalo Novým prvkom na prednej strane zásobníka. 

Ak chcete pop chceme len zmazať, že prvý prvok. A tak podstate to, čo musíme urobiť tu, dobre musíme nájsť druhý prvok. Nakoniec, že ​​sa stane novým hlavu po tom, čo sme odstrániť prvý jeden. Takže len musíme začať od začiatok, pohybovať jedným dopredu. Potom, čo máme držať na jednom vpred, kde sme v súčasnosti sme môžete odstrániť prvý bezpečne a potom môžeme len presunúť hlavou poukázať na to, čo bolo druhý termín a potom teraz je prvá po tom Uzol bol zmazaný. 

Takže znova, pričom sa pozrieť na to ako diagram my Chcete teraz pop prvok z tohto zásobníka. Tak čo budeme robiť? Tak sme to ako prvý chce vytvoriť nový ukazovateľ, ktorý sa deje poukázať na rovnakom mieste ako hlava. Budeme to jedno miesto presunúť vpred tým, že hovorí tráv rovná tráv ďalší napríklad, ktorý by postupovať ten, tráv ukazovateľ polohy dopredu. Teraz, keď máme držať na prvý prvok cez ukazovatele s názvom zoznamu a Druhý prvok prostredníctvom ukazovateľa nazvaný tráv, môžeme bezpečne zmazať, že prvý prvok zo zásobníka bez straty zvyšku reťaze, pretože sme mať spôsob, ako odkazovať k druhému prvku odovzdá prostredníctvom z ukazovateľ nazvaný tráv. 

Takže teraz sa môžeme oslobodiť tento uzol. Môžeme oslobodiť zoznam. A potom všetko, čo potrebujete urobiť, je teraz presunúť zoznam bodu na rovnaké miesto že tráv robí, a my sme tak nejako staré kde sme začali, než sme sa tlačil 12 na prvom mieste, doprava. To je presne tam, kde sme boli. Mali sme štvorprvková zásobníka. Pridali sme pätinu. Presadili sme pätinu prvok na, a potom sme vyskočila, že v poslednej dobe pridaný element späť. 

To je naozaj celkom veľa všetko, čo je na komíny. Môžete je implementovať ako pole. Môžete ich implementovať ako prepojené zoznamy. Tam sú, samozrejme, ostatné spôsoby, ako je tiež realizovať. V podstate dôvod, prečo by sme použiť zásobníky je udržať dát takým spôsobom, že naposledy pridané prvkom je prvá vec, ktorú sme bude chcieť vrátiť. Som Doug Lloyd, to je CS50.