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.