DOUG LLOYD: Rendben, így ezen a ponton vagytok Valószínűleg elég ismerős tömbök és láncolt listák amely a két primer adatstruktúrák voltunk beszélt tartása készlet adatok hasonló adattípusok szervezett. Most fogunk beszélni körülbelül egy-két variáció A tömbök és kapcsolt listák. Ebben a videóban megyünk beszélni stack. Különösen fogunk beszélni körülbelül egy adatstruktúra úgynevezett verem. Emlékezzünk vissza az előző megbeszélések mintegy mutatók és a memória, hogy a köteg is név egy szegmense memória ahol statikusan deklarált memory-- memória, hogy Íme, változók akkor nevezd et cetera és funkciója kép, amely azt is hívási verem keretek léteznek. Tehát ez egy verem adatszerkezet Nem verem szegmens a memóriában. OKÉ. 

De mi van egy halom? Tehát ez nagyjából csak egy különleges fajta struktúra amely fenntartja az adatok szervezett módon. És van két nagyon közös módon hajtsák végre stack két adatstruktúrák hogy már ismeri, tömbök és kapcsolt listák. Mitől lesz egy halom külön van a milyen módon tesszük információk a verem, és ahogyan mi adatok eltávolításához a verem. Különösen halom a szabály csak a legfontosabb nemrég hozzáadott elem lehet távolítani. 

Így gondolok rá, mintha ez egy verem. Mi cölöp információk a tetején is, és csak a dolog, a tetején a halom el lehet távolítani. Nem tudjuk eltávolítani a dolog alatta mert minden más lenne összeomlás, és felborulhat. Tehát tényleg az épület egy halom, hogy Ezután el kell távolítani, apránként. Emiatt mi gyakran hivatkoznak egy köteg, mint egy LIFO szerkezet, tart, first out. LIFO, utolsó, first out. 

Szóval emiatt korlátozás hogyan információt adhatunk és el kell távolítani egy köteg, ott tényleg Csak két dolgot tehetünk egy köteg. Mi is nyomja, amely a távon használjuk a hozzá egy új eleme, hogy a tetején a verem, vagy ha a köteg nem létezik és mi hozzuk létre a semmiből, ami a verem az első helyen lenne nyomva. Aztán felbukkan, hogy az a fajta CS távon használjuk, hogy távolítsa el a legutóbb hozzáadott eleme a tetején a verem. 

Mi is így fogjuk nézni mindkét megvalósítások, mind tömb alapú és láncolt lista alapján. És megyünk kezdeni tömb alapú. Tehát itt az alapötlet, hogy mi A tömb alapú verem adatszerkezet nézne. Van egy gépelt meghatározás itt. Belsejét, hogy van két tagja vagy mezők a szerkezet. Van egy tömbben. És megint én vagyok a tetszőleges adat típusú érték. 

Tehát ez lehet bármilyen típusú adatot, int char vagy valamely más adat írja előzőleg létrehozott. Tehát van egy sor méretű kapacitás. Kapacitások, egy font meghatározott állandó, talán valahol máshol van a fájl. Tehát észre már ezzel a végrehajtása vagyunk határosak magunkat, mint volt, jellemzően a helyzet a tömbök, amit nem tudunk dinamikusan átméretezni, ahol egy bizonyos számú Az elemek maximum, tudunk rakni a mi verem. Ebben az esetben ez kapacitás elemeit. 

Azt is nyomon követheti A tetején a verem. Mi elem a leginkább Nemrég adtunk a verem? És így nyomon követheti, hogy egy változó nevű tetején. És mindez tördelése fel együtt egy új adattípus úgynevezett verem. És ha egyszer mi létrehozott Az új adatok típusa tudjuk kezelni, mint bármilyen más típusú adatokat. Kijelenthetjük verem s, mint tudnánk tenni int x, y, vagy char. És amikor azt mondjuk verem s, illetve mi történik A mi kap egy sor memória félre minket. 

Ebben az esetben a kapacitás Már nyilvánvalóan úgy döntött, 10 mert kaptam egy Egyetlen változó típusú köteg amely két területen felidézni. Egy tömb, ebben az esetben megy hogy egy sor egészek amint ez a helyzet a legtöbb az én példa. És még egy egész változó tárolására alkalmas a felső, A legutóbb hozzáadott eleme, hogy a kémény. Tehát egyetlen verem, amit Csak meghatározott néz ki. Ez egy dobozt, amiben egy sor 10 mi lesz egész ebben az esetben, és Egy másik egész változó van, zöld jelzésére a verem tetejére. 

Beállításához a tetején a verem mi csak mondani s.top. Mi így elérheti a mező egy szerkezet visszahívás. s.top egyenlő 0 hatékonyan Teszi ezt a mi verem. Tehát megint van két művelet hogy el tudjuk végezni most. Mi lehet nyomni, és mi is felbukkan. Kezdjük push. Ismét nyomja hozzá egy új eleme, hogy a tetején a verem. 

Szóval mit kell tennünk a ez a tömb alapú megvalósítása? Nos általában a Push funkció folyik hogy el kell fogadnunk a mutatót a verem. Most hogy egy második, és gondolj rá. Miért akarnánk elfogadni egy mutatót a verem? Emlékezzünk vissza az előző videók változó alkalmazási körét és mutatók, mi lenne, ha mi csak küldeni verem, s inkább az a paraméter? Milyen valójában telt el oda? Ne feledje, mi hozzuk létre egy másolatot amikor átadjuk azt a funkciót hacsak nem használunk mutató. És így ez a funkció nyomja igényeinek elfogadni egy mutatót a verem így vagyunk valójában változó A verem kívánunk változtatni. 

A másik dolog, nyomja talán jobban örülne elfogadja az adat elemének típusú értéket. Ebben az esetben, ismét, egy egész szám, amely fogunk hozzá, hogy a felső verem. Tehát van a két paraméter. Mit fogunk Most csinálni benne push? Nos, egyszerűen, mi csak lesz hozzá ez az elem, hogy a tetején a verem majd változtatni, ahol a felső a verem, hogy s dot felső értéket. Szóval ez az, amit egy függvény nyilatkozatot push nézhet ki egy tömb alapú végrehajtását. 

Ismét ez nem egy kemény és gyors szabály hogy meg tudná változtatni ezt, és van ez változhat a különböző módokon. Talán s nyilvánítják világszerte. És így nem is kell át ez a paraméter. Ez megint csak egy Általános esetben a push. És ott vannak a különböző módja annak végrehajtására. De ebben az esetben mi nyomja fog tartani két érv, egy mutató a verem és adatelem típusú értéket, egész ebben az esetben. 

Szóval nyilvánította s mi mondta s.top egyenlő 0. Most nyomja meg a szám 28 a verembe. Nos, mit is jelent ez? Nos jelenleg a verem tetején 0. És akkor mi alapvetően fog történni, fogunk ragaszkodni száma 28 a tömb 0 helyen. Elég egyszerű, ugye, hogy volt, a felső és most még jól jöhet. És akkor meg kell változtatni, mit A tetején a verem lesz. Ahhoz, hogy a következő alkalommal mi nyomja egyik eleme, fogunk tárolja tömb helyét, valószínűleg nem 0. Mi nem akarja felülírni amit csak fel ott. És ezért most is csak mozgatni a felső 1. Hogy lenne értelme. 

Most, ha azt akarjuk, hogy egy másik elem a verembe, mondjuk azt akarjuk, hogy álljon 33, Hát most mi csak fog tartani 33 és tedd tömb helyét száma 1, és változtassa meg a tetején a verem, hogy tömb helyét a két számot. Tehát, ha a következő alkalommal szeretnénk nyomja egy elem a verembe, ez lesz bevezetni tömb helyen 2. És csináljuk meg még egyszer. Majd nyomja le 19 a stack. Fogjuk fel 19 tömb helyen 2 és a változás a tetején a verem hogy tömb helyét 3 így ha a következő alkalommal már kell, hogy egy push mi még jól jöhet. 

OK, szóval ez rámenős dióhéjban. Mi a helyzet a felbukkanó? Tehát pukkanó a fajta megfelelője rámenős. Ez hogyan távolítsa el az adatokat a verem. És általában pop igényeinek a következő lépésekre. Meg kell, hogy fogadja el a mutató a verem, ismét az általános esetben. Néhány más esetben lehet, nyilatkoztak a verem globálisan, Ebben az esetben nem kell átadni A mert már hozzáféréssel rendelkezik, hogy mint globális változót. De akkor mi mást tennie kell tennünk? Hát mi is megnő A tetején a verem push, így valószínűleg fog akarnak hogy csökkentse az a verem tetejére a pop, ugye? És akkor persze mi is akarnak vissza az értéket, amit eltávolítani. Ha mi hozzátéve elemeket, szeretnénk hogy elemeket ki később, akkor valószínűleg tényleg szeretné tárolni őket, így mi Nem csak törölni őket a verem, majd mit kezdeni velük. Általában, ha mi vagyunk tolás és felbukkanó itt szeretnénk tárolni ezt információt értelmes módon és így nem teszik értelme, hogy csak megválni tőle. Szóval ezt a funkciót kell Valószínűleg vissza értéket számunkra. 

Szóval ez az, amit abban a nyilatkozatban, pop nézhet ki ott a bal felső sarokban. Ez a függvény típusú adatok értékét. Ismét voltunk segítségével egészek egész. És hogy elfogadja a mutató egy köteg, mint egyedüli érvet vagy kizárólagos paramétert. Tehát mi pop fog csinálni? Tegyük fel, hogy szeretnénk most pop egyik eleme le s. Úgy emlékszem, azt mondta, hogy halmok utolsó in, first out, LIFO adatszerkezeteket. Melyik elem fog kell távolítani a verem? Találta ki 19? Mert igazad van. 19 volt az utolsó elem is hozzáadódik a verem, amikor mi voltunk nyomva elemek, És ez így megy az első eleme, hogy eltűnik. Olyan ez, mintha azt mondta 28 és majd rakjuk 33 a tetején, és rakjuk 19 a tetején, hogy. Az egyetlen elem tudunk felszállni a 19. 

Most az ábra itt, mit tettem A fajta törölt 19 a tömbből. Ez valójában nem mit fogunk csinálni. Mi csak lesz ilyen A tettetni, hogy nincs ott. Még mindig ott van a hogy az emlékezet helye, de mi csak úgy figyelmen kívül hagyni megváltoztatásával tetején a verem attól, hogy 3-2. Tehát ha voltunk most álljon Egy másik elem a verembe, ez több mint 19 levelet. 

De ne menjünk végig a baj A törlés 19 a veremből. Mi is csak úgy, mintha ez nem létezik. Céljából a verem, hogy elment, ha megváltoztatjuk a felső, hogy 2 helyett 3. Rendben, ez volt nagyjából azt. Ez minden, amit tennie kell a pop egy elem ki. Csináljuk újra. Tehát amit kiemelt pirossal ide jelzik csinálunk egy másik hívást. Fogunk ugyanezt csinálja. 

Tehát mi fog történni? Nos, megyünk tárolni 33 x és megyünk megváltoztatni a tetején a verem 1. Tehát, hogy ha mi most, hogy álljon egy elemet a verem, amely mi vagyunk fog tenni most, mi fog történni A megyünk felülírás tömb helyét száma 1. Tehát, hogy 33-ben a fajta maradt mögött, hogy mi csak úgy tett, mintha már nincs ott, mi csak megy a cucc, és tedd 40 van helyette. És akkor persze, mivel tettünk egy push, megyünk emelheti a a verem tetején 1-2 így ha most hozzá Egy másik elem, hogy lesz bemegy tömb helyét a két számot. 

Most kapcsolt listák másik módja a stack. És ha ez a megfogalmazás a képernyőből ismerős neked, azért, mert úgy néz ki, szinte pontosan ugyanaz, sőt, ez nagyjából pontosan ugyanaz, mint a külön-külön láncolt lista, ha visszahívja a vitánk a egyszeresen láncolt listák egy másik videó. Az egyetlen korlátozás van számunkra, mint a programozók, mi nem hagyjuk beszúrni vagy törölni véletlenszerűen A külön-külön láncolt lista amit lehetett korábban megtenni. Mi csak most beszúrni és törölni az első vagy a tetején a linkelt listán. Ez tényleg az egyetlen különbség mégis. Ez egyébként egy egyszeresen láncolt lista. Ez csak a korlátozás helyett magunkra programozók, hogy megváltoztatja azt egy verem. 

A szabály az, hogy állandóan mutatót a fejét egy láncolt lista. Ez természetesen egy általánosan Fontos szabály először. Mert egyedül láncolt lista amúgy is csak kell egy mutatót a fejét annak érdekében, hogy, hogy a lánc lesz képes utalni az összes többi elemhez A láncolt lista. Azonban különösen az Fontos egy köteg. És így általában te fog valójában akar Ez a mutató, hogy egy globális változót. Ez valószínűleg meg is még könnyebb lesz így. Tehát mi az analógok push és pop? Jobb. Tehát nyomja meg újra hozzátéve Új elem, hogy a kémény. A láncolt lista, amely azt jelenti, megyünk, hogy hogy hozzon létre egy új csomópontot, hogy mi vagyunk fog hozzá a láncolt lista, és kövesse az óvatos léptekkel hogy már korábban vázolt egyszeresen láncolt listák hogy add meg A lánc feltörése nélkül a lánc és a vesztes vagy orphaning bármely elemei a láncolt lista. És ez alapvetően ez az kis folt a szövegben foglalja össze. És vessünk egy pillantást úgy, mint egy rajz. 

Tehát itt van a láncolt lista. Ez egyszerre négy elemet. És még tökéletesebben itt a mi verem tartalmazó négy elem. És mondjuk most szeretnénk álljon egy új elemet erre verem. És azt akarjuk, hogy álljon egy új elem, amelynek adatait az érték 12. Hát most mit fogunk csinálni? Hát először megyünk malloc tér, dinamikusan osztja helyet egy új csomópontot. És természetesen követően azonnal mi szeretnénk hívni malloc mindig győződjön meg arról, hogy ellenőrizze a null, mert ha megvan null vissza volt valami probléma. Nem akarjuk, hogy követéssel, hogy null mutatót vagy akkor szenvedni egy seg hiba. Ez nem jó. Így már malloced a csomópont. Feltételezzük, már volt sikere van. Megyünk fel 12 be az adatmező az említett csomópont. Most emlékszel, melyik a mi mutatók mozog jövő így nem megtörni a láncot? Van egy pár lehetőség, de itt Az egyetlen, ami lesz biztonságban az, hogy hozzanak hírt következő mutatót pont a régi lista élére vagy mi hamarosan az régi lista élére. És most, hogy minden kedves elemek egymáshoz láncolva, akkor csak mozgatni a listát, hogy pont hogy ugyanazon a helyen, hogy az új csinál. És most már gyakorlatilag tolt egy Új elemet az első a stack. 

Pop mi csak szeretnénk törölni, hogy az első elem. És így alapvetően mi meg kell tennünk itt, valamint meg kell találnunk a második elem. Végül, hogy lesz az új fej után töröljük az elsőt. Szóval csak meg kell kezdeni a Kezdetben, mozog egy előre. Amint megvan a hold egy előre, ahol jelenleg vagyunk törölheti az elsőt biztonságosan és akkor csak mozgatni a fejét hogy pont mi volt a második ciklusra, majd most az első után, hogy csomópont törlésre került. 

Tehát ismét egy pillantást úgy, mint egy diagramon szeretnénk teremteni a pop egy elem le ezt a verem. Szóval mit tegyünk? Nos mi először fog létrehozni új mutatót, hogy folyik hogy pont ugyanazon a helyen, mint a feje. Fogunk mozgatni egy hellyel előre azzal trav egyenlők trav következő például, amely lenne előre a trav mutató egy Csatárként. Most, hogy már van egy tartsa az első elem a mutató az úgynevezett listán, és a második eleme egy mutatót nevezzük trav, nyugodtan törölheti, hogy első elem a kéményből anélkül, hogy elveszítené a többi a lánc, mert Van egy módja annak, hogy utalja hogy a második elem továbbítsa útján a pointer nevű trav. 

Tehát most is szabad, hogy csomópontot. Mi lehet a szabad listán. És akkor minden meg kell tennie, most mozgatni a listát, hogy pont ugyanazon a helyen hogy trav csinál, és mi vagyunk a fajta vissza ahol elkezdtük előtt toltuk 12 a az első helyen, jobbra. Pontosan ez az, ahol mi voltunk. Mi volt ez a négy elem verem. Adtunk egy ötödik. Toltuk egy ötödik elemet, és aztán durrantott, hogy nemrégiben hozzáadott elem vissza le. 

Ez tényleg elég sok minden van halmozódik. Akkor ezek végrehajtásához tömbök. Akkor ezek végrehajtásához kapcsolódó listákat. Vannak, persze, más ezek végrehajtásának módozatait is. Alapvetően azért szeretnénk használni halom, hogy fenntartsa az adatok oly módon hogy a legutóbb hozzáadott elem az első dolog vagyunk majd szeretnék visszatérni. Én Doug Lloyd, ez CS50.