DOUG LLOYD: Dobře, takže tímto bodem, kterou jste
asi dost povědomý s polí a spojových seznamů
což je dva primární datové struktury jsme
mluvil o pro vedení sad Údaje z podobných typů datových organizovaný.
>> Teď budeme mluvit o několik variant
Na pole a spojových seznamů.
V tomto videu budeme mluvit o komíny.
Konkrétně budeme mluvit o datovou strukturu volal hromadu.
Připomeňme z předchozích diskusí o ukazatele a paměť,
že zásobník je také jmenovat segment paměti
kde staticky deklaroval memory-- paměť, která vám
jméno, proměnné, které si jen vzpomenete, et cetera a funkce rámy, které jsme také
zásobník volání rámce existují.
Takže tohle je struktura zásobník dat není stoh segment paměti.
DOBŘE.
>> Ale co je to zásobník?
Takže je to do značné míry jen Zvláštní druh konstrukce
který udržuje data v organizovaným způsobem.
A tam jsou dvě velmi obyčejné způsoby, jak realizovat
komíny pomocí dvou datových struktur že jsme již obeznámeni s,
pole a spojové seznamy.
Co dělá balík zvláštní, je způsob, ve kterém se vložit informace
do komína, a způsob, jakým odebrat informace ze zásobníku.
Zejména s komíny pravidlo je jen ty
přidání element mohou být odstraněny.
>> Takže myslíte, že o tom, jako kdyby je to hromada.
Jsme hromadí informace v horní části sama o sobě,
a to pouze věc na vrcholu hromady mohou být odstraněny.
Nemůžeme odstranit věc pod protože všechno ostatní by
zhroutí a spadnout.
Takže jsme vlastně budujeme svazek, který my pak muset odstranit kousek po kousku.
Z tohoto důvodu jsme se obyčejně se odkazují do komína jako struktura LIFO,
poslední dovnitř, první ven.
LIFO, poslední dovnitř, první ven.
>> Takže kvůli tomuto omezení jak mohou být informace přidány do
a odstranil z balíčku, je to opravdu jen dvě věci, co můžeme udělat s komínem.
Můžeme tlačit, což je termín používáme pro přidávání
nový prvek v horní části stack, nebo pokud neexistuje stack
a my jsme ji vytvářet od nuly, vytváření zásobníku na prvním místě
bude tlačit.
A pak se pop, to je druh CS termín používáme k odstranění naposledy
přidán prvek z horní části zásobníku.
>> Takže budeme dívat na obou implementace, a to jak na bázi pole
a spojový seznam založen.
A jdeme začít s řadou bázi.
Tak tady je základní myšlenka o tom, co struktura zásobníku datové pole na bázi
vypadat.
Máme definici zadaný zde.
Uvnitř, že máme dva členy nebo pole struktury.
Máme pole.
A opět jsem pomocí libovolná datový typ hodnoty.
>> Takže to může být jakýkoliv datový typ, int char nebo jiné údaje
typ jste dříve vytvořili.
Takže máme řadu velikosti kapacity.
Kapacita je půl kila definovaný konstantní, Možná někde jinde v naší souboru.
Takže si všimnout již s tímto konkrétním implementace jsme ohraničující
sami sebe jako byl typicky případ s poli,
které nemůžeme dynamicky měnit velikost, tam, kde je určitý počet
z prvků, které maxima můžeme dát v naší zásobníku.
V tomto případě je to kapacitní prvky.
>> Také sledovat v horní části zásobníku.
Co element je nejvíce nedávno přidal do stohu?
A tak jsme se sledovat, že v proměnné s názvem vrcholu.
A to vše dostane zabalené spolu do nového datového typu s názvem hromadu.
A jakmile jsme vytvořili tento nový datový typ
můžeme léčit jako jakýkoli jiný typ dat.
Můžeme prohlásit zásobníku s, stejně jako jsme mohli udělat int x, nebo char y.
A když říkáme stack s, i co se stane
se dostaneme sadu Paměť zrušil pro nás.
>> V tomto případě kapacity Jsem se zřejmě rozhodl,
10 proto, že jsem dostal single proměnná typu zásobníku
který obsahuje dvě pole oběhu.
Pole, v tomto případě bude být pole celých čísel
jako je tomu v případě většiny svých příkladů.
A další integer proměnná schopný uložení na vrchol,
nejnověji přidané element do stohu.
Takže jeden jediný zásobník, co jsme Jen definovány vypadá takto.
Je to krabička obsahující Pole 10, co
bude celá čísla v tomto případě, a další integer proměnná tam zeleně
pro indikaci v horní části zásobníku.
>> Chcete-li nastavit horní z stack jsme jen říct s.top.
To je, jak jsme přístup k pole strukturu odvolání.
s.top rovná 0 účinně dělá to na náš stack.
Takže znovu máme dvě operace že můžeme hrát teď.
Můžeme tlačit a můžeme pop.
Začněme s Push.
Opět platí, že tlačí je přidání nové prvek na vrchol zásobníku.
>> Takže to, co potřebujeme udělat v Toto pole implementace na bázi?
No obecně Funkce Push se děje
muset akceptovat Ukazatel na zásobníku.
Nyní se druhý a přemýšlet o tom.
Proč bychom chtěli přijmout ukazatel na zásobníku?
Připomeňme z předešlých videí na variabilní rozsah a ukazatele,
co by se stalo, kdybychom právě poslal zásobník, to spíše jako parametr?
Co by vlastně být předány tam?
Pamatujte si, že jsme vytvoření kopie když jsme to předat funkci
pokud nebudeme používat ukazatele.
A tak tato funkce tlačit potřeby přijmout ukazatel na stohu
takže jsme skutečně mění, stoh hodláme změnit.
>> Další věc, tlak pravděpodobně chce přijmout je datový prvek z hodnoty typ.
V tomto případě je opět, celé číslo, které budeme přidávat na vrchol zásobníku.
Takže máme naše dva parametry.
Co budeme teď dělat uvnitř tlačit?
No, prostě jsme jen tak přidat že element na vrchol stohu
a potom změňte kde je horní zásobník je, že s dot nejvyšší hodnotu.
Takže tohle je to, co funkce Prohlášení Push
by mohla vypadat An array-založené implementace.
>> Opět to není tvrdé a rychlé pravidlo že byste mohli změnit a mají
že se liší v různých směrech.
Možná, že s je deklarován globálně.
A tak ani nepotřebujete předat je jako parametr.
To je opět jen obecný případ Push.
A tam jsou různé způsoby, jak k jeho provedení.
Ale v tomto případě je naše Push bude trvat
dva argumenty, ukazatel zásobníku a datový prvek typu hodnoty, celočíselné
v tomto případě.
>> Takže jsme deklarovali ů, my řekl s.top rovná 0.
Nyní pojďme tlačit číslo 28 do zásobníku.
Tak co to znamená?
No v současné době stoh papíru je 0.
A tak to, co je v podstatě bude dít, je
budeme držet číslo 28 do umístění pole 0.
Docela jednoduché, vpravo, že byl vrchol a teď jsme dobří jít.
A pak musíme změnit to, co horní část zásobníku bude.
Tak, že příště tlačíme prvek v,
budeme ukládat do umístění pole, pravděpodobně ne 0.
Nechceme, aby přepsat co jsme právě tam dal.
A tak jsme si jen přesunout odshora 1.
To asi dává smysl.
>> Nyní, pokud chceme dát další prvek do zásobníku, že chceme, aby se zasadila 33,
No teď jsme jen bude trvat 33 a dal ho na pole číslo umístění
1, a poté změňte na vrchol našeho stack být pole číslo umístění dvou.
Takže pokud příště chceme tlačit prvek do zásobníku,
to bude dát v místě pole 2.
A pojďme to udělat ještě jednou.
Budeme tlačit 19 pryč z komínů.
Dáme 19 v místě pole 2 a změnit na vrchol našeho stohu
být umístění pole 3 takže pokud příště
je třeba, aby se tlačit jsme dobří jít.
>> OK, takže se tlačí v kostce.
A co objevovat?
Takže popping je druh protějšek tlačit.
Je to, jak jsme se odstranit data ze zásobníku.
A v sociální potřeby popových udělat následující.
Je třeba přijmout ukazatel na zásobník, opět v obecném případě.
V některých opačném případě byste mohli prohlásily stoh globálně,
v takovém případě nemusíte jej projít V protože již má přístup k němu
jako globální proměnné.
Ale co jiného dělat, musíme udělat?
Tak jsme se postupně horní část zásobníku v tlačit,
tak jsme pravděpodobně bude chtít pro snížení horní část stohu
v pop, že jo?
A pak samozřejmě jsme také bude chtít
vrátit hodnotu, které jsme odstranit.
Pokud jsme přidat prvky, chceme dostat prvky se později,
tak si pravděpodobně skutečně Chcete je uložit, takže jsme
ne jen odstranit z stack, a pak dělat nic s nimi.
Obecně platí když jsme tlačení a praskání zde
chceme uložit tento Informace smysluplně
a tak to neznamená, že smysl jen odhodit to.
Takže tato funkce by měla pravděpodobně vrátit hodnotu k nám.
>> Takže to je to, co prohlášení pro pop může vypadat, jako by tam v levém horním rohu.
Tato funkce vrací Data typu hodnoty.
Opět jsme byli s použitím celá čísla v celém textu.
A to přijímá ukazatel na stack jako jeho jediným argumentem, nebo jediný parametr.
Takže to, co se pop dělat?
Řekněme, že chceme, aby teď pop prvek pryč s.
Takže pamatujte Řekl jsem, že zásobníky jsou poslední in, first out, LIFO datových struktur.
Který prvek se chystá být odstraněna ze zásobníku?
Věděli jste asi 19?
Vzhledem k tomu, že budeš v pořádku.
19 byla poslední element jsme přidali do stack, když jsme tlačili na prvky,
a tak to bude první element, který se odstraní.
Je to, jako kdybychom řekli 28, a Pak jsme dali 33 na vrcholu toho,
a klademe 19 na vrcholu to.
Jediný prvek můžeme sundat, je 19.
>> Nyní v diagramu tady, co jsem udělal je druh vymazán 19 z pole.
To není ve skutečnosti to, co budeme dělat.
Jsme jen tak druhu z předstírat, že tam není.
Je to pořád tam v že paměťové místo,
ale my jsme jen tak ignorovat změnou vrchol našeho stohu
toho, že 3 až 2.
Takže kdybychom teď tlačit Dalším prvkem do zásobníku,
že by v průběhu psát 19.
>> Ale pojďme se projít potíží mazání 19 ze zásobníku.
Můžeme jen předstírat, že tam není.
Pro účely stohu je to pryč, pokud změníme horní být 2 namísto 3.
Dobře, takže to bylo docela hodně to.
To je vše, co potřebujete udělat, pop prvek off.
Udělejme to znovu.
Takže jsem ho zvýrazněny červeně zde naznačují, děláme další hovor.
Chystáme se udělat to samé.
>> Takže co se stane?
No, budeme uchovávat 33 v x a jedeme
pro změnu v horní části zásobníku 1.
Takže kdybychom teď tlačit prvek do zásobníku, který kterém jsme
dělat právě teď, co se bude dít
se jdeme přepisování array číslo umístění 1.
Takže to 33, který byl druh vlevo za které jsme před chvílí předstíral
už tam není, jsme jen tak to nandat a dal 40 tam místo.
A pak samozřejmě, od té doby jsme udělali tlak,
jdeme pro zvýšení hodnoty Vrchol zásobníku 1-2
takže pokud bychom nyní přidat Dalším prvkem bude to
přejít do pole umístění číslo dvě.
>> Nyní spojové seznamy jsou další způsob, jak realizovat komíny.
A je-li tato definice na straně Obrazovka tady vypadá povědomě vám,
je to proto, že vypadá skoro přesně stejný, ve skutečnosti,
je to docela hodně je přesně stejné jako jednotlivě spojový seznam,
Pokud si vzpomínáte z naší diskuse o jednotlivě spojené seznamy v jiném videu.
Jediné omezení zde je pro nás jako programátoři,
nejsme dovoleno vložení nebo odstranění náhodně
ze jednotlivě Google seznamu které jsme mohli dříve udělat.
Můžeme se teprve nyní vložit a odstranit z přední nebo horní části spojeny
Seznam.
To je opravdu jen rozdíl ačkoli.
To je jinak singly provázaný seznam.
Je to jen omezení nahrazovat sami na sebe
jako programátoři, že změní jej do zásobníku.
>> Pravidlo je zde vždy udržovat ukazatel na hlavu propojeného seznamu.
Toto je samozřejmě obecně Důležité pravidlo jako první.
Pro jednotlivě spojeny seznam stejně se vám potřebují pouze ukazatel na hlavě
aby se, že řetězec se odvolat
ke každému druhému prvku v připojeném seznamu.
Ale je to zvláště důležité s hromadu.
A tak obecně, že jste bude skutečně chtít
Tento ukazatel být globální proměnná.
Je to pravděpodobně bude být ještě jednodušší, že cesta.
Takže jaké jsou analogy tlačit a pop?
Správně.
Takže znovu tlačí je přidání nový prvek do zásobníku.
V seznamu, který Google znamená, že budeme mít
vytvořit nový uzel, že jsme Přidáme do propojeného seznamu,
a pak postupujte podle pokynů pečlivě že jsme se již dříve nastínil
v jednotlivě spojových seznamů přidat do řetěz bez přerušení řetězce
a ztrácí nebo orphaning jakýkoli prvky Google seznamu.
A to je v podstatě, co to malá kapka textu tam shrnuje.
A pojďme se podívat se na to jako diagram.
>> Tak tady je náš provázaný seznam.
To současně obsahuje čtyři prvky.
A dokonaleji Tady je náš stack obsahující čtyři prvky.
A řekněme, že chceme nyní tlačit nové položky na tomto zásobníku.
A my chceme, aby se zasadila nový položka, jejíž údaje hodnota je 12.
Tak co budeme dělat?
Tak zaprvé, že budeme malloc prostor, dynamicky
přidělit prostor pro nový uzel.
A samozřejmě okamžitě po uděláme volání jsme vždy malloc
ujistěte se, že pro kontrolu null, protože pokud bychom dostali null zpátky
tam byl nějaký problém.
Nechceme, aby dereference tomuto null Ukazatel nebo budete trpět poruchu seg.
To není dobré.
Takže jsme malloced uzlu.
Budeme předpokládat, že jsme měli úspěch zde.
Chystáme se dát do 12 pole data tohoto uzlu.
Teď vzpomínáš si, které z našich ukazatelů přesune příští takže neporušují řetěz?
Máme několik možností, ale zde jediná, která to bude v bezpečí
je stanovit další ukazatele na novinky přejděte na starou hlavu seznamu
nebo to, co bude brzy stará hlava seznamu.
A teď, že všechny naše prvky jsou připoutal spolu,
můžeme jen přesunout seznam na bod na stejné místo, že nová dělá.
A my jsme teď skutečně prosazovalo Novým prvkem na přední straně zásobníku.
>> Chcete-li pop chceme jen smazat, že první prvek.
A tak podstatě to, co musíme udělat tady,
dobře musíme najít druhý prvek.
Nakonec, že ​​se stane novým hlavu poté, co jsme odstranit první jeden.
Takže jen musíme začít od začátek, pohybovat jedním dopředu.
Poté, co máme držet na jednom vpřed, kde jsme v současné době
jsme můžete odstranit první bezpečně a pak můžeme jen přesunout hlavou
poukázat na to, co bylo druhý termín a pak nyní
je první po tom Uzel byl smazán.
>> Takže znovu, přičemž se podívat na to jako diagram my
Chcete nyní pop prvek z tohoto zásobníku.
Tak co budeme dělat?
Tak jsme to jako první hodlá vytvořit nový ukazatel, který se děje
poukázat na stejném místě jako hlava.
Budeme to jedno místo přesunout vpřed tím, že říká trav rovná
trav další například, který by postupovat ten, trav ukazatel
polohy dopředu.
Teď, když máme držet na první prvek
přes ukazatele s názvem seznamu a Druhý prvek prostřednictvím ukazatele nazvaný
trav, můžeme bezpečně smazat, že první prvek ze zásobníku
bez ztráty zbytku řetězu, protože jsme
mít způsob, jak odkazovat k druhému prvku
předá prostřednictvím z ukazatel nazvaný trav.
>> Takže teď se můžeme osvobodit tento uzel.
Můžeme osvobodit seznam.
A pak vše, co potřebujete udělat, je nyní přesunout seznam bodu na stejné místo
že trav dělá, a my jsme tak nějak zpátky kde jsme začali, než jsme se tlačil 12
na prvním místě, doprava.
To je přesně tam, kde jsme byli.
Měli jsme čtyřprvková zásobníku.
Přidali jsme pětinu.
Prosadili jsme pětinu prvek na, a pak jsme
vyskočila, že v poslední době přidán element zpátky.
>> To je opravdu docela hodně všechno, co je na komíny.
Můžete je implementovat jako pole.
Můžete je implementovat jako propojené seznamy.
Tam jsou, samozřejmě, ostatní způsoby, jak je také realizovat.
V podstatě důvod, proč bychom použít zásobníky je udržet dat takovým způsobem,
že naposledy přidané prvkem je první věc, kterou jsme
bude chtít vrátit.
Jsem Doug Lloyd, to je cs50.