DOUG LLOYD: Allt í lagi, svo með þessum tímapunkti sem þú ert líklega nokkuð kunnuglegt með fylki og tengd listum sem er tvær aðal gögn uppbygging sem við höfum talað um að halda setur gögn af svipuðum gagnatög skipulögð. Nú erum við að fara að tala um nokkra tilbrigðum á fylki og tengd listum. Í þessu myndbandi sem við erum að fara að tala um stafla. Sérstaklega við erum að fara að tala um gögn uppbygging kallast stafla. Muna frá fyrri umræðum um ábendingum og minni, að stafla er einnig nafn fyrir a hluti af minni þar statically lýst memory-- minni sem þér nafn, breytur sem þú nafn, et cetera og virka rammar sem við einnig kalla stafla ramma til. Svo er þetta stafla gögn uppbygging ekki stafla hluti af minni. OK. 

En hvað er stafla? Svo það er ansi mikið bara sérstaka tegund af uppbyggingu sem viðheldur gögn á skipulegan hátt. Og það er tveir mjög algengar leiðir til að hrinda í framkvæmd stafla með tveimur gögn uppbygging sem við erum nú þegar kunnugt, fylki og tengd listum. Hvað gerir stafla sérstakt er Leiðin sem við setjum upplýsingar í stafla, og hvernig við fjarlægja upplýsingar úr stafla. Einkum með stafla reglan er aðeins mest bætt nýlega þáttur er hægt að fjarlægja. 

Svo hugsa um það eins og ef það er stakkur. Við erum hlóðust upplýsingar ofan á sig, og aðeins eina efst á staurnum er hægt að fjarlægja. Við getum ekki losnað við neitt undir vegna þess að allt annað myndi hrynja og falla yfir. Svo við í raun ert að byggja upp stafla sem við höfum þá að fjarlægja stykkjum. Vegna þessa að við vísa almennt að stafla sem LIFO uppbyggingu, endast í, fyrst út. LIFO, endast inn, fyrst út. 

Svo vegna þessa takmörkun á hvernig upplýsingar er hægt að bæta við og fjarlægð úr stafla, það er í raun aðeins tveir hlutir sem við getum gert með stafla. Við getum ýta, sem er tíma við notum til að bæta við nýju atriði til the toppur af the stafla, eða ef stafla er ekki til og við erum að skapa það frá grunni, skapa stafla í fyrsta sæti væri að þrýsta. Og þá skjóta, sem er tegund af CS Hugtakið við notum til að fjarlægja nýlega bætt frumefni úr efsta hluta stafla. 

Þannig að við erum að fara að líta á bæði gerð, bæði array byggir og tengda listanum byggt. Og við erum að fara að byrja með array byggir. Svo hér er grunn hugmynd um hvað array byggir stafla gögn uppbygging myndi líta út. Við höfum vélritað skilgreiningu hér. Inni að við höfum tvo menn eða sviðum uppbyggingu. Við höfum fylki. Og aftur ég er að nota er handahófskennt gögn tegund gildi. 

Þannig að þetta gæti verið hvaða gögn tegund, INT bleikju eða einhver önnur gögn tegund þú áður búið. Þannig að við höfum fjölda stærð getu. Getu verið pund skilgreind stöðug, kannski annars staðar í skrá okkar. Svo eftir þegar við þetta tiltekna framkvæmd við erum afmarka okkur sem var yfirleitt málið með fylki, sem við getum ekki virk búa, þar er ákveðin tala staka hámarki sem við getum sett í stafla okkar. Í þessu tilfelli er það þætti getu. 

Við stöndum einnig utan um efst á stafla. Hvað þáttur er mest nýlega bætt við stafla? Og svo við að halda utan um það í breytu sem heitir ofan. Og allt þetta fær pakkað upp saman í nýja tegund gagna kallast stakkur. Og þegar við erum búin þetta nýja gögn gerð við getum meðhöndla það eins og önnur gögn tegund. Við getum lýst stafla s, rétt eins og við gætum gert int x, eða bleikju y. Og þegar við segjum stafla s, vel hvað gerist er að við fá a setja af minni til hliðar fyrir okkur. 

Í þessu tilfelli getu Ég hef greinilega ákveðið er 10 vegna þess að ég hef fengið einn af taginu stafla sem inniheldur tvær sviðum muna. An array, í þessu tilfelli er að fara að vera array af heiltölur eins og raunin er í flestum dæmum mínum. Og annar heiltölubreytu fær um að geyma á toppinn, The nýlega bætt þáttur í stafla. Svo eitt stafla af því sem við bara skilgreint lítur svona út. Það er kassi sem inniheldur fylki af 10 hvað verður heiltölur í þessu tilfelli og annar heiltölubreytu það í grænu að tilgreina efst á stafla. 

Til að stilla the toppur af the stafla við segjum bara s.top. Það er hvernig við aðgang að reit af uppbyggingu muna. s.top jafngildir 0 raun er þetta að stafla okkar. Svo aftur að við höfum tvær aðgerðir sem við getum gert núna. Við getum ýta og við getum skjóta. Við skulum byrja með ýta. Aftur, þrýsta er að bæta við nýjum þáttur til the toppur á stafla. 

Svo hvað þurfum við að gera í þetta array undirstaða framkvæmd? Jæja í Almennt ýta virka er að fara að þurfa að sætta sig við bendi á mánudaginn. Nú taka annað og hugsa um það. Hvers vegna viljum við taka bendi á mánudaginn? Muna frá fyrri vídeó á Variable Gildissvið og ábendingum, hvað myndi gerast ef við sendum bara stafla, s frekar inn sem stiki? Hvað myndi reyndar vera liðin í það? Mundu að við erum að búa til afrit þegar við gefa það til aðgerð nema við notum ábendingum. Og svo þessi aðgerð ýta þörfum að samþykkja bendi á mánudaginn þannig að við erum í raun að breyta stafla sem við ætlum að breyta. 

The annar hlutur ýta vill sennilega að taka er gögn þáttur tegund gildi. Í þessu tilviki, aftur, heil tala sem við erum að fara að bæta við efst á stafla. Þannig að við höfum fengið tvær breytur okkar. Hvað erum við að fara að nú gera inni ýta? Jæja, einfaldlega, við erum bara að fara að bæta við þessi þáttur til the toppur á stafla og þá breyta þar efst á stafla er, að er punktur efst gildi. Svo er þetta það fall yfirlýsing um að ýta getur litið eins og í array byggir framkvæmd. 

Aftur er þetta ekki föst regla sem þú gætir breyta þessu og hafa það verið á mismunandi vegu. Kannski s er lýst á heimsvísu. Og svo þú þarft ekki einu sinni að gefa það er sem viðfang. Þetta er aftur bara almenn mál fyrir ýta. Og það eru mismunandi leiðir til að framkvæma það. En í þessu tilfelli okkar ýta er að fara að taka tvær breytur, bendi á stafla og a gögn þátturinn af gerðinni verðmæti, heiltala í þessu tilfelli. 

Þannig að við lýst s, við sagði s.top jafngildir 0. Nú skulum ýta númer 28 á mánudaginn. Jæja hvað þýðir það? Jæja nú Efst á stafla er 0. Og svo er það í grundvallaratriðum að fara að gerast er við erum að fara að halda fjölda 28 í array stað 0. Mjög einfalt, ekki satt, að var efst og nú erum við gott að fara. Og þá þurfum við að breyta því sem efst á stafla verður. Þannig að næst þegar við ýta stak í, við erum að fara að geyma það í array staðsetningu, sennilega ekki 0. Við viljum ekki að skrifa hvað við setjum bara þarna. Og svo við verðum bara að fara á toppinn á 1. Það gerir líklega vit. 

Nú ef við viljum setja annar þáttur á mánudaginn, segja að við viljum að ýta 33, Jæja núna erum við bara að fara að taka 33 og setja það á array staðsetningu númer 1, og þá breyta efst okkar stafla vera array staðsetningu númer tvö. Svo ef næsta skipti sem við viljum ýta stak á mánudaginn, það verður sett í array stað 2. Og við skulum gera það einu sinni enn. Við munum ýta 19 burt af stafla. Við munum setja 19 í array stað 2 og breyta efst stafla okkar að vera array staðsetningu 3 þannig að ef við næstu þarf að gera ýta við erum gott að fara. 

OK, svo það er að þrýsta í hnotskurn. Hvað um pabbi? Svo er pabbi konar hliðstæðu til að þrýsta. Það er hvernig við að fjarlægja gögn úr stafla. Og í almennar þarfir pop að gera eftirfarandi. Það þarf að taka bendi á stafla, aftur í almennu máli. Í sumum öðrum tilvikum gætir þú hafa lýst stafla heimsvísu, í því tilviki að þú þarft ekki að gefa það í því að hún hefur nú þegar aðgang að henni sem alþjóðlegt breytu. En hvað þá annað þurfum við að gera? Jæja við vorum incrementing efst á stafla í ýta, þannig að við erum líklega að fara að vilja að lækka efst á stafla í popp, ekki satt? Og svo auðvitað við erum líka að fara til að vilja að skila gildi sem við fjarlægja. Ef við erum að bæta þætti, við viljum að fá þætti út síðar, við líklega í raun vilt geyma þá svo við ekki bara eyða þeim úr stafla og þá gera ekkert með þeim. Almennt ef við erum ýta og pabbi hér við viljum geyma þetta upplýsingar á markvissan hátt og svo það þýðir ekki að gera vit í að bara henda því. Svo þessi aðgerð ætti líklega skila gildi til okkar. 

Svo er þetta það yfirlýsingu um pop gæti litið út eins og það efst til vinstri. Þetta fall skilar gögn af gerðinni gildi. Aftur höfum við verið að nota heiltölur í gegn. Og það tekur bendi á mánudaginn og il rök hennar eða eini breytu. Svo hvað er pop að fara að gera? Segjum að við viljum nú skjóta stak burt af s. Svo man ég sagði að stafla eru síðustu í, fyrst út, LIFO gögn uppbygging. Hvaða þáttur er fara að fjarlægður úr stafla? Vissir þú giska 19? Þar sem þú vilt vera rétt. 19 var síðasta þáttur við bætt við stafla þegar við vorum að ýta þætti á, og svo það er að fara að fyrsta þáttur sem fær eytt. Það er eins og ef við sögðum 28, og þá erum við að setja 33 ofan á það, og við setjum 19 ofan á það. Eina þáttur sem við getum tekið burt er 19. 

Nú á myndinni hér það sem ég hef gert er tegund af eytt 19 frá array. Það er í raun ekki það sem við erum að fara að gera. Við erum bara að fara að eins konar af þykjast það er ekki þar. Það er enn í að minni staðsetningu, en við erum bara að fara að hunsa það með því að breyta efst staflans okkar frá því að vera 3 til 2. Svo ef við vorum að nú ýta annar þáttur á mánudaginn, það myndi yfir skrifa 19. 

En við skulum ekki fara í gegnum vandræði um að eyða 19 úr stafla. Við getum bara láta það er ekki þar. Í þeim tilgangi að stafla það er farið ef við að breyta efst til að vera 2 í stað 3. Allt í lagi, svo það var ansi mikið það. Það er allt sem við þurfum að gera að skjóta stak af. Við skulum gera það aftur. Þannig að ég hef bent henni í rauðu hér að benda að við erum að gera annað símtal. Við erum að fara að gera það sama. 

Svo hvað er að fara að gerast? Jæja, við erum að fara að geyma 33 í x og við erum að fara til að breyta efst á stafla til 1. Þannig að ef við vorum nú að ýta að þáttur í stafla sem við erum að fara að gera núna, hvað er að fara að gerast er að við erum að fara Skrifa yfir array staðsetningu númer 1. Þannig að 33 voru eins konar vinstri bak sem við lést bara er ekki þar lengur, við erum bara að fara að clobber það og setja 40 þar í staðinn. Og svo auðvitað þar sem við gert ýta, við erum að fara að hækka í Efst á stafla frá: 1 til að 2 þannig að ef við bætum nú annar þáttur það verður fara í array staðsetningu númer tvö. 

Nú tengd listum eru önnur leiðin til að innleiða stafla. Og ef þessari skilgreiningu hins skjár lítur hér þekki þig, það er vegna þess að það lítur næstum nákvæmlega það sama, í raun, það nokkuð mikið er einmitt sama og eintengdan lista, ef þú manst frá umræðu okkar ein tengd listum í öðru vídeó. Eina takmörkun hér er fyrir okkur sem forritari, við erum ekki leyft að setja inn eða eyða af handahófi frá eintengdan lista sem við gætum áður gert. Við getum aðeins núna að setja inn og eyða úr framan eða ofan á tengd lista. Það er í raun eina Munurinn þó. Þetta er annars eintengdan lista. Það er aðeins takmörkun skipta á okkur sem forritari að breytist það í stafla. 

Reglan hér er að alltaf að halda a bendi á höfuð tengda listanum. Þetta er auðvitað almennt mikilvægur regla fyrst. Fyrir eintengdan lista samt þér þarf aðeins bendi á höfði í því skyni að hafa sem keðja vera fær um að vísa að sérhver önnur frumefni í tengda listanum. En það er sérstaklega mikilvægt með stafla. Og svo almennt að þú ert fara til raunverulega vilja þetta bendi til að vera alþjóðlegt breytu. Það er líklega að fara að enn auðveldara þannig. Svo það eru hliðstæður ýta og popp? Hægri. Svo ýta aftur er að bæta a nýr þáttur á mánudaginn. Í tengda listanum sem þýðir að við erum að fara að hafa til að búa til nýjan hnút sem við erum að fara að bæta inn í tengda listanum, og þá fylgja varfærin skref sem við höfum lýst áður í ein tengd listum að bæta því við keðja án þess að brjóta keðju og tapa eða orphaning eitthvað þættir í tengda listanum. Og það er í rauninni það sem að lítið Blob texta þar samantekt. Og við skulum taka a líta á það sem skýringarmynd. 

Svo er hér tengd listi okkar. Það inniheldur samtímis fjóra þætti. Og meira fullkomlega Hér er okkar stafla sem inniheldur fjóra þætti. Og við skulum segja að við viljum nú að ýta nýtt atriði á þessa stafla. Og við viljum að ýta nýtt atriði sem gildi gagnanna er 12. Jæja hvað erum við að fara að gera? Jæja fyrst við erum að fara að malloc pláss, virk úthluta pláss fyrir nýja hnút. Og auðvitað strax eftir við að hringja að malloc við alltaf ganga úr skugga um að athuga fyrir null, því ef við fengum null aftur það var einhvers konar vandamál. Við viljum ekki að dereference þess null bendillinn eða þú munt þjást seg kenna. Það er ekki gott. Þannig að við höfum malloced hnútarins. Við munum gera ráð sem við höfum haft árangur hér. Við erum að fara að setja 12 í gögn sviði hnút. Nú þú manst hvaða ábendingum okkar færist næsta þannig að við brjóta ekki keðju? Við hafa a par af valkostur hér en sú eina sem er að fara til að vera örugg er að setja fréttir næsta músina til benda á gamla höfuð á listanum eða hvað mun brátt vera gamall yfirmaður lista. Og nú að allt okkar þættir eru handjárnaða saman, við getum bara flutt lista til að benda á sama stað sem nýtt gerir. Og við höfum nú í raun ýtt a Ný þáttur framan á mánudaginn. 

Að skjóta Við bara vilja til að eyða sem fyrst þáttur. Og svo í rauninni það við þurfum að gera hér, vel við verðum að finna annað frumefni. Loksins að verða að nýjum höfuð eftir að við eyða fyrsta. Þannig að við þurfum bara að byrja frá upphaf, færa einn framherja. Þegar við höfum fengið að halda á einn áfram þar sem við nú við erum getur eytt fyrsti örugglega og þá getum við bara færa höfuðið til að benda á hvað var Seinni tíma og þá nú er fyrsta eftir að hnút hefur verið eytt. 

Svo aftur, taka a líta á það sem skýringarmynd við viljum nú skjóta að þáttur burt af þessum stafla. Svo hvað eigum við að gera? Jæja við erum fyrst að fara að búa til ný músina sem er að fara til að benda á sama stað og höfuðið. Við erum að fara að flytja það eina stöðu áfram með því að segja Trav jafn Trav næst til dæmis, þar sem myndi fara á Trav músina einn stöðu áfram. Nú þegar við höfum fengið halda á fyrstu frumefni gegnum músina heitir listanum og er Annað þáttur gegnum bendi heitir Trav, getum við örugglega eyða að Fyrsti þátturinn úr stafla án þess að missa restina keðjunni vegna þess að við hafa a vegur til að vísa við annað frumefni senda með því að í bendi heitir Trav. 

Svo nú getum við frjáls hnút. Við getum frjáls lista. Og þá er allt sem við þurfum að gera núna færa lista til að benda á sama stað sem trav gerir, og við erum svona aftur þar sem við byrjuðum áður en við ýtt 12 á í fyrsta sæti, ekki satt. Þetta er einmitt þar sem við vorum. Við áttum fjóra þátturinn stafla. Við bætt við fimmta. Við ýtt fimmtungur þáttur á, og þá erum við smella sem nýlega bætt þáttur aftur burt. 

Það er í raun ansi mikið allt sem er til stafla. Þú getur innleiða þá sem fylki. Þú getur innleiða þá sem tengd listum. Það eru, Að sjálfsögðu henta önnur leiðir til að framkvæma þær eins og heilbrigður. Í grundvallaratriðum er ástæða þess að við myndum nota stafla er að halda gögnum á þann hátt að nýlega bætt þáttur er það fyrsta sem við erum fara til að vilja fá til baka. Ég er Doug Lloyd, þetta er CS50.