Doug LLOYD: Gerai, taip šiuo klausimu esate tikriausiai gana susipažinę su matricomis ir susijusių sąrašus kuris yra du pirminės duomenų struktūros mes kalbėjo apie laikymo rinkiniai duomenys panašių duomenų tipų organizuotas. Dabar mes ketiname kalbėti apie keletą variacijų ant matricos ir susijusių sąrašus. Šiame vaizdo mes ketiname kalbėti apie šūsnis. Tiksliau, mes ketiname kalbėti apie duomenų struktūra vadinama kamino. Prisiminkite iš ankstesnių diskusijų apie nurodymus ir atminties, kad kamino yra taip pat vardą kaip atminties segmentą kur statiškai paskelbė memory-- atminties, kuri jus pavadinimą, kintamieji, kad jūs Vardas et Cetera ir funkcijų rėmai kurią mes taip pat Skambučių kamino rėmai egzistuoja. Taigi tai yra kamino duomenų struktūra nėra kamino segmentas atmintį. GERAI. 

Bet kas yra kamino? Taigi, tai gana daug tik specialios rūšies struktūros kad palaiko duomenis organizuotu būdu. Ir ten du labai paplitusių būdų įgyvendinti kaminai, naudojant du duomenų struktūras kad mes jau esate susipažinę su, matricas ir susiję sąrašus. Ką daro kamino ypatingą yra būdas, kuriuo mes įdėti informaciją į krūvą, kaip mes pašalinti informaciją iš kamino. Visų pirma su kaminai taisyklė yra tik labiausiai neseniai pridėta elementas gali būti pašalintas. 

Taigi manau, apie tai, kaip jei tai kamino. Mes polių informacija ant savaime, ir tik viršuje dalykas krūva gali būti pašalintas. Mes negalime pašalinti dalykas po nes visa kita būtų žlugti ir nukristi. Taigi mes tikrai statome krūvą, kad tada mes turime pašalinti gabalėlį. Dėl šios priežasties mes dažniausiai nurodo į krūvą, kaip LIFO struktūrą, paskutinis in, first out. LIFO, paskutinis, pirmasis iš. 

Taigi dėl šio apribojimo kaip informacija gali būti įtraukta į ir pašalinti iš kamino, ten tikrai Tik du dalykai, ką galime padaryti su kamino. Mes gali stumti, kuris yra Terminas mes naudojame pridedant naujas elementas į viršų sukrauti, arba jei kamino neegzistuoja ir mes jį kurti nuo nulio, sukurti į pirmąją vietą krūvą būtų stumti. Ir tada pop, tai CS Rūšiuoti Terminas mes naudojame pašalinti labiausiai neseniai pridėta elementą iš kamino viršuje. 

Taigi mes ketiname pažvelgti tiek diegimas, tiek masyvo remiantis ir susijusi sąrašas pagrįstas. Ir mes ketiname pradėti su masyvo pagrįstos. Taigi čia yra pagrindinė idėja, ką masyvo remiantis kamino duomenų struktūra atrodys. Mes turime įvedėte apibrėžimą čia. Viduje, kad mes turime du narius laukai ar struktūros. Mes turime masyvą. Ir vėl aš, naudojant savavališkai duomenų tipas vertė. 

Taigi, tai gali būti bet koks duomenų tipas, int char arba kai kiti duomenys įrašykite anksčiau sukurta. Taigi, mes turime nuo jų dydžio pajėgumus masyvo. Talpa yra svaras apibrėžta pastovus, gal kažkur kitur mūsų faile. Taigi pastebėti jau su šio įgyvendinimas mes aprėpties save, kaip buvo paprastai atveju matricos, kurių mes negalime dinamiškai keisti dydį, kur yra tam tikras skaičius elementų daugiau, kad mes galime įdėti mūsų kamino. Šiuo atveju tai gebėjimas elementus. 

Mes taip pat sekti rietuvės viršaus. Tai, kas elementas yra labiausiai neseniai pridėta prie kamino? Ir todėl mes sekti, kad kintamu vadinamas viršuje. Ir visa tai bus suvynioti kartu į naują duomenų tipą, vadinamą kamino. Ir kai mes sukūrėme Ši nauja duomenų tipas galime traktuoti kaip bet koks kitas duomenų tipas. Mes galime paskelbti kamino s, kaip mes galime padaryti int x, arba char m. Ir kai sakome sukrauti ai, gerai, kas atsitinka, yra mes gauti rinkinį atminties atidėta mus. 

Šiuo atveju talpos Aš, matyt, nusprendė 10 nes aš turiu vieno kintamojo tipo kamino kuriame yra du laukai prisiminti. Masyvas, šiuo atveju vyksta turi būti iš sveikųjų skaičių masyvas kaip yra daugumoje mano pavyzdžių atveju. Ir dar vienas sveikasis skaičius kintamasis gali saugoti viršų, labiausiai neseniai papildė elementas prie kamino. Taigi vienas kamino, ką mes tik apibrėžta atrodo taip. Tai dėžutė, kurioje yra kaip 10 matrica, kas bus sveikieji šiuo atveju ir kitą kintamąjį, ten žalia nurodyti rietuvės viršuje. 

Norėdami nustatyti viršutinio kamino mes tiesiog pasakyti s.top. Štai kaip mes prieiti prie srityje statinio atšaukimo. s.top lygus 0 efektyviai tai daro mūsų kamino. Taigi dar kartą mes turime dvi operacijas kad mes galime atlikti dabar. Mes galime stumti, ir mes galime pop. Pradėkime paspaudimu. Vėlgi, stūmimas yra pridėti naują elementas kamino viršuje. 

Taigi, ką mes turime daryti, šio masyvo remiantis įgyvendinimas? Na apskritai Push funkcija vyksta to reikia priimti rodyklę į krūvą. Dabar imtis antrą ir galvoti apie jį. Kodėl mes norime priimti rodyklė į krūvą? Prisiminkite iš ankstesnių video apie kintamasis apimtis ir patarimų, kas nutiktų, jei mes tiesiog atsiuntė kamino, s, o į kaip parametras? Ką iš tikrųjų praėjo ten? Įsiminti mes sukurti kopiją kai mes pereiname jį funkcija nebent mes naudojame patarimų. Ir taip ši funkcija stumti poreikius priimti žymeklį į rietuvę taip, kad mes iš tikrųjų keičiasi kamino mes ketiname pakeisti. 

Kitas dalykas, stumti tikriausiai nori priimti yra duomenų elementas tipo vertės. Šiuo atveju, vėl, yra sveikas skaičius, kad mes ketiname pridėti prie kamino viršaus. Taigi mes turime mūsų du parametrus. Ką mes ketiname dabar daryti viduje stumti? Na, tiesiog, mes tiesiog ketiname pridėti kad elementas, kamino viršuje ir tada pakeisti, kur viršuje kamino yra, kad ai dot viršų vertę. Taigi tai yra tai, ką funkcija deklaracija paspaudimu gali atrodyti nurodytame masyvo pagrindu įgyvendinimas. 

Vėlgi, tai nėra sunku ir greitai taisyklės , kad galėtumėte pakeisti tai ir jis gali skirtis skirtingais būdais. Galbūt s pareiškė visame pasaulyje. Ir todėl jūs net nereikia praeiti ji yra, kaip parametras. Tai vėl tik Apskritai dėklas paspaudimu. Ir yra skirtingi būdų, kaip jį įgyvendinti. Bet šiuo atveju mūsų stumti ketina imtis du argumentai, rodyklė į krūvą ir duomenų elemento tipo verte, sveikasis skaičius tokiu atveju. 

Taigi, mes paskelbė s, mes sakė s.top lygus 0. Dabar galime stumti numeris 28 ant kamino. Na, ką tai reiškia? Na šiuo metu Į viršų kamino yra 0. Ir kas taip iš esmės nutiks tai mes ketiname laikytis numerį 28 į masyvą vietoje 0. Gana paprasta, tiesa, kad buvo viršuje, o dabar mes gerai eiti. Ir tada mes turime pakeisti tai, ką rietuvės viršaus bus. Taip, kad kitą kartą mes stumti in elementas, mes ketiname laikyti jį masyvas vietą, tikriausiai ne 0. Mes nenorime, kad perrašyti Ką mes tiesiog įdėti ten. Ir todėl mes tiesiog perkelti viršaus į 1. Tai tikriausiai turi prasmę. 

Dabar, jei mes norime įdėti kitą elementą ant kamino, sako, kad mes norite stumti 33, Na, dabar mes tik ketina imtis 33 ir įdėti jį masyvo vietos numerį 1, ir tada pakeisti viršuje mūsų kamino turi būti masyvas vietą numeris du. Taigi, jei kitą kartą mes norime stumti elementą ant kamino, Tai bus įdėti į masyvą vietoje 2. Ir darykime, kad vienas daugiau laiko. Mes stumti 19 off rietuvių. Mes įdėti 19 masyvo vietoje 2 ir pakeisti mūsų kamino viršų būti masyvas vieta 3 Taigi, jei kitą kartą mes reikia padaryti push mes gera eiti. 

Gerai, kad manimi stumia trumpai. Ką apie Popping? Taigi Popping yra tarsi priešinys stumia. Tai, kaip mes pašalinti duomenis iš kamino. Ir apskritai pop poreikius daryti toliau. Reikia sutikti rodyklę į kamino, vėl bendruoju atveju. Kai kuriose kitu atveju jums gali pareiškė kamino visame pasaulyje, Tokiu atveju jums nereikia perduoti jį į, nes jis jau turi prieigą prie jo kaip pasaulio kintamasis. Bet tada ką dar mes turime daryti? Na mes buvome incrementing Iš Tiesioginio kamino viršaus, todėl mes tikriausiai norės į Mažėja kamino viršų pop, tiesa? Ir tada, žinoma, mes taip pat norės grąžinti vertę, kad mes pašalinti. Jei mes pridėti elementus, mes norime gauti elementus iš vėliau, mes tikriausiai iš tikrųjų nori laikyti juos, kad mes ne tiesiog ištrinti juos iš sukrauti ir tada nieko su jais. Apskritai, jei mes stumti ir Popping čia norime laikyti šį informacija prasmingai ir taip tai nereiškia, kad jausmas tiesiog jį išmeskite. Taigi ši funkcija turėtų tikriausiai grąžina reikšmę mums. 

Taigi tai, kas deklaracija pop gali atrodyti kaip ten viršuje kairėje. Ši funkcija grąžina duomenų tipo vertės. Vėlgi mes buvome naudojant sveikieji skaičiai visoje. Ir ji priima žymiklį į kamino kaip jos vienintelis argumentas ar vienintelis parametras. Taigi, kas yra pop ketinate daryti? Tarkime, mes norime dabar pop elementas off s. Taigi nepamirškite pasakiau, kad kaminai paskutinis in, first out, LIFO duomenų struktūras. Kuris elementas ketina būti pašalintas iš kamino? Ar galite atspėti, 19? Kadangi jūs norite būti teisus. 19 buvo paskutinis elementas mes pridėjome į kamino, kai mes buvome stumia elementus,, ir todėl ji ketina pirmas elementas, kuris pašalinamas. Tai tarsi mes sakėme, 28, ir tada mes įdėti 33 ant jo, ir mes įdėti 19 viršuje, kad. Vienintelis elementas mes galime pakilti yra 19. 

Dabar diagramoje čia, ką aš padariau yra tarsi ištrinta nuo 19 masyvo. Tai ne iš tikrųjų ką mes ketiname daryti. Užtenka tik ketina rūšies iš apsimesti, kad nėra. Jis vis dar ten kad atminties vietą, bet mes tik ketina jį ignoruoti keičiant mūsų kamino viršų gražu 3 2. Taigi, jei mes dabar stumti kita ant kamino elementas, tai per parašyti 19. 

Bet tegul ne eiti per bėdų ištrynę 19 iš kamino. Mes galime tik apsimesti, kad nėra. Taikant kamino jis dingo, jei mes pakeisti viršuje, kad būtų 3 2, o ne. Gerai, kad buvo gana daug. Tai viskas, ką reikia padaryti pop elementas išjungtas. Darom dar kartą. Taigi aš pabrėžė, kad raudona spalva čia rodo, mes darome kitą skambutį. Mes ketiname padaryti tą patį. 

Taigi, kas nutiks? Na, mes ketiname saugoti 33 X ir mes ketiname pakeisti kamino viršaus iki 1. Taigi, kad jei mes dabar stumti elementas į krūvą, kuri mes ketina daryti dabar, kas nutiks yra mes ketiname perrašymo masyvas vietą numeris 1. Taigi, kad 33, kuris buvo tarsi liko atsilieka, kad mes tik apsimetė ten nėra daugiau, mes tik ketina į Clobber ją ir įdėti 40 ten vietoj. Ir tada, žinoma, nes mes padarė stumti, mes ketiname prieaugio top rietuvės 1-2 taip, kad jei dabar mes pridėti Kitas elementas jis bus eiti į masyvo vietos numeris du. 

Dabar susiję sąrašai kitą būdas įgyvendinti kaminai. Ir jei tai apibrėžimo ekranas čia atrodo pažįstamas, tai todėl, kad jis atrodo beveik lygiai taip pat,, iš tikrųjų, tai gana daug yra tiksliai toks pat, kaip pavieniui susietą sąrašo, Jei prisimenate iš mūsų diskusija atskirai susijęs sąrašus kitoje vaizdo. Vienintelis apribojimas čia yra mums, programuotojams, mes neleidžiama įterpti ar ištrinti atsitiktinai iš pavieniui susietą sąrašą kuriuos mes anksčiau galėjo daryti. Mes tik dabar galite įterpti ir pašalinti iš priekinis arba susietą viršų sąrašas. Tai tikrai tik Skirtumas nors. Tai kitaip atskirai susijusi sąrašas. Tai tik apribojimas pakeisti savyje programuotojais, kad keičia jį į rietuvę. 

Taisyklė čia yra visada išlaikyti žymiklį į susietą sąrašą galvos. Tai, žinoma, visuotinai svarbi taisyklė pirmas. Dėl pavieniui susiję sąrašą vistiek tik reikia žymiklį į galvą siekiant turėti, kad grandinės galėtų kreiptis kiekvienam kito elemento susijusioje sąrašą. Bet tai ypač svarbus kamino. Ir taip paprastai esate vyksta iš tikrųjų nori Ši rodyklė būti pasaulio kintamasis. Tai tikriausiai bus dar lengviau, kad taip. Taigi, kas yra push ir pop analogai? Teisė. Taigi stumia vėl pridedant naujas elementas prie kamino. Be susietą sąrašą, kad reiškia, kad mes ketiname turėti sukurti naują mazgą, kad mes ketiname pridėti į susietą sąrašą ir vykdykite veiksmus atidžiai kad mes sukūrėme anksčiau į vieną, susijusių sąrašus įtraukti jį į grandinė nesulaužant grandinę ir prarasti arba orphaning bet elementai iš susietų sąrašą. Ir tai iš esmės, ką tai mažai BLOB teksto ten apibendrina. Ir tegul pažvelgti ne tai, kaip schemoje. 

Taigi čia mūsų susijusi sąrašas. Tai kartu yra keturi elementai. Ir dar puikiai Štai mūsų kamino, kuriame yra keturi elementai. Ir tarkim dabar mes norime stumti naują elementą į šį steką. Ir mes norime stumti nauja daiktai, kurių duomenys vertė yra 12. Na, ką mes ketiname daryti? Na pirmiausia mes ketiname malloc erdvė, dinamiškai skirti vietos naują mazge. Ir, žinoma, iš karto po mes paskambinti malloc mes visada įsitikinkite, kad patikrinti for null, nes jei mes turime null Atgal ten buvo keletas problema rūšiuoti. Mes nenorime, kad dereference to null Rodyklė arba jūs kenčia SEG gedimą. Tai nėra gerai. Taigi mes malloced mazgas. Tarkime, mes turėjo sėkmę čia. Mes ketiname įdėti į 12 duomenys laukas tos mazgas. Dabar jūs prisiminti, kuris iš mūsų patarimų juda kitas todėl mes negalime nutraukti grandinę? Mes turime keletą galimybių, bet čia tik viena, kad ketina būti saugus yra nustatyti naujienas šalia Rodyklė taškas senosios galvos sąrašo ar kas greičiau bus senas vadovas sąrašo. Ir dabar, kad visi mūsų elementai yra grandinės kartu, mes galime tiesiog perkelti sąrašą atkreipti į tą pačią vietą, kad naujos daro. Ir mes dabar efektyviai stumti naujas elementas ant iš kamino priekyje. 

Pop Mes tik norime ištrinti tą pirmąjį elementą. Ir todėl iš esmės ką mes turime padaryti čia Na mes turime rasti antrą elementą. Kad ilgainiui taps nauja galvą, kai mes ištrinti pirmasis. Taigi mes tiesiog reikia pradėti nuo pradžia, perkelti vieną į priekį. Kai mes turime griebtis dėl vieno Persiųsti kur mes šiuo metu mes galime ištrinti pirmasis saugiai ir tada mes galime tiesiog perkelti galvą atkreipti dėmesį į tai, kas buvo antroji kadencija, o tada dabar yra pirmasis, kad po to, kai mazgas buvo ištrintas. 

Taigi dar kartą, atsižvelgiant išvaizdą ne tai, kaip schemoje mes noriu dabar pop elementas išjungti šio kamino. Taigi, ką mes galime padaryti? Na mes pirmą kartą ketina sukurti naujas žymeklis, kad vyksta iki punkto pačioje vietoje kaip ir galvos. Mes ketiname perkelti jį vieną poziciją Persiųsti sakydamas Trav dydžiu neprilygstami Trav šalia kurios, pavyzdžiui, būtų iš anksto į Trav rodyklę vieną pozicija į priekį. Dabar, mes turime turėti ant pirmojo elemento per rodykle vadinamas, sąrašą ir Antrasis elementas per žymeklis vadinamas Trav, mes galime saugiai ištrinti, kad Pirmasis elementas iš kamino neprarasdamas likusios grandinės, nes mes turi būdą, kaip perduoti prie antrojo elemento perduoti būdu iš žymeklis vadinamas Trav. 

Taigi, dabar mes galime išlaisvinti tą mazgą. Galime nemokamai sąrašą. Ir tada viskas, ką reikia padaryti dabar judėti sąrašą taško į tą pačią vietą kad Trav daro, ir mes tarsi atgal kur mes pradėjome prieš mums stumiama 12 ant į pirmąją vietą, į dešinę. Tai yra būtent tai, kur buvome. Mes turėjome šį keturių elementų kamino. Mes pridėjo penktadalį. Mes stumti penktadalį elementas, ir tada mes popped, kad pastaruoju įtraukta elementą atgal išjungti. 

Tai tikrai gana daug visi yra kaminai. Galite jas įgyvendinti, kaip matricos. Galite jas įgyvendinti kaip susijusios sąrašus. Yra, žinoma, kita būdų, kaip jas įgyvendinti, taip pat. Iš esmės todėl mes būtų naudoti rietuvės yra išlaikyti duomenis tokiu būdu, kad neseniai pridėta elementas yra pirmas dalykas, kurį mes norės grįžti. Aš Doug Lloyd, tai CS50.