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.