DOUG LLOYD: Lahat ng mga karapatan, kaya sa pamamagitan ng puntong ito ikaw ay malamang na medyo pamilyar sa array at mga listahan ng link kung saan ay ang dalawang pangunahing istruktura ng data na namin usapan tungkol sa para sa pagsunod sa mga hanay ng mga data ng mga katulad na uri ng data na inayos. Ngayon kami ay pagpunta sa makipag-usap tungkol sa isang pares ng mga pagkakaiba-iba sa array at mga listahan ng link. Sa video na ito kami ay pagpunta makipag-usap tungkol stack. Partikular kami ay pagpunta sa makipag-usap tungkol sa isang istraktura ng data na tinatawag na isang stack. Pagpapabalik mula sa mga nakaraang talakayan tungkol sa mga payo at memorya, na ang stack ay din ang pangalan para sa isang segment ng memory kung saan statically ipinahayag na memorya memory na kayo pangalan, mga variable na pangalan mo, et iba pa at pag-andar ng mga frame na kung saan namin din umiiral call frames stack. Kaya ito ay isang istraktura stack data hindi isang segment stack ng memory. SIGE. 

Ngunit ano ang isang stack? Kaya ito ay medyo mas lamang ng isang espesyal na uri ng istraktura na nagpapanatili ng data sa isang organisadong paraan. At may dalawang tunay karaniwang mga paraan upang ipatupad stack gamit ang dalawang mga istraktura ng data na hindi namin na pamilyar sa, array at mga listahan ng link. Kung bakit ang isang stack espesyal ay ang paraan na kung saan inilalagay namin ang impormasyon sa stack, at ang paraan ng aming tanggalin ang impormasyon mula sa stack. Sa partikular na may mga stack ang mga tuntunin ay lamang ang pinaka kamakailan maaaring alisin karagdagang elemento. 

Kaya mag-isip tungkol sa mga ito tulad ng kung ito ay isang stack. Kami ay piling impormasyon sa itaas ng kanyang sarili, at lamang ang mga bagay sa itaas ng pile maaaring alisin. Hindi namin maaaring alisin ang mga bagay sa ilalim ng dahil lahat ng iba pa gagawin tiklupin at mahulog. Kaya namin talagang ay pagbuo ng isang stack na pagkatapos kami ay may sa alisin ang piraso ng piraso. Dahil dito ang aming karaniwang sumangguni sa isang stack bilang isang istraktura LIFO, huling sa, first out. LIFO, tatagal, unang labas. 

Kaya dahil dito pagbabawal sa kung paano maaaring idagdag ang impormasyon sa at inalis mula sa isang stack, may tunay na lamang ng dalawang mga bagay na maaari naming gawin sa isang stack. Maaari naming itulak, kung saan ay ang katawagan na ginagamit namin para sa pagdaragdag isang bagong sangkap sa itaas ng stack, o kung ang stack ay hindi umiiral at kami ay ang paglikha ng ito mula sa simula, paglikha ng stack sa unang lugar ay panunulak. At pagkatapos ay pop, na ang uri ng CS kataga naming gamitin upang alisin ang mga pinaka-kamakailan dagdag na sangkap mula sa tuktok ng stack. 

Kaya kami ay pagpunta upang tumingin sa parehong pagpapatupad, batay sa parehong array at naka-link na listahan batay. At kami ay pagpunta sa magsimula sa array based. Kaya dito ay ang pangunahing ideya ng kung ano ang ang istraktura stack data array batay ay ang hitsura. Kami ay may isang kahulugan ng nag-type dito. Sa loob ng na kami ay may dalawang mga kasapi o mga patlang ng mga istraktura. Kami ay may isang array. At muli ako gamit ang arbitrary halaga uri ng data. 

Kaya ito ay maaaring sa anumang mga uri ng data, int char o ilang iba pang data type nilikha mo dati. Kaya kami ay may isang hanay ng mga kakayahan laki. Kapasidad na tinukoy constant ng kalahating kilong, marahil sa ibang lugar sa aming file. Kaya mapapansin na sa partikular na pagpapatupad namin ay lukso ang ating mga sarili bilang ay karaniwang ang kaso sa array, na kung saan hindi namin maaaring magilas na baguhin ang laki, kung saan may isang tiyak na bilang ng maximum na mga elemento na maaari naming ilagay sa aming stack. Sa kasong ito ito ay elemento ng kapasidad. 

Panatilihin din kami ng track ng sa itaas ng stack. Ano ang sangkap ay ang pinaka kamakailang idinagdag sa stack? At kaya sinusubaybayan namin na sa variable na tinatawag na top a. At lahat ng ito ay makakakuha ng abala magkasama sa isang bagong uri ng data na tinatawag na isang stack. At sa sandaling kami ay nilikha ang bagong uri ng data maaari naming ituring ito tulad ng anumang iba pang uri ng data. Maaari naming ipahayag stack s, tulad ng maaari naming gawin int x, o char y. At kapag kami sabihin stack s, well kung ano ang mangyayari ay makakakuha tayo ng isang set ng mga magtabi memory para sa amin. 

Sa kapasidad na kaso Tila ako ay nagpasya ay 10 dahil Mayroon akong isang single variable ng uri ng stack na naglalaman ng dalawang mga patlang na pagpapabalik. Ang dami, sa kasong ito ay pagpunta upang maging isang array ng mga integer tulad ng kaso sa karamihan ng aking mga halimbawa. At isa pang integer variable kaya ng pagtatago sa itaas, ang pinaka-kamakailang idinagdag sangkap sa mga stack. Kaya isa single stack ng kung ano ang aming tinukoy lamang ganito ang hitsura nito. Ito ay isang kahon na naglalaman ng isang hanay ng mga 10 ano ay integer sa kasong ito at isa pang integer variable doon sa green upang ipahiwatig ang tuktok ng stack. 

Upang i-set sa itaas ng stack naming sabihin lamang s.top. Iyon ay kung paano namin ma-access ang isang larangan ng isang istraktura pagpapabalik. s.top katumbas ng 0 epektibong Ginagawa ito sa aming stack. Kaya muli kami ay may dalawang mga operasyon maaari naming gawin ngayon. Maaari naming itulak at maaari naming pop. Magsimula tayo sa push Hayaan. Muli, panunulak ay nagdadagdag ng isang bagong sangkap sa itaas ng stack. 

Kaya kung ano ang dapat nating gawin sa array na ito pagpapatupad batay? Well sa pangkalahatan ang push function ay pagpunta sa kailangan upang tanggapin ang isang pointer sa stack. Ngayon kumuha ng isang pangalawang at sa tingin tungkol dito. Bakit gusto naming tanggapin isang pointer sa stack? Pagpapabalik mula sa mga nakaraang mga video sa variable na saklaw at mga payo, ano ang mangyayari kung ipinadala namin lamang stack, s halip sa bilang parameter? Ano ang gusto talaga maipasa sa doon? Tandaan namin ang paglikha ng isang kopya kapag pumasa namin ito sa isang function maliban kung ginagamit namin mga payo. At kaya itulak ang function na pangangailangan upang tanggapin ang isang pointer sa stack kaya na namin ang aktwal na binabago stack balak namin na baguhin. 

Marahil nais Ang iba pang bagay push to tanggapin ang isang elemento ng data ng halaga type. Sa kasong ito, muli, na isang integer na kami ay pagpunta upang idagdag sa tuktok ng stack. Kaya Mayroon namin ang aming dalawang mga parameter. Ano ang mga namin pagpunta sa ngayon ang gagawin sa loob ng push? Well, kailangan lang, lamang kami ay pagpunta upang magdagdag ng sangkap na sa tuktok ng stack at pagkatapos ay baguhin kung saan ang tuktok ng ang stack ay, na s dot top halaga. Kaya ito ay kung ano ang isang function deklarasyon para sa push maaaring magmukhang sa isang array-based na pagpapatupad. 

Muli ito ay hindi isang mabigat na kautusan na maaari mong baguhin ito at magkaroon ng mag-iba ang mga ito sa iba't ibang paraan. Marahil s ay ipinahayag globally. At kaya hindi mo kahit na kailangan upang pumasa ito ay bilang isang parameter. Ito ay muli lamang ng isang pangkalahatang mga kaso para sa push. At may mga iba't-ibang mga paraan upang ipatupad ito. Ngunit sa kasong ito ang aming push ay pagpunta sa tumagal dalawang argumento, isang pointer sa isang stack at isang elemento ng data ng halaga type, integer sa kasong ito. 

Kaya ipinahayag namin s, kami ay Sinabi s.top katumbas ng 0. Ngayon natin itulak ang ipaalam number 28 papunta sa stack. Well kung ano ang ibig sabihin nito? Well kasalukuyang ang tuktok ng stack ay 0. At kaya kung ano talaga ang pagpunta sa mangyari ay kami ay pagpunta sa stick sa bilang 28 sa array lokasyon 0. Medyo prangka, kanan, na ay ang top at ngayon kami ay handa na upang patakbuhin. At pagkatapos ay kailangan namin upang baguhin kung ano ang sa itaas ng stack ay. Kaya na ang mga susunod na panahon itulak namin ang isang elemento sa, kami ay pagpunta sa store na ito sa lokasyon array, marahil ay hindi 0. Hindi namin nais na patungan kung ano ang namin lamang ilagay doon. At kaya kailangan lang ilipat namin sa itaas hanggang 1. Iyon marahil ang akma. 

Ngayon kung gusto naming ilagay ang isa pang elemento papunta sa stack, sabihin nating nais naming itulak 33, well ngayon lang kami na kumuha ng 33 at ilagay ito sa numero ng lokasyon array 1, at pagkatapos ay baguhin ang tuktok ng aming stack na array lokasyon bilang dalawang. Kaya kung ang mga susunod na panahon na gusto naming itulak ang isang elemento papunta sa stack, makikita ito ay ilagay sa array lokasyon 2. At gawin na isa pang beses ipaalam. Susubukan naming itulak 19 off ng stack. Susubukan naming ilagay 19 sa array lokasyon 2 at baguhin ang tuktok ng aming stack na array lokasyon 3 kaya kung ang mga susunod na oras namin kailangan upang gumawa ng push hindi namin handa na upang patakbuhin. 

OK, kaya na pagtulak sa maikling sabi. Ano ang tungkol sa pop? Kaya pop ay ang uri ng kamukhang-mukha sa panunulak. Ito ay kung paano namin tanggalin ang data mula sa stack. At sa pangkalahatan pangangailangan pop upang gawin ang mga sumusunod. Kailangan nito upang tanggapin ang isang pointer sa stack, muli sa pangkalahatang kaso. Sa ilang iba pang mga kaso maaari ka Aking ipinahayag ang mga stack globally, sa kaso na hindi mo na kailangan upang pumasa ito sa dahil ito ay mayroon ng access sa mga ito bilang isang global variable. Ngunit pagkatapos ay kung ano pa ang dapat nating gawin? Well kami ay incrementing sa itaas ng stack sa push, kaya marahil kami ay pagpunta sa gusto sa pagbawas sa itaas ng stack sa pop, i-right? At pagkatapos ng kurso din namin ay pagpunta sa nais upang ibalik ang halaga na alisin namin. Kung kami ay nagdadagdag ng mga elemento, gusto naming upang makakuha ng mga elemento out sa susunod, kami ay marahil talagang nais na iimbak ang mga ito kaya namin huwag tanggalin na lamang ang mga ito mula sa stack at pagkatapos ay wala sa kanila. Sa pangkalahatan, kung hindi kami pagtulak at pop dito gusto naming upang i-imbak ang impormasyon sa isang makahulugang paraan at upang hindi ito gumawa ng kahulugan upang itapon lamang ito. Kaya ang function na ito ay dapat na marahil nagbabalik ng halaga sa amin. 

Kaya ito ay kung ano ang isang deklarasyon para sa pop maaaring magmukhang doon sa itaas na kaliwang. Function na babalik na ito data ng halaga type. Muli nakaya naming gamit integer sa buong lugar. At ito ay tumatanggap ng isang pointer sa isang stack bilang sarili nitong argument o nag-iisang parameter. Kaya kung ano ang pop pagpunta sa gawin? Ipagpalagay natin na nais nating ngayon pop isang elemento off ng s. Kaya tandaan sinabi ko na stack ay huling in, first out, LIFO istruktura ng data. Aling elemento ay pagpunta sa ay aalisin mula sa stack? Hulaan mo ba 19? Dahil gusto mo ay tama. 19 ay ang huling elemento idinagdag namin sa stack kapag kami pagtulak ay elemento sa, at kaya ito ay pagpunta sa unang elemento na makakakuha ng tinanggal. Ito ay bilang kung sinabi namin 28, at pagkatapos ay inilalagay namin 33 sa tuktok ng ito, at ilalagay namin ang 19 sa tuktok ng na. Ang tanging sangkap na maaari naming mag-alis ay 19. 

Ngayon sa diagram dito kung ano ang nagawa ko ay isang uri ng mga tinanggal na 19 mula sa array. Iyan ay hindi tunay na kung ano ang namin ang pagpunta sa gawin. Kami ay pagpunta sa uri ng magpanggap na ito ay hindi doon. Ito ay pa rin doon sa na lokasyon sa memorya, ngunit lamang namin ang pagpunta upang huwag pansinin ito sa pamamagitan ng pagbabago sa tuktok ng aming stack mula sa pagiging 3 sa 2. Kaya kung kami ay sa ngayon itulak isa pang elemento papunta sa stack, ito ay higit sa 19 magsulat. 

Ngunit hindi na pumunta sa pamamagitan ng problema ipaalam ng pagtanggal ng 19 mula sa stack. Maaari lang namin magpanggap na ito ay hindi doon. Para sa mga layunin ng stack na ito ay wala na kung palitan namin tuktok na 2 sa halip ng 3. Lahat ng karapatan, kaya na ay medyo magkano ito. Iyon lang ang kailangan nating gawin mag-pop-off ang isang elemento. Gawin natin ito muli. Kaya nai-highlight ko ito sa red para ipahiwatig ginagawa namin ng isa pang tawag. Kami ay pagpunta sa gawin ang parehong bagay. 

Kaya kung ano ang nangyayari sa mangyayari? Well, kami ay pagpunta upang mag-imbak 33 in x at kami ay pagpunta upang baguhin ang tuktok ng stack sa 1. Kaya na kung kami ay upang itulak ang isang ngayon element sa stack na hindi namin pagpunta sa gawin sa ngayon, kung ano ang nangyayari sa mangyayari ay namin ang pagpunta overwrite array lokasyon number 1. Kaya na 33 na uri ng kaliwa sa likod na nagpanggap lang namin ay hindi doon ngayon, lang kami sa gumulpi ito at ilagay sa 40 doon sa halip. At pagkatapos ng kurso, dahil gumawa kami ng isang push, kami ay pagpunta sa pagdami ang mga tuktok ng stack mula 1 hanggang 2 upang kung namin magdagdag ngayon isa pang elemento idedetalye ito pumunta sa array lokasyon bilang dalawang. 

Ngayon na naka-link na listahan ay isa pang paraan upang ipatupad ang mga stack. At kung ito kahulugan sa dito mukhang pamilyar sa iyo screen, ito ay dahil ito ay mukhang halos eksaktong pareho, sa katunayan, ito ay medyo marami ay eksaktong parehong bilang isang isa-isa naka-link na listahan, kung isipin mo mula sa aming mga talakayan ng isa-isa mga listahan ng link sa isa pang video. Ang tanging mga paghihigpit dito ay para sa amin bilang mga programmer, hindi namin pinahihintulutan na ipasok o tanggalin sapalaran mula sa isa-isa listahan ng mga link kung saan maaari naming dati gawin. Maaari lamang kami ngayong ipasok at tanggalin ang mula sa sa harap o sa itaas ng mga naka-link listahan. Iyan ay talagang lamang pagkakaiba bagaman. Ito ay sa kabilang banda isang isa-isa naka-link na listahan. Ito ay lamang ang paghihigpit pagpapalit sa ating sarili bilang programmer na pagbabago ito sa isang stack. 

Ang rule dito ay ang palaging mapanatili ang isang pointer sa ulo ng isang naka-link na listahan. Ito ay siyempre isang karaniwang mahalagang tuntunin muna. Para isa-isa list na naka-link sa iyo pa rin kailangan lamang ng isang pointer sa ulo upang magkaroon ng na chain ma-refer sa bawat iba pang mga elemento sa naka-link na listahan. Ngunit ito ay lalo mahalaga sa isang stack. At kaya sa pangkalahatan ikaw pagpunta sa aktwal na nais ang pointer upang maging isang global variable. Marahil ito ay pagpunta sa magiging mas madali na paraan. Kaya ano ang mga analogs ng push at pop? Right. Kaya pagtulak muli ay pagdaragdag isang bagong sangkap sa stack. Sa isang naka-link na listahan ay nangangahulugan na kami ay pagpunta sa may upang lumikha ng isang bagong node na hindi namin pagpunta upang idagdag sa listahan ng mga link, at pagkatapos ay sundin ang mga maingat na hakbang na ibinalangkas namin dati sa isa-isa na naka-link na listahan upang idagdag ito sa ang mga kadena na walang paglabag sa kadena at pagkawala o orphaning anumang elemento ng naka-link na listahan. At na talaga kung ano na ang maliit na patak ng text doon nagbubuod. At ang isang pagtingin hayaan sa ito bilang isang diagram. 

Kaya narito ang aming listahan ng mga link. Ito Kasabay naglalaman ng apat na mga sangkap. At higit na ganap narito ang aming stack na naglalaman ng apat na mga sangkap. At sabihin natin na nais natin ngayon upang itulak ang isang bagong item na ito papunta sa stack. At gusto namin na itulak ang isang bagong item na ang halaga ng data ay 12. Well kung ano ang gagawin natin? Well unang kami ay pagpunta sa malloc espasyo, magilas maglaan ng espasyo para sa isang bagong node. At siyempre kaagad pagkatapos gumawa kami ng isang tawag sa malloc kami ay palaging siguraduhin na suriin para sa null, dahil kung nakuha namin ang null likod nagkaroon ng ilang mga uri ng problema. Hindi namin nais na dereference na null pointer o ikaw ay magdusa ng isang seg fault. Iyan ay hindi mabuti. Kaya mo malloced kami ng node. Kami ipalagay na nagkaroon kami tagumpay dito. Kami ay pagpunta sa ilagay ang 12 sa larangan data ng na node. Ngayon mo isipin kung alin sa aming mga payo gumagalaw susunod kaya hindi namin basagin ang kadena? Kami ay may isang pares ng mga pagpipilian dito ngunit ang isa lamang na ay magiging ligtas ay upang itakda ang mga balita susunod na pointer sa point sa lumang ulo ng listahan o kung ano ay malapit ang lumang ulo ng listahan. At ngayon na ang lahat ng aming elemento ay chained magkasama, maaari naming ilipat lamang list upang ituro sa parehong lugar na ang mga bagong ginagawa. At kami ay ngayong epektibong itinulak ng bagong sangkap papunta sa harap ng stack. 

Upang pop namin lamang ang nais na tanggalin na ang unang elemento. At kaya kung ano talaga kami ay may sa gawin dito, well kami ay upang mahanap ang pangalawang elemento. Sa kalaunan na ang magiging bagong tumuloy matapos naming tanggalin ang una. Kaya kailangan lang namin upang simulan mula sa sa simula, ilipat ang isa forward. Kapag namin nakuha ng isang hold sa isa forward ng kung saan kami ay kasalukuyang ay maaari naming tanggalin ang unang isa ligtas na at pagkatapos ay maaari naming ilipat lamang ang ulo upang tumuro sa kung ano ang ikalawang termino at pagkatapos ay ngayon ay ang unang matapos na node ay tinanggal na. 

Kaya muli, pagkuha ng isang pagtingin sa ito bilang isang diagram namin nais na ngayon pop isang element off ng mga ito stack. Kaya kung ano ang gagawin namin? Well unang kami ay pagpunta upang lumikha ng isang bagong pointer na pupuntahan upang ituro sa parehong lugar bilang pinuno. Kami ay pagpunta sa ilipat ito sa isang posisyon forward sa pamamagitan ng pagsasabi trav equals trav susunod na halimbawa, kung saan Gusto isulong ang isa trav pointer posisyon ng pasulong. Ngayon na mayroon ka namin ng isang hawakan ang unang elemento sa pamamagitan ng pointer na tinatawag na listahan, at ang pangalawang elemento sa pamamagitan ng isang pointer na tinatawag na trav, maaari naming ligtas na tanggalin ang unang elemento mula sa stack nang hindi nawawala ang mga natitirang ng chain dahil tayo magkaroon ng isang paraan upang sumangguni sa pangalawang elemento ipasa sa pamamagitan ng paraan ng tinatawag trav pointer. 

Kaya ngayon maaari naming magbakante na node. Maaari naming magbakante listahan. At pagkatapos ang lahat ng kailangan naming gawin ngayon ay ilipat ang listahan upang point sa parehong lugar na trav ang ginagawa, at hindi namin uri ng likod kung saan kami nagsimula bago namin itinulak 12 on sa unang lugar, right. Ito ay eksakto kung saan namin. Kami ay nagkaroon ng ito stack ng apat na elemento. Nagdagdag kami ng isang ikalima. Itinulak namin ang ikalimang element sa, at pagkatapos namin pop na pinaka-kamakailan dagdag na sangkap back off. 

Iyan ay talagang medyo marami lahat ng may sa stack. Maaari mong ipatupad ang mga ito bilang mga array. Maaari mong ipatupad ang mga ito bilang mga listahan ng link. May, siyempre, iba pang mga paraan upang ipatupad ang mga ito pati na rin. Talaga ang dahilan gusto naming gamitin stack ay upang mapanatili ang data sa paraan na ang pinaka-kamakailang idinagdag sangkap ay ang unang bagay na hindi namin pagpunta sa nais na makabalik. Ako Doug Lloyd, ito ay cs50.