DOUG LLOYD: pob hawl, hynny gan y pwynt hwn eich bod yn yn ôl pob tebyg yn eithaf cyfarwydd gyda araeau a rhestrau cysylltiedig sef y ddau brif strwythurau data rydym wedi yn siarad am ar gyfer cadw setiau o data o fathau data tebyg a drefnwyd. Nawr rydym yn mynd i siarad am un neu ddau o amrywiadau ar araeau a rhestrau cysylltiedig. Yn y fideo hwn rydym yn mynd i siarad am staciau. Yn benodol rydym yn mynd i siarad am strwythur data o'r enw pentwr. Dwyn i gof o drafodaethau blaenorol am awgrymiadau a chof, bod y pentwr hefyd yn enwi ar gyfer segment o gof lle ddatgan llonydd cof memory-- eich bod enw, newidynnau eich bod yn enw, et fframiau cetera a swyddogaeth yr ydym hefyd fframiau stac alwad yn bodoli. Felly, mae hwn yn strwythur data pentwr Nid yw segment pentwr o gof. IAWN. 

Ond beth yw pentwr? Felly mae'n 'n bert lawer dim ond fath arbennig o strwythur sy'n cynnal data mewn ffordd drefnus. Ac mae dau iawn ffyrdd cyffredin i weithredu staciau ddefnyddio dau strwythurau data ein bod eisoes yn gyfarwydd â nhw, araeau a rhestrau cysylltiedig. Beth sy'n gwneud pentwr arbennig yw'r ffordd y byddwn yn rhoi gwybodaeth i mewn i'r pentwr, a'r ffordd yr ydym tynnu gwybodaeth o'r pentwr. Yn benodol gyda chyrn y rheol dim ond y mwyaf Gall elfen ychwanegu cael ei symud yn ddiweddar. 

Felly meddyliwch am y peth fel pe ei fod yn pentwr. Rydym yn pentyrru gwybodaeth ar ben ei hun, a dim ond y peth ar y brig Gall y pentwr yn cael ei ddileu. Ni allwn gael gwared ar y peth oddi tano gan y byddai popeth arall cwympo ac yn disgyn drosodd. Felly, rydym yn wir yn adeiladu pentwr sy'n Yna, mae'n rhaid i ni gael gwared fesul darn. Oherwydd hyn, rydym yn aml yn cyfeirio i stac fel strwythur LIFO, olaf i mewn, cyntaf allan. LIFO, bara i mewn, cyntaf allan. 

Felly, oherwydd y cyfyngiad hwn ar sut y gellir wybodaeth yn cael ei ychwanegu at a'i symud o'r pentwr, mae 'n sylweddol Dim ond dau beth y gallwn ei wneud gyda pentwr. Gallwn gwthio, sef y term a ddefnyddiwn ar gyfer ychwanegu elfen newydd i frig y simnai, neu os nad yw'r pentwr yn bodoli ac rydym yn ei greu o'r newydd, gan greu y das yn y lle cyntaf fyddai gwthio. Ac yna pop, dyna'r math o CS term a ddefnyddiwn i gael gwared ar y rhan fwyaf diweddar Elfen ychwanegol o ben y pentwr. 

Felly rydym yn mynd i edrych ar y ddau gweithrediadau, yn seiliedig ddau arae ac yn seiliedig rhestr gysylltiedig. Ac rydym yn mynd i yn dechrau gyda seiliedig ar amrywiaeth. Felly dyma y syniad sylfaenol o beth y strwythur data stac seiliedig amrywiaeth Byddai edrych. Mae gennym ddiffiniad deipio yma. Y tu mewn o fod gennym ddau aelod neu feysydd y strwythur. Mae gennym amrywiaeth. Ac eto, Im 'yn arfer y Gwerth math data mympwyol. 

Felly gallai hyn fod yn unrhyw fath o ddata, torgoch int neu ryw ddata arall teipiwch chi greu flaenorol. Felly mae gennym amrywiaeth o gapasiti maint. Capasiti yn cael ei ddiffinio punt cyson, efallai rhywle arall yn ein ffeil. Felly, yn sylwi eisoes gyda hyn arbennig gweithredu yr ydym yn ffinio ein hunain fel yr oedd yn nodweddiadol yr achos gyda arrays, na allwn ddynamig newid maint, lle mae 'na nifer penodol o elfennau uchafswm y gallwn roi yn ein pentwr. Yn yr achos hwn, mae'n elfennau capasiti. 

Rydym hefyd yn cadw golwg ar ben y pentwr. Pa elfen yw'r mwyaf Ychwanegwyd yn ddiweddar at y pentwr? Ac felly rydym yn cadw golwg ar y mewn newidyn a elwir top. Ac mae hyn i gyd yn cael ei lapio fyny at ei gilydd i mewn i fath ddata newydd o'r enw pentwr. Ac unwaith rydym yn ei greu y math data newydd gallwn ei drin fel unrhyw fath ddata arall. Gallwn ddatgan stac s, yn union fel gallem ei wneud int x, neu torgoch y. A phan fyddwn yn dweud stac s, yn dda beth sy'n digwydd yn ein bod yn cael set o cof a neilltuwyd ar ein cyfer. 

Yn yr achos hwn cynhwysedd Rwyf wedi penderfynu yn ôl pob golwg yw 10 oherwydd gen i sengl newidyn o'r math stac sy'n cynnwys dau gae yn cofio. Amrywiaeth, yn yr achos hwn yn mynd i fod amrywiaeth o gyfanrifau fel sy'n wir yn y rhan fwyaf o fy enghreifftiau. Ac amrywiol cyfanrif arall gallu storio y brig, yr ychwanegwyd fwyaf diweddar elfen i'r pentwr. Felly, un sengl pentwr o hyn yr ydym dim ond yn edrych fel hyn diffiniedig. Mae'n blwch sy'n cynnwys amrywiaeth o 10 beth Bydd yn cyfanrifau yn yr achos hwn ac newidyn cyfanrif arall yno yn wyrdd i ddangos ben y pentwr. 

Gosod ben y pentwr rydym yn unig yn dweud s.top. Dyna sut yr ydym yn cael mynediad i maes adalw strwythur. s.top yn dychwelyd 0 yn effeithiol yn gwneud hyn at ein corn. Felly, unwaith eto mae gennym ddau gweithrediadau ein bod yn gallu perfformio yn awr. Gallwn gwthio a gallwn pop. Gadewch i ni ddechrau gyda gwthio. Unwaith eto, gwthio yn ychwanegu newydd elfen i ben y pentwr. 

Felly beth sydd angen i ni ei wneud yn gweithredu sy'n seiliedig ar amrywiaeth hon? Yn dda yn y gyffredinol swyddogaeth gwthio yn mynd y bydd angen i dderbyn Pointer i'r pentwr. Nawr yn cymryd eiliad ac yn meddwl am y peth. Pam y byddai rydym am dderbyn pwyntydd i'r pentwr? Dwyn i gof o fideos blaenorol ar cwmpas ac awgrymiadau amrywiol, beth fyddai'n digwydd os ydym yn unig a anfonwyd stac, s yn hytrach mewn fel paramedr? Beth fyddai mewn gwirionedd yn cael ei basio i mewn 'na? Cofiwch ein bod yn creu copi pan fyddwn yn ei throsglwyddo i swyddogaeth oni bai ein bod yn defnyddio awgrymiadau. Ac felly swyddogaeth hon gwthio anghenion i dderbyn pwyntydd i'r pentwr fel ein bod yn yn newid mewn gwirionedd y pentwr rydym yn bwriadu newid. 

Mae'n debyg bod y gwthio peth arall eisiau derbyn yn elfen data o werth fath. Yn yr achos hwn, unwaith eto, yn gyfanrif sy'n rydyn ni'n mynd i ychwanegu at y ben y pentwr. Felly, mae gennym ni ein dau paramedrau. Beth ydym yn mynd i bellach yn ei wneud tu mewn gwthio? Wel, yn syml, rydym yn jyst yn mynd i ychwanegu yr elfen honno i ben y pentwr ac yna newid ble ben y pentwr yw, ei fod ef dot gwerth uchaf. Felly, mae hyn yn beth yn swyddogaeth datganiad ar gyfer gwthio Gallai edrych fel mewn yn seiliedig ar amrywiaeth-waith. 

Unwaith eto, nid yw hyn yn rheol caled a chyflym y gallech newid hyn ac yn cael yn amrywio mewn gwahanol ffyrdd. Efallai s yn cael ei ddatgan yn fyd-eang. Ac felly peidiwch â hyd yn oed angen i chi i basio ei fod fel baramedr. Mae hyn eto yn unig achos cyffredinol ar gyfer gwthio. Ac mae gwahanol ffyrdd o weithredu. Ond yn yr achos hwn mae ein gwthio yn mynd i gymryd dwy ddadl, pwyntydd i stac a elfen data o werth math, cyfanrif yn yr achos hwn. 

Felly, rydym yn datgan s, rydym yn Dywedodd s.top yn dychwelyd 0. Nawr, gadewch i wthio'r rhif 28 ar y pentwr. Wel beth mae hynny'n ei olygu? Wel ar hyn o bryd y ben y pentwr yw 0. Ac felly beth yn y bôn mynd i ddigwydd yw rydyn ni'n mynd i gadw nifer 28 i mewn i leoliad array 0. Pretty syml, dde, bod Roedd y brig ac yn awr rydym yn dda i fynd. Ac yna mae angen i ni newid yr hyn Bydd ben y pentwr fod. Fel bod y tro nesaf rydym yn gwthio elfen mewn, rydym yn mynd i storio mewn Lleoliad array, yn ôl pob tebyg nid 0. Nid ydym am ei throsysgrifo hyn yr ydym newydd ei roi yno. Ac felly byddwn dim ond symud y top i 1. Yn ôl pob tebyg sy'n gwneud synnwyr. 

Nawr, os ydym am roi elfen arall ar y pentwr, yn dweud ein bod am wthio 33, yn dda erbyn hyn rydym yn jyst yn mynd i gymryd 33 ac yn ei roi yn y array rhif Lleoliad 1, ac yna newid frig ein stacio i fod yn array rhif leoliad dau. Felly, os y tro nesaf rydym am gwthio elfen ar y pentwr, bydd yn cael ei roi yn amrywiaeth lleoliad 2. A gadewch i ni wneud hynny un mwy o amser. Byddwn yn gwthio 19 i ffwrdd o'r cyrn. Byddwn yn rhoi 19 mewn amrywiaeth lleoliad 2 a newid y frig ein pentwr i fod yn array lleoliad 3 felly os y byddwn yn y tro nesaf angen i ni wneud gwthio rydym yn dda i fynd. 

Iawn, felly mae hynny'n gwthio yn gryno. Beth am popping? Felly popping yw'r math o cyfatebol i wthio. Mae'n sut yr ydym yn tynnu data o'r pentwr. Ac yn anghenion pop gyffredinol i wneud y canlynol. Mae angen iddo dderbyn pwyntydd i'r stac, eto yn yr achos cyffredinol. Mewn rhai achosion eraill yr ydych efallai wedi datgan y pentwr yn fyd-eang, ac yn yr achos nad oes angen i chi basio yn oherwydd bod ganddo fynediad iddo eisoes fel newidyn byd-eang. Ond yna beth arall y mae angen inni ei wneud? Wel oeddem yn incrementing ben y pentwr yn gwthio, felly rydym yn fwy na thebyg yn mynd i eisiau i lleihau a ben y pentwr mewn pop, dde? Ac yna, wrth gwrs, rydym hefyd yn mynd i eisiau i ddychwelyd y gwerth yr ydym yn cael gwared. Os byddwn yn ychwanegu elfennau, rydym am i gael elfennau allan yn nes ymlaen, mae'n debyg ein bod mewn gwirionedd yn awyddus i'w storio er mwyn i ni peidiwch â dim ond eu dileu o'r stacio ac yna gwneud dim gyda nhw. Yn gyffredinol os ydym gwthio a popping yma rydym am i storio hwn gwybodaeth mewn ffordd ystyrlon ac felly nid yw'n gwneud synnwyr i ddim ond taflu iddo. Felly, dylai swyddogaeth hon yn ôl pob tebyg yn dychwelyd gwerth i ni. 

Felly, mae hyn yn beth datganiad am pop Gallai edrych fel yno ar y brig chwith. Mae'r swyddogaeth hon yn dychwelyd data o werth fath. Unwaith eto, rydym wedi bod yn defnyddio cyfanrifau drwyddi draw. Ac mae'n derbyn pwyntydd i'r stac fel ei unig ddadl neu unig paramedr. Felly, yr hyn sy'n pop mynd i'w wneud? Lets 'ddeud rydym am nawr pop elfen oddi ar s. Felly cofiwch dywedais y pentyrrau yn olaf i mewn,, strwythurau data LIFO cyntaf allan. Pa elfen yn mynd i gael ei ddileu o'r pentwr? A wnaethoch chi ddyfalu 19? Oherwydd byddech yn gywir. 19 oedd yr elfen olaf yr ydym yn ychwanegu at y stacio pan oeddem yn gwthio elfennau ar, ac felly mae'n mynd i'r cyntaf elfen sy'n cael ei dynnu. Mae fel pe baem dywedodd 28, a Yna, rydym yn rhoi 33 ar ei ben, ac rydym yn rhoi 19 ar ben hynny. Yr unig elfen y gallwn eu cymryd i ffwrdd yn 19. 

Nawr yn y diagram yma yr hyn yr wyf wedi ei wneud yn fath o ddileu 19 o'r rhesi. Nid yw hyn yn mewn gwirionedd yr hyn yr ydym yn mynd i'w wneud. Rydym yn jyst yn mynd i fath o esgus nad yw yno. Mae'n dal i fod yno yn y lleoliad hwnnw cof, ond rydym yn jyst yn mynd i anwybyddu drwy newid frig ein pentwr o fod yn 3-2. Felly, pe baem yn gwthio yn awr Elfen arall ar y pentwr, byddai'n ysgrifennu dros 19 oed. 

Ond gadewch i ni fynd drwy'r drafferth o ddileu 19 o'r pentwr. Allwn esgus nad yw yno. At ddibenion y pentwr mae'n mynd os byddwn yn newid y top i fod yn 2 yn lle 3. Mae pob hawl, felly, yr oedd 'n bert lawer iddo. Dyna'r cyfan sydd angen ei wneud i pop elfen ffwrdd. Gadewch i ni wneud hynny eto. Felly, rwyf wedi tynnu sylw at ei mewn coch yma yn dangos ein bod yn gwneud galwad arall. Rydym yn mynd i wneud yr un peth. 

Felly beth sy'n mynd i ddigwydd? Wel, rydym yn mynd i storio 33 yn x ac rydym yn mynd i newid ben y pentwr i 1. Felly os ydym yn awr i wthio i elfen i mewn i'r pentwr yr ydym ni'n mynd i'w wneud ar hyn o bryd, beth sy'n mynd i ddigwydd yn rydym yn mynd Ysgrifennu dros amrywiaeth rhif leoliad 1. Fel bod 33 a oedd fath o chwith y tu ôl i hynny rydym yn unig esgus yw nad oes anymore, rydym yn jyst yn mynd i trosysgrifo'r a'i roi 40 yno yn lle hynny. Ac yna, wrth gwrs, ers i ni wneud ymdrech, rydyn ni'n mynd i gynyddiad y ben y pentwr 1-2 felly os ydym yn awr yn ychwanegu elfen arall y mae'n chi helpu mynd i mewn i amrywiaeth rhif leoliad dau. 

Nawr rhestrau cysylltiedig yn un arall ffordd i weithredu cyrn. Ac os y diffiniad hwn ar y sgrin yma yn edrych yn gyfarwydd i chi, 'i' oherwydd ei fod yn edrych bron yn union yr un fath, mewn gwirionedd, mae'n 'n bert lawer yn union yr un fath ag rhestr cysylltiedig yn unigol, os cofiwch o'n trafodaeth ar rhestrau cysylltiedig yn unigol mewn fideo arall. Yr unig gyfyngiad yma yw i ni fel rhaglenwyr, nid ydym yn caniatáu i mewnosod neu ddileu hap o'r rhestr cysylltiedig yn unigol y gallem ei wneud o'r blaen. Ni allwn ond yn awr yn mewnosod a dileu o'r y blaen neu ben y cysylltiedig rhestr. Mae hynny'n wir yr unig gwahaniaeth er. Mae hyn yn wahanol restr cysylltiedig yn unigol. Dim ond y cyfyngiad ailosod ar ein hunain fel rhaglenwyr sy'n yn newid i mewn pentwr. 

Y rheol yma yw bob amser yn cynnal Pointer i bennaeth rhestr cysylltiedig. Mae hyn wrth gwrs yn gyffredinol rheol bwysig yn gyntaf. Ar gyfer rhestr gysylltiedig beth bynnag yn unigol chi Dim ond angen pwyntydd i'r pen er mwyn cael bod cadwyn yn gallu cyfeirio i bob elfen arall yn y rhestr cysylltiedig. Ond mae'n arbennig bwysig gyda stac. Ac felly yn gyffredinol rydych yn mynd i mewn gwirionedd yn eisiau pwyntydd hwn yn newidyn byd-eang. Mae'n debyg ei fod yn mynd i yn haws hyd yn oed y ffordd honno. Felly beth yw analogs o gwthio a pop? Hawl. Felly gwthio unwaith eto yn ychwanegu elfen newydd i'r pentwr. Mewn rhestr cysylltiedig sy'n yn golygu ein bod yn mynd i gael i greu nod newydd yr ydym ni'n mynd i ychwanegu i mewn i'r rhestr cysylltiedig, ac yna dilynwch y camau yn ofalus ein bod ni wedi amlinellwyd yn flaenorol mewn rhestrau cysylltu'n unigol i ychwanegu at y gadwyn heb dorri'r gadwyn a cholli neu orphaning unrhyw elfennau o'r rhestr cysylltiedig. A dyna yn y bôn yr hyn sy'n Ychydig blob o destun yno crynhoi. A gadewch i ni edrych arno fel diagram. 

Felly dyma ein rhestr cysylltiedig. Mae'n cynnwys pedair elfen yr un pryd. Ac yn fwy berffaith dyma ein stacio sy'n cynnwys pedair elfen. A gadewch i ni ddweud ein bod yn awr am gwthio eitem newydd i'r pentwr hwn. Ac rydym am i wthio newydd eitem eu data gwerth yn 12. Wel beth ydym yn mynd i'w wneud? Wel yn gyntaf rydym yn mynd i gofod malloc, ddeinamig neilltuo lle ar gyfer nod newydd. Ac wrth gwrs yn syth ar ôl rydym yn gwneud galwad i malloc rydym bob amser gwnewch yn siwr i wirio am null, oherwydd os rydym yn cael null nôl roedd rhyw fath o broblem. Nid ydym am i dereference hynny null Bydd pwyntydd neu os ydych yn dioddef nam GEY. Dyw hynny ddim yn dda. Felly, rydym wedi malloced y nôd. Byddwn yn cymryd yn ganiataol ein bod wedi cael llwyddiant yma. Rydym yn mynd i roi i mewn i 12 maes data hwnnw nôd. Nawr ydych chi'n cofio pa rai o'n awgrymiadau yn symud nesaf, felly nid ydym yn torri'r gadwyn? Mae gennym gwpl o opsiynau yma, ond yr unig un sydd yn mynd i fod yn ddiogel yw gosod newyddion pwyntydd nesaf i pwynt i'r hen bennaeth y rhestr neu beth fydd yn fuan yn y hen bennaeth y rhestr. Ac yn awr bod ein holl elfennau yn cael eu clymu at ei gilydd, gallwn dim ond symud y rhestr i bwynt i'r un lle sy'n gwneud newydd. Ac rydym yn awr wedi gwthio yn effeithiol yn Elfen newydd ar flaen y pentwr. 

I pop rydym yn unig eisiau dileu yr elfen gyntaf. Ac felly y bôn yr hyn mae'n rhaid i ni wneud yma, dda mae'n rhaid i ni ddod o hyd i'r ail elfen. Yn y pen draw a fydd yn dod yn y newydd pen ar ôl i ni ddileu'r un cyntaf. Felly, dim ond angen i ni ddechrau o'r y dechrau, symud un ei flaen. Unwaith y byddwn wedi cael gafael ar un ymlaen o lle'r ydym ar hyn o bryd yn y gallwn ddileu'r un cyntaf yn ddiogel ac yna gallwn dim ond symud y pen i dynnu sylw at yr hyn oedd y ail dymor ac yna nawr yw'r cyntaf ar ôl hynny nod wedi cael ei ddileu. 

Felly unwaith eto, yn edrych arno fel diagram i ni eisiau yn awr yn pop i elfen oddi ar pentwr hwn. Felly beth ydym ni'n ei wneud? Wel rydym yn mynd yn gyntaf i greu mae pwyntydd newydd sy'n mynd i dynnu sylw at yr un man fel pennaeth. Rydym yn mynd i symud un safle ymlaen drwy ddweud hafal Trav Trav nesaf er enghraifft, a oedd yn Byddai symud y pwyntydd un Trav sefyllfa ymlaen. Nawr ein bod ni wedi cael dal ar yr elfen gyntaf drwy'r rhestr pwyntydd o'r enw, a'r ail elfen drwy pwyntydd enw Trav, gallwn ddileu hynny yn ddiogel elfen gyntaf o'r pentwr heb golli gweddill o'r gadwyn oherwydd ein wedi ffordd i gyfeirio at yr ail elfen anfon ymlaen drwy gyfrwng y pwyntydd enw Trav. 

Felly nawr, gallwn ryddhau y nod. Gallwn rhestr rhad ac am ddim. Ac yna i gyd mae angen i ni ei wneud yn awr yw symud y rhestr i bwynt i'r un lle hynny Trav yn ei wneud, ac rydym yn fath o yn ôl lle rydym yn dechrau cyn i ni gwthio 12 ymlaen yn y lle cyntaf, ar y dde. Mae hyn yn union lle yr oeddem. Roedd gennym bedwar elfen hon stac. Rydym yn ychwanegu pumed. Rydym yn gwthio un rhan o bump Elfen ar, ac yna rydym yn popped bod y rhan fwyaf diweddar Elfen hychwanegu yn ôl i ffwrdd. 

Mae hynny'n wir yn 'n bert lawer popeth sydd i'w staciau. Gallwch eu rhoi ar waith fel araeau. Gallwch eu rhoi ar waith fel rhestrau cysylltiedig. Mae yna, wrth gwrs, eraill ffyrdd i'w gweithredu hefyd. Yn y bôn y rheswm byddem yn ei ddefnyddio staciau yw cynnal data yn y fath fodd bod yr ychwanegwyd fwyaf diweddar elfen yw'r peth cyntaf rydym yn mynd i eisiau mynd yn ôl. Rwy'n Doug Lloyd, mae hyn yn cs50.