DOUG LLOYD: zote haki, hivyo kwa hatua hii uko pengine pretty ukoo na arrays na orodha wanaohusishwa ambayo ni ya msingi mbili miundo data tumekuwa kuongelea kwa ajili ya kuweka seti ya data ya aina hiyo data kupangwa. Sasa sisi ni kwenda kuzungumza juu ya wanandoa wa tofauti juu ya arrays na orodha wanaohusishwa. Katika video hii tunakwenda kuzungumzia mwingi. Hasa sisi ni kwenda kuzungumza kuhusu muundo data kuitwa stack. Kumbuka kutoka mijadala iliyopita kuhusu kuyatumia na kumbukumbu, kuwa stack pia ni jina kwa sehemu ya kumbukumbu ambapo statically alitangaza memory-- kumbukumbu kwamba wewe jina, vigezo kwamba wewe jina, et kadhalika na kazi muafaka na sisi pia muafaka wito mkusanyiko kuwepo. Hivyo hii ni muundo wa mkusanyiko data si stack sehemu ya kumbukumbu. SAWA. 

Lakini ni nini stack? Hivyo ni pretty much tu aina maalum ya muundo wa kwamba inao data katika njia kupangwa. Na kuna mawili sana njia ya kawaida ya kutekeleza mwingi kwa kutumia miundo mbili data kuwa tuko tayari ukoo na, arrays na orodha wanaohusishwa. Kinachofanya mkusanyiko maalum ni njia ambayo sisi kuweka taarifa kwenye mkusanyiko, na njia ya sisi kuondoa habari kutoka stack. Hasa na mwingi utawala ni tu zaidi hivi karibuni aliongeza kipengele inaweza kuondolewa. 

Hivyo kufikiri juu yake kana kwamba ni stack. Sisi ni piling taarifa juu ya yenyewe, na tu kitu juu ya rundo inaweza kuondolewa. Hatuwezi kuondoa kitu chini kwa sababu kila kitu kingine ingekuwa kuanguka na kuanguka juu. Hivyo sisi kweli ni kujenga stack kwamba sisi kisha una kuondoa kipande kwa kipande. Kwa sababu hiyo sisi kawaida rejea kwa stack kama muundo LIFO, mwisho katika, nje ya kwanza. LIFO, mwisho katika, kwanza nje. 

Hivyo kwa sababu ya kizuizi juu ya hii jinsi habari unaweza kuongezwa kwa na kuondolewa kutoka stack, kuna kweli mambo mawili tu tunaweza kufanya na stack. Tunaweza kushinikiza, ambayo ni mrefu sisi kutumia kwa ajili ya kuongeza kipengele mpya juu ya stack, au kama stack haipo na sisi ni kujenga ni kutoka mwanzo, kujenga stack katika nafasi ya kwanza itakuwa kusukuma. Na kisha pop, hiyo ni aina ya CS mrefu sisi kutumia ili kuondoa hivi karibuni aliongeza kipengele kutoka juu ya stack. 

Hivyo sisi ni kwenda kuangalia wote utekelezaji, wote safu msingi na orodha wanaohusishwa msingi. Na tunakwenda kuanza na safu ya msingi. Hivyo hapa ni wazo la msingi la nini safu msingi muundo stack data bila kuangalia kama. Tuna typed ufafanuzi hapa. Ndani ya kwamba tuna wanachama wawili au mashamba ya muundo. Tuna safu. Na tena mimi nina kutumia holela aina data thamani. 

Hivyo hii inaweza kuwa aina yoyote data, int char au baadhi ya data mengine aina wewe hapo awali kuundwa. Hivyo tuna safu ya ukubwa uwezo. Uwezo kuwa pauni inavyoelezwa mara kwa mara, labda mahali pengine katika faili wetu. Hivyo taarifa tayari kwa hii hasa utekelezaji sisi ni bounding wenyewe kama alikuwa kawaida kesi na arrays, ambayo hatuwezi dynamically resize, ambapo kuna idadi fulani ya mambo ya kiwango cha juu kwamba tunaweza kuweka katika stack yetu. Katika kesi hiyo ni mambo uwezo. 

Sisi pia kuweka wimbo wa juu ya stack. Nini kipengele ni zaidi hivi karibuni aliongeza kwa stack? Na hivyo sisi kuweka wimbo wa kwamba katika variable kuitwa juu. Na hii yote anapata ilimalizika pamoja ndani ya mwezi aina data aitwaye stack. Na mara moja sisi ni umba hii aina mpya data tunaweza kutibu kama Aina ya data nyingine yoyote. Tunaweza kutangaza stack s, kama vile tunaweza kufanya int x, au char y. Na wakati sisi kusema stack s, pamoja kile kinachotokea ni sisi kupata seti ya kumbukumbu zilizotengwa kwa ajili yetu. 

Katika uwezo huu kesi Nimekuwa inaonekana aliamua ni 10 kwa sababu mimi nimepata kutofautiana moja ya aina stack ambayo ina mashamba mawili kukumbuka. Safu, katika kesi hii ni kwenda kuwa safu ya integers kama ilivyo katika maeneo mengi ya mifano yangu. Na mwingine kutofautiana integer uwezo wa kuhifadhi juu, hivi karibuni aliongeza kipengele kwa stack. Hivyo moja mkusanyiko wa kile sisi tu kuelezwa inaonekana kama hii. Ni sanduku zenye safu ya 10 nini itakuwa integers katika kesi hii na mwingine kutofautiana integer huko katika kijani zinaonyesha juu ya stack. 

Kuweka juu ya stack sisi tu kusema s.top. Hiyo ni jinsi sisi kupata uwanja wa muundo kukumbuka. s.top sawa na 0 ufanisi gani hii kwa stack yetu. Hivyo tena tuna shughuli mbili tuweze kufanya sasa. Tunaweza kushinikiza na tunaweza pop. Hebu kuanza na kushinikiza. Tena, kusukuma ni kuongeza mpya kipengele juu ya stack. 

Basi je, tunahitaji kufanya katika hii safu ya utekelezaji msingi? Vizuri kwa ujumla the kushinikiza kazi ni kwenda haja ya kukubali pointer kwa stack. Sasa kuchukua pili na kufikiri juu yake. Kwa nini tunataka kukubali pointer stack? Kumbuka kutoka video ya awali juu ya wigo kutofautiana na kuyatumia, nini kitatokea kama sisi tu alimtuma stack, s badala katika kama parameter? Nini ingekuwa kweli kuwa kupita katika huko? Kumbuka sisi ni kujenga nakala wakati sisi kupita kwa kazi isipokuwa sisi kutumia kuyatumia. Na hivyo kazi hii kushinikiza mahitaji kukubali pointer mkusanyiko ili sisi ni kweli kubadilisha stack sisi nia ya kubadilika. 

Wengine jambo kushinikiza pengine anataka kukubali ni data kipengele cha aina thamani. Katika kesi hiyo, tena, integer kwamba tunakwenda kuongeza hadi juu ya stack. Hivyo sisi tumepewa vigezo zetu mbili. Je, ni sisi kwenda sasa kufanya ndani ya kushinikiza? Naam, tu, sisi ni kwenda tu kuongeza kwamba kipengele juu ya stack na kisha kubadili ambapo juu ya stack ni, kwamba s dot thamani ya juu. Hivyo hii ni nini kazi Tamko kwa kushinikiza ili kuangalia kama katika safu makao utekelezaji. 

Tena hii si utawala ngumu na ya haraka kwamba unaweza kubadili hali hii na kuwa na ni kutofautiana katika njia tofauti. Labda s ni alitangaza kimataifa. Na hivyo huna hata haja kupita ni kama parameter. Hii ni mara ya pili tu ujumla kesi kwa kushinikiza. Na kuna tofauti njia za kutekeleza. Lakini katika kesi hii yetu kushinikiza ni kwenda kuchukua hoja mbili, pointer mkusanyiko na data kipengele cha aina thamani, integer kwa kesi hii. 

Hivyo sisi alitangaza s, sisi Alisema s.top sawa na 0. Sasa hebu kushinikiza idadi 28 kwenye stack. Vizuri nini maana gani? Naam sasa juu ya stack ni 0. Na hivyo kile kimsingi kinaenda kutokea ni tunakwenda fimbo idadi 28 katika safu eneo 0. Pretty moja kwa moja, kulia, na hivyo Ilikuwa juu na sasa sisi ni vizuri kwenda. Na kisha sisi haja ya kubadili kile juu ya stack itakuwa. Hivyo kwamba wakati mwingine sisi kushinikiza kipengele katika, tunakwenda kuhifadhi katika safu eneo, pengine si 0. Hatutaki overwrite nini sisi tu ya kuweka huko. Na hivyo tutaweza tu hoja juu ya 1. Kwamba pengine hufanya akili. 

Sasa kama tunataka kuweka kipengele mwingine kwenye stack, wanasema tunataka kushinikiza 33, vizuri sasa sisi ni kwenda tu kuchukua 33 na kuiweka katika safu eneo idadi 1, na kisha kubadili juu ya yetu stack kuwa safu eneo namba mbili. Hivyo kama wakati mwingine tunataka kushinikiza kipengele kwenye stack, kutakuwa na kuwekwa katika safu eneo 2. Na hebu kufanya hivyo mara moja zaidi. Tutaweza kushinikiza 19 mbali ya mwingi. Tutaweza kuweka 19 katika safu eneo 2 na mabadiliko juu ya stack yetu kuwa safu eneo 3 hivyo kama ijayo wakati sisi haja ya kufanya kushinikiza sisi ni vizuri kwenda. 

OK, hivyo hiyo ni kusukuma kwa kifupi. Je kuhusu yanajitokeza? Hivyo popping ni aina ya mwenzake kwa kusukuma. Ni jinsi gani sisi kuondoa data kutoka stack. Na katika mahitaji ujumla pop kufanya yafuatayo. Inahitaji kukubali pointer stack, tena katika kesi ujumla. Katika baadhi ya kesi nyingine waweza wametangaza stack kimataifa, katika kesi ambayo huna haja ya kupita katika sababu tayari ina huduma hiyo kama variable kimataifa. Lakini basi kile kingine tunahitaji kufanya nini? Vizuri tulikuwa incrementing juu ya stack katika kushinikiza, hivyo sisi ni pengine atataka kwa pungufu juu ya stack katika pop, sawa? Na kisha bila shaka sisi ni pia atataka kurudi thamani kwamba sisi kuondoa. Kama sisi ni kuongeza vipengele, tunataka kupata mambo nje baadaye, sisi pengine kwa kweli unataka kuhifadhi yao ili sisi si tu kufuta yao kutoka stack na kisha kufanya chochote pamoja nao. Kwa ujumla kama tuko kusukuma na popping hapa tunataka kuhifadhi hii Maelezo kwa njia ya maana na hivyo hana kufanya maana tu kuondokana na hilo. Hivyo kazi hii lazima pengine kurudi thamani kwetu. 

Hivyo hii ni nini tamko kwa pop ili kuangalia kama kuna juu kushoto. Hii anarudi kazi data ya aina thamani. Tena tumekuwa kutumia integers hela. Na anapokea pointer mkusanyiko kama pekee hoja yake au vigezo pekee. Kwa hiyo kile ni pop kwenda kufanya? Hebu sema tunataka sasa pop kipengele mbali ya s. Basi kumbuka mimi alisema kuwa mwingi ni mwisho katika, kwanza nje, LIFO data miundo. Ambayo kipengele ni kwenda kuondolewa kutoka mkusanyiko? Je, nadhani 19? Kwa sababu wewe d kuwa na haki. 19 Ilikuwa kipengele mwisho sisi aliongeza kwa stack tulipokuwa kusukuma mambo juu, na hivyo ni kwenda kwanza kipengele kwamba anapata kuondolewa. Ni kama tulivyosema 28, na kisha sisi kuweka 33 juu yake, na sisi kuweka 19 juu ya kwamba. Kipengele tu tunaweza kuchukua mbali ni 19. 

Sasa katika mchoro hapa kile nimepata kufanyika ni aina ya kufutwa 19 kutoka safu. Hiyo ni kweli nini tunakwenda kufanya. Tunakwenda tu aina ya kujifanya si huko. Bado kuna katika kwamba kumbukumbu eneo, lakini sisi ni kwenda tu kupuuza kwa kubadilisha juu ya stack yetu asiwe 3-2. Hivyo kama tulikuwa sasa kushinikiza kipengele kingine kwenye stack, ingekuwa juu ya kuandika 19. 

Lakini hebu kwenda kwa njia ya shida ya kufuta 19 kutoka stack. Tunaweza kujifanya tu siyo huko. Kwa madhumuni ya mkusanyiko ni gone ikiwa sisi kubadili juu ya kuwa 2 badala ya 3. Haki wote, ili kwamba ilikuwa pretty kiasi. Hayo ni yote tunahitaji kufanya pop kipengele mbali. Hebu kufanya hivyo tena. Hivyo nimekuwa yalionyesha katika nyekundu hapa zinaonyesha sisi ni kufanya wito mwingine. Tunakwenda kufanya kitu kimoja. 

Basi nini kitatokea? Naam, sisi ni kwenda kuhifadhi 33 katika x na tunakwenda kubadili juu ya stack kwa 1. Hivyo kwamba kama tulikuwa sasa kushinikiza kipengele kwenye mkusanyiko ambayo tuko kwenda kufanya hivi sasa, nini kitatokea ni tunakwenda overwrite safu eneo namba 1. Hivyo kwamba 33 ni aina ya kushoto nyuma ya kwamba sisi tu akadai si huko tena, tunakwenda tu kwa clobber yake na kuweka 40 huko badala yake. Na kisha bila shaka, tangu tukiwa kushinikiza, tunakwenda increment juu ya stack 1-2 ili kwamba kama sisi sasa kuongeza kipengele mwingine ni itabidi kwenda katika safu eneo namba mbili. 

Sasa orodha wanaohusishwa ni mwingine njia ya kutekeleza mwingi. Na kama ufafanuzi juu ya hii screen hapa inaonekana ukoo na wewe, ni kwa sababu inaonekana karibu sawa, kwa kweli, ni pretty much ni hasa sawa na orodha moja moja wanaohusishwa, kama unakumbuka kutoka mjadala wetu wa moja moja wanaohusishwa orodha katika video nyingine. Kizuizi tu hapa ni kwa ajili yetu kama programmers, sisi ni haruhusiwi kuingiza au kufuta nasibu kutoka orodha moja moja wanaohusishwa ambayo tunaweza awali kufanya. Tunaweza tu sasa kuingiza na kufuta kutoka mbele au juu ya wanaohusishwa orodha. Hiyo ni kweli tu tofauti ingawa. Hii ni vinginevyo orodha moja moja wanaohusishwa. Ni tu kizuizi kuchukua nafasi ya juu ya sisi wenyewe kama programmers kwamba mabadiliko hayo kwenye mkusanyiko. 

Utawala hapa ni daima kudumisha pointer na mkuu wa orodha wanaohusishwa. Bila shaka hii ni kwa ujumla utawala muhimu kwanza. Kwa moja moja wanaohusishwa orodha anyway wewe tu haja pointer kichwa ili kuwa na kwamba mlolongo kuwa na uwezo wa kutaja kwa kila kipengele nyingine katika orodha wanaohusishwa. Lakini ni hasa muhimu kwa stack. Na hivyo kwa ujumla uko kwenda kwa kweli wanataka pointer hii kuwa kutofautiana kimataifa. Ni pengine kwenda kuwa hata rahisi kwa njia hiyo. Hivyo milinganisho ya kushinikiza na pop ni nini? Kulia. Hivyo kusukuma tena ni kuongeza kipengele mpya ya stack. Katika orodha wanaohusishwa kwamba ina maana tunakwenda na kujenga nodi mpya kwamba sisi ni kwenda kuongeza katika orodha wanaohusishwa, na kisha kufuata hatua makini kwamba tumekuwa ilivyoainishwa hapo awali katika orodha moja moja wanaohusishwa na kuongeza kuwa kwa mlolongo bila kuvunja mlolongo na kupoteza au orphaning yoyote mambo ya orodha wanaohusishwa. Na kwamba kimsingi nini kwamba Blob kidogo ya maandishi huko muhtasari. Na hebu tuangalie saa hiyo kama kielelezo. 

Hivyo hapa ni orodha yetu wanaohusishwa. Ni Sanjari ina mambo manne. Na kwa usahihi zaidi hapa ni wetu stack zenye mambo manne. Na hebu sema sisi sasa wanataka kushinikiza bidhaa mpya kwenye stack hii. Na tunataka kushinikiza mpya bidhaa ambazo data thamani ya 12. Vizuri nini sisi kwenda kufanya? Vizuri kwanza tunakwenda malloc nafasi, dynamically kutenga nafasi kwa nodi mpya. Na bila shaka mara baada ya sisi kufanya wito malloc sisi daima kuhakikisha kuangalia kwa null, kwa sababu kama tulipata null nyuma kulikuwa na aina fulani ya tatizo. Hatutaki dereference kwamba null pointer au utakuwa kuteseka seg kosa. Hiyo si nzuri. Hivyo tumekuwa malloced ya nodi. Tutaweza kudhani tumekuwa na mafanikio hapa. Sisi ni kwenda kuweka katika 12 uwanja wa nodi data. Sasa je, unakumbuka ambayo ya kuyatumia yetu hatua ijayo hivyo hatuna kuvunja minyororo? Sisi kuwa wanandoa wa chaguzi hapa lakini moja tu kwamba kinaendelea kuwa salama ni kuweka habari ijayo pointer hatua kwa kichwa wa zamani wa orodha au nini hivi karibuni kuwa umri wa mkuu wa orodha. Na sasa kwamba wote wa wetu mambo ni minyororo pamoja, tunaweza tu hoja orodha kwa uhakika kwenye sehemu moja kwamba mwezi gani. Na sisi sasa kwa ufanisi kusukuma kipengele mpya kwenye mbele ya stack. 

Pop sisi nataka tu kufuta kwamba kipengele kwanza. Na hivyo kimsingi nini tuna kufanya hapa, vizuri inabidi kutafuta kipengele cha pili. Hatimaye ambayo yamekuwa mapya kichwa baada ya sisi kufuta moja ya kwanza. Hivyo sisi tu haja ya kuanza kutoka mwanzo, kusonga mbele moja. Mara sisi tumepewa uwezo juu moja mbele ya ambapo sisi sasa ni tunaweza kufuta moja kwanza salama na kisha tunaweza tu hoja kichwa kwa uhakika na kile ilikuwa awamu ya pili na kisha sasa ni ya kwanza baada ya kuwa nodi umefutwa. 

Hivyo tena, kuchukua kuangalia saa hiyo kama mchoro sisi wanataka sasa pop kipengele mbali ya stack hii. Hivyo tunafanya nini? Naam sisi ni kwanza kwenda kujenga pointer mpya ambayo inaenda kwa uhakika na doa sawa na kichwa. Tunakwenda hoja hiyo nafasi moja mbele kwa kusema trav sawa Trav ijayo kwa mfano, ambayo ingekuwa mapema trav pointer moja nafasi mbele. Sasa kwa kuwa sisi tumepewa kushikilia kitu cha kwanza kupitia pointer iitwayo orodha, na kipengele cha pili kupitia pointer iitwayo trav, tunaweza kwa usalama kufuta kwamba kitu cha kwanza kutoka mkusanyiko bila ya kupoteza wengine ya mlolongo sababu sisi kuwa na njia kwa kutaja kwa kipengele cha pili mbele kwa njia ya pointer iitwayo trav. 

Hivyo sasa tunaweza bure kwamba nodi. Tunaweza bure orodha. Na kisha wote tunahitaji kufanya sasa ni hoja ya orodha kwa uhakika kwenye sehemu moja kwamba trav gani, na tuko aina ya nyuma ambapo sisi kuanza kabla ya sisi kusukuma 12 juu ya katika nafasi ya kwanza, haki. Hii ni hasa ambapo tulikuwa. Tulikuwa na hii stack nne kipengele. Sisi aliongeza tano. Sisi kusukuma tano kipengele juu, na kisha sisi popped kwamba hivi karibuni aliongeza kipengele nyuma mbali. 

Hiyo ni kweli pretty much yote kuna mwingi. Unaweza kutekeleza yao kama arrays. Unaweza kutekeleza yao kama orodha wanaohusishwa. Kuna, bila shaka, wengine njia za kutekeleza yao pia. Kimsingi sababu tunataka kutumia mwingi ni kudumisha data kwa namna kwamba hivi karibuni aliongeza kipengele ni jambo la kwanza tuko atataka kupata nyuma. Mimi nina Doug Lloyd, hii ni cs50.