DOUG LLOYD: Ceart go leor, mar sin ag an bpointe seo tá tú is dócha ar an eolas go leor le arrays agus liostaí nasctha a bhfuil an dá bunscoile struchtúir sonraí tá muid Labhair faoi do thacair de a choinneáil sonraí de chineálacha sonraí den chineál céanna eagraithe. Anois, tá muid ag dul chun labhairt faoi ​​cúpla athruithe ar arrays agus liostaí nasctha. Sa físeán seo, táimid ag dul chun labhairt faoi stoic. Go sonrach táimid ag dul chun labhairt faoi ​​struchtúr sonraí dtugtar Stack. Athghairm ó phlé roimhe seo faoi ​​threo agus cuimhne, go bhfuil an chairn freisin an ainm le haghaidh deighleog de chuimhne i gcás ina ndearbhaítear statically cuimhne memory-- go bhfuil tú ainm, athróga a ainm duit, et frámaí cetera agus feidhm a againn chomh maith frámaí Stack glaoch ann. Mar sin, tá sé seo le struchtúr sonraí Stack Ní le teascán Stack de chuimhne. OK. 

Ach cad é Stack? Mar sin tá sé go leor i bhfad ach cineál speisialta an déanmhais go gcoimeádann sonraí ar bhealach eagraithe. Agus níl dhá an- bealaí a chur chun feidhme cruacha ag baint úsáide as dhá struchtúr sonraí go bhfuil muid eolas maidir leis cheana féin, arrays agus liostaí nasctha. Cad a dhéanann é speisialta Stack an tslí ina chuir muid eolas isteach an chairn, agus ar an mbealach ina ndéanaimid eolas ó an chairn a bhaint. Go háirithe le stoic is é an riail ach amháin an chuid is mó le déanaí Is féidir an ghné seo a leanas a chur as oifig. 

Mar sin, smaoineamh ar é mar má tá sé ina chairn. Táimid ag piling faisnéis ar bharr féin, agus gan ach an rud ag an mbarr Is féidir an carn a chur as oifig. Ní féidir linn a bhaint as an rud thíos toisc go mbeadh gach rud eile collapse agus titim os a chionn. Mar sin, táimid i ndáiríre ag tógáil Stack go ní mór dúinn ansin píosa a bhaint de phíosa. Mar gheall ar seo táimid ag tagairt go coitianta go Stack mar struchtúr LIFO, go deireanach i, an chéad amach. LIFO, go deireanach i, an chéad amach. 

Mar sin, mar gheall ar seo srian le conas is féidir faisnéis a chur leis agus a chur as Stack, níl i ndáiríre ach dhá rud is féidir linn a dhéanamh le Stack. Is féidir linn a bhrú, a bhfuil an téarma a úsáidimid le cur le coinníollacha gné nua chun an barr an Stack, nó más rud é nach bhfuil an chairn ann agus táimid ag a chruthú sé ó thús, ag cruthú an chairn ar an gcéad dul bheadh ​​ag brú. Agus ansin pop, go bhfuil an saghas CS téarma linn a úsáid a bhaint as an chuid is mó le déanaí eilimint chur leis ó bharr an chairn. 

Mar sin, táimid ag dul chun breathnú ar an dá implementations, idir eagar atá bunaithe agus liosta a nasctha bunaithe. Agus táimid ag dul chun tús a chur le sraith bunaithe. Mar sin, tá anseo an smaoineamh bunúsach ar cad a an struchtúr sonraí Stack eagar bunaithe Bheadh ​​cuma mhaith. Ní mór dúinn a shainmhíniú clóscríofa anseo. Taobh istigh de go bhfuil muid dhá chomhalta nó réimsí an struchtúir. Ní mór dúinn le sraith. Agus arís mé ag baint úsáide as an luach cineál sonraí treallach. 

Mar sin d'fhéadfadh sé seo a bheith de chineál ar bith sonraí, Char slánuimhir nó sonraí éigin eile cineál chruthaigh tú cheana. Mar sin, ní mór dúinn le sraith de acmhainn méid. Cumas a bheith punt sainithe tairiseach, b'fhéidir áit éigin eile in ár gcomhad. Mar sin, faoi deara cheana féin leis seo go háirithe cur i bhfeidhm táimid theorainn dúinn féin mar a bhí de ghnáth an cás le arrays, nach féidir linn a Athraigh dinimiciúil, i gcás ina níl líon áirithe na n-eilimintí uasmhéid is Is féidir linn a chur in ár chairn. Sa chás seo, tá sé gnéithe acmhainne. 

Coinneoimid freisin súil a choinneáil ar barr an chairn. Cad eilimint é an chuid is mó leis le déanaí leis an chairn? Agus mar sin a choinneáil orainn súil a choinneáil ar a i athróg ar a dtugtar barr. Agus seo ar fad faigheann fillte suas le chéile i ndáil le cineál sonraí nua ar a dtugtar Stack. Agus nuair a bhíonn muid a cruthaíodh an cineál nua sonraí is féidir linn a chóireáil sé cosúil aon chineál sonraí eile. Is féidir linn a dhearbhú Stack s, díreach cosúil féidir linn a dhéanamh slánuimhir x, y nó Char. Agus nuair a rá linn a Stack s, go maith cad a tharlaíonn Tá fháil againn sraith de cuimhne ar leataobh dúinn. 

Sa cháil cás Tá mé cinneadh déanta cosúil Is 10 mar tá fuair mé athróg amháin de chineál chairn ina bhfuil dhá réimsí cuimhne. Tá sraith, sa chás seo ag dul a bheith le sraith de slánuimhreacha mar is amhlaidh sa chuid is mó de mo samplaí. Agus athróg slánuimhir eile in ann a stóráil an barr, an chur leis an chuid is mó le déanaí eilimint leis an chairn. Mar sin, aon Stack amháin de cad againn díreach sainithe Breathnaíonn mar seo. Tá sé bosca ina bhfuil le sraith de 10 cad Beidh slánuimhreacha sa chás seo agus athróg slánuimhir eile ann i glas a chur in iúl ar an barr an chairn. 

A shocrú ar an barr an Stack linn a rá ach s.top. Sin é an chaoi a chuirimid ar rochtain a fháil ar réimse dtagann aisghlaoch struchtúr. s.top cothrom le 0 héifeachtach mbaineann sé seo chun ár chairn. Mar sin, arís tá dhá oibríochtaí gur féidir linn a dhéanamh anois. Is féidir linn a bhrú agus is féidir linn pop. A ligean ar tús a chur le bhrú. Arís, ag brú go bhfuil cur nua eilimint go barr an chairn. 

Mar sin, cad a dhéanann gá dúinn a dhéanamh i an eagar a chur i bhfeidhm atá bunaithe ar? Go maith sa gcoitinne Tá feidhm bhrú ag dul go mór chun glacadh le pointeoir chuig an chairn. Anois a ghlacadh an dara agus smaoineamh air. Cén fáth go mbeadh muid ag iarraidh a glacadh pointeoir chuig an chairn? Athghairm ó físeáin roimhe seo ar raon feidhme athraitheach agus leideanna, cad a tharlódh má sheoltar muid díreach Stack s, in áit i mar pharaiméadar? Cad é a chur ar aghaidh i ndáiríre i ann? Cuimhnigh táimid ag cruthú cóip nuair a théann muid é le feidhm ach amháin má úsáidimid leideanna. Agus mar sin an fheidhm seo riachtanais a bhrú glacadh le pointeoir chuig an chairn ionas go mbeidh muid ag athrú go hiarbhír an chairn ar intinn againn a athrú. 

An rud bhrú eile ba mhaith leis is dócha go Is gné sonraí de luach chineál glacadh leis. Sa chás seo, arís, slánuimhir go táimid ag dul a chur leis an barr an chairn. Mar sin, tá muid fuair ár dhá paraiméadair. Cad tá muid ag dul go dtí anois a dhéanamh taobh istigh de bhrú? Bhuel, go simplí, táimid ag dul díreach a chur an ghné go dtí an barr an chairn agus ansin a athrú i gcás an barr is é an chairn, go s luach is fearr ponc. Mar sin, is é seo cad feidhm dearbhú bhrú D'fhéadfadh cuma mhaith ar sraith-bhunaithe a chur chun feidhme. 

Arís nach bhfuil an riail crua agus go tapa go bhféadfaí tú a athrú seo agus tá Athraíonn sé ar bhealaí éagsúla. B'fhéidir go bhfuil s dhearbhú ar fud an domhain. Agus mar sin ní gá duit fiú chun pas a fháil go bhfuil sé mar pharaiméadar. Tá sé seo arís ach cás ginearálta le haghaidh bhrú. Agus tá go difriúil bealaí a chur i bhfeidhm. Ach sa chás seo ár Tá bhrú ag dul a ghlacadh dhá argóint, pointeoir chuig Stack agus eilimint sonraí a bhfuil luach de chineál, slánuimhir sa chás seo. 

Mar sin, a dhearbhú linn a s, táimid ag Dúirt ionann s.top 0. Anois, a ligean ar a bhrú ar an uimhir 28 ar an chairn. Bhuel cad a chiallaíonn? Bhuel faoi láthair ar an Is barr an chairn 0. Agus mar sin cad atá go bunúsach ag dul le tarlú go bhfuil táimid ag dul chun bata leis an uimhir 28 i suíomh eagar 0. Pretty simplí, ceart, go ba é an barr agus anois tá muid go maith chun dul. Agus ansin is gá dúinn a athrú ar cad Beidh an barr an chairn a bheith. Ionas go mbeidh an chéad uair eile a bhrú linn a gné i, táimid ag dul chun é a stóráil i suíomh eagar, is dócha nach bhfuil 0. Nílimid ag iarraidh a fhorscríobh cad a chuir muid díreach ann. Agus mar sin beidh muid ag bogadh ach an barr a 1. Sin a dhéanann ciall dócha. 

Anois, más mian linn a chur ar gné eile isteach ar an chairn, a rá ba mhaith linn a bhrú 33, go maith anois táimid ag dul ach a ghlacadh 33 agus é a chur ag uimhir suíomh eagar 1, agus ansin a athrú an barr ár Stack a bheith eagar dhá uimhir suíomh. Mar sin, más rud é an chéad uair eile ba mhaith linn a eilimint a bhrú isteach ar an chairn, beidh sé a chur i suíomh eagar 2. Agus a ligean ar é sin a dhéanamh níos mó ama amháin. Beidh muid a bhrú 19 uaire an stacks. Beidh muid a chur ar 19 i suíomh eagar 2 agus athrú ar an bharr ár chairn a bheith suíomh eagar 3 mar sin más rud é an chéad uair eile a chuirimid ar Ní mór a dhéanamh a bhrú táimid go maith chun dul. 

OK, mar sin go bhfuil ag brú i nutshell. Cad mar gheall ar popping? Dá bhrí sin tá popping an saghas mhacasamhail a brú. Tá sé conas a sonraí a bhaint as an chairn. Agus riachtanais pop gcoitinne a dhéanamh ar an méid seo a leanas. Caithfidh sé a glacadh le pointeoir chuig an Stack, arís sa chás go ginearálta. I gcás eile, d'fhéadfadh tú roinnt dhearbhú an chairn ar fud an domhain, agus sa chás sin ní gá duit a pas a fháil sé i toisc go bhfuil sé cheana rochtain air mar athróg domhanda. Ach ansin cad eile a dhéanamh is gá dúinn a dhéanamh? Bhuel bhí muid ag incriminteach barr an chairn i bhrú, mar sin táimid ag dul is dócha a iarraidh chun decrement an barr an chairn i pop, ceart? Agus ansin ar ndóigh táimid ag dul freisin chun iarraidh a thabhairt ar ais ar an luach a bhaint againn. Má tá muid ag cur gnéithe, ba mhaith linn chun eilimintí fháil amach níos déanaí, táimid ag is dócha i ndáiríre ag iarraidh chun iad a stóráil mar sin againn ná scrios ach iad as an Stack agus ansin a dhéanamh rud ar bith leo. Go ginearálta má tá muid ag brú agus a popping anseo ba mhaith linn a stóráil seo faisnéis ar bhealach bríoch agus mar sin ní dhéanann sé a dhéanamh ciall a scriosadh ach é. Mar sin, ba chóir an fheidhm seo is dócha go bhfuil luach ar ais chugainn. 

Mar sin, is é seo cad dearbhú do pop D'fhéadfadh cuma mhaith ann ag an mbarr clé. Seo tuairisceáin fheidhm sonraí de luach chineál. Arís tá muid ag baint úsáide as slánuimhreacha ar fud. Agus glacann sé pointeoir a Stack mar a argóint aonair nó paraiméadar amháin. Mar sin, cad é pop ag dul a dhéanamh? Ligean le rá ba mhaith linn a anois pop gné uaire de s. Mar sin, cuimhnigh a dúirt mé go bhfuil stoic caite i, amach ar dtús, LIFO struchtúir sonraí. Cé acu eilimint ag dul chun a chur as an chairn? An raibh tú buille faoi thuairim 19? Toisc gur mhaith leat a bheith ceart. Bhí an ghné dheireanach chuir muid go dtí an 19 Stack nuair a bhí na heilimintí brú dúinn ar, agus mar sin tá sé ag dul go dtí an chéad eilimint go bhfaigheann bhaint astu. Tá sé mar má dúirt muid 28, agus ansin chuir muid 33 ar a bharr, agus chuir muid 19 ar a bharr sin. Is é an ghné amháin is féidir linn a éirí de thalamh 19. 

Anois sa léaráid anseo cad atá déanta agam Tá saghas a scriosadh 19 ó na eagar. Ní sin i ndáiríre cad tá muid ag dul a dhéanamh. Táimid ag dul díreach a chineál de ligean nach bhfuil sé ann. Tá sé fós ann i go suíomh chuimhne, ach táimid ag dul díreach chun neamhaird a dhéanamh air ag athrú an bharr ár chairn ó bheith 3-2. Mar sin má bhí muid a bhrú anois eilimint eile isteach ar an chairn, bheadh ​​sé ag scríobh níos mó ná 19. 

Ach a ligean ar nach dul tríd an deacracht de a scriosadh 19 as an chairn. Is féidir linn a ligean ach nach bhfuil sé ann. Chun críocha an chairn tá sé imithe más rud é athraíonn muid an barr a bheith 2 in ionad 3. Ceart go leor, mar sin go raibh go leor i bhfad é. Sin go léir is gá dúinn a dhéanamh a pop gné amach. A ligean ar é a dhéanamh arís. Mar sin, tá mé béim air i dearg anseo Léiríonn táimid ag déanamh glao eile. Táimid ag dul a dhéanamh ar an rud céanna. 

Mar sin, cad atá ar siúl le tarlú? Bhuel, táimid ag dul a stóráil 33 in x agus táimid ag dul a athrú ar an barr an chairn go 1. Ionas go má bhí muid anois a bhrú ar eilimint isteach an chairn a bhfuil muid ag dul a dhéanamh ceart anois, cad atá ar siúl le tarlú Tá táimid ag dul forscríobh eagar uimhir suíomh 1. Mar sin, go 33 gur saghas chlé taobh thiar de sin lig againn ach nach bhfuil ann níos mó, táimid ag dul díreach a clobber é agus chuir 40 ann ina ionad. Agus ansin ar ndóigh, ós rud é a rinne muid a bhrú, táimid ag dul chun incrimint an barr an chairn 1-2 ionas go má táimid a chur anois eilimint eile Feicfidh sé dul i sraith dhá uimhir suíomh. 

Anois tá liostaí nasctha eile bhealach chun stoic a chur i bhfeidhm. Agus má sainmhíniú seo ar an Breathnaíonn an scáileán anseo eolas a thabhairt duit, tá sé mar tá sé beagnach díreach mar an gcéanna, i ndáiríre, tá sé go leor i bhfad go díreach ar an mar liosta nasctha ina n-aonar céanna, má tá tú chun cuimhne as ár plé ar ina n-aonar liostaí nasctha i físeán eile. An srian amháin anseo Is le haghaidh dúinn mar ríomhchláraitheoirí, ní táimid cead chur isteach nó a scriosadh randamach ón liosta nasctha ina n-aonar a d'fhéadfadh muid a dhéanamh roimhe seo. Is féidir linn a chur isteach ach amháin anois agus scrios ó an tosaigh nó barr an nasctha liosta. Sin i ndáiríre an t-aon difríocht cé. Tá sé seo ar shlí eile liosta nasctha ina n-aonar. Tá sé ach an srian in áit ar dúinn féin mar ríomhchláraitheoirí go athruithe sé isteach Stack. 

Is é an riail anseo a choimeád ar bun i gcónaí pointeoir chuig ceann liosta nasctha. Tá sé seo ar ndóigh go ginearálta riail chéad tábhachtach. Le haghaidh nasctha ina n-aonar liosta mar sin féin agat gá ach pointeoir chun an ceann d'fhonn go mbeadh go slabhra a bheith in ann a tharchur gach gné eile ar an liosta nasctha. Ach tá sé go háirithe tábhachtach le Stack. Agus mar sin go ginearálta go bhfuil tú ag dul go dtí mhaith iarbhír an pointeoir a bheith ina domhanda athraitheach. Tá sé ag dul is dócha go a bheith níos éasca go bhealach. Mar sin, cad iad na analogs de bhrú agus pop? Ceart. Mar sin, ag brú arís ag cur gné nua chun an chairn. I liosta nasctha go ciallaíonn táimid ag dul go bhfuil a chruthú nód nua go mbeimid dul a chur isteach ar an liosta nasctha, agus ansin lean na céimeanna go cúramach go atá leagtha amach againn roimhe i liostaí nasctha ina n-aonar chun é a chur le an slabhra gan briseadh an slabhra agus a chailliúint nó a orphaning aon gnéithe den liosta nasctha. Agus sin go bunúsach cad a Blob beag de théacs achoimre ann. Agus a ligean ar ghlacadh le breathnú ar sé mar léaráid. 

Mar sin, tá anseo ar ár liosta nasctha. Tá sé i gcomhthráth ceithre ghné. Agus níos foirfe anseo ar ár Stack ina bhfuil ceithre ghné. Agus a ligean le rá ba mhaith linn anois a bhrú mír nua isteach ar an chairn. Agus ba mhaith linn a bhrú nua Tá mír a bhfuil a luach shonraí 12. Bhuel cad tá muid ag dul a dhéanamh? Bhuel ar dtús táimid ag dul chun spás malloc, dinimiciúil spás a leithdháileadh le haghaidh nód nua. Agus ar ndóigh díreach tar éis a théimid ar glaoch a malloc againn i gcónaí a dhéanamh cinnte a sheiceáil le haghaidh null, mar má fuair muid ar ais null bhí de chineál éigin fhadhb. Ní chuirimid iarraidh a téigh i sin null Beidh pointeoir nó tú ag fulaingt locht seg. Ní Sin maith. Mar sin, tá muid malloced an nód. Beidh muid glacadh leis a bhí againn rath anseo. Táimid ag dul a chur i 12 an réimse sonraí an nód. Anois a dhéanann tú a thabhairt chun cuimhne a bhfuil ár n-leideanna bogann ar aghaidh mar sin ní féidir linn a bhriseadh an slabhra? Ní mór dúinn cúpla roghanna anseo ach an ceann amháin go bhfuil dul a bheith sábháilte Tá nuacht chugainn pointeoir go a shocrú pointe ar an ceann d'aois ar an liosta nó cad a bheidh go luath ar an ceann d'aois ar an liosta. Agus anois go bhfuil gach ceann dár heilimintí atá chained le chéile, Is féidir linn bogadh go díreach liosta a chur in iúl go dtí an áit chéanna go ndéanann nua. Agus ní mór dúinn anois bhrú héifeachtach eilimint nua isteach ar an os comhair an chairn. 

A pop muid ach ag iarraidh a scrios go chéad eilimint. Agus mar sin go bunúsach cad ní mór dúinn a dhéanamh anseo, go maith ní mór dúinn a fháil ar an dara gné. Faoi dheireadh beidh a bheith ar an nua ceann i ndiaidh a scriosadh muid a an chéad cheann. Mar sin, ní mór dúinn ach chun tús a chur as an tús, dul ar aghaidh amháin. Chomh luath agus tá muid fuair a shealbhú ar cheann amháin ar aghaidh ar an áit ina againn faoi láthair Tá féidir linn a scriosadh an chéad cheann go sábháilte agus ansin is féidir linn bogadh ach an ceann a chur in iúl leis an méid a bhí an dara téarma agus ansin anois Is é an chéad uair tar éis sin Tá nód Scriosadh. 

Mar sin arís, ag cur le breathnú ar sé mar léaráid linn a ag iarraidh a pop anois eilimint uaire den chairn. Mar sin, cad a dhéanaimid? Bhuel táimid ag dul ar dtús a chruthú pointeoir nua go bhfuil dul a chur in iúl ar an láthair céanna leis an ceann. Táimid ag dul a bhogadh suíomh amháin ar aghaidh ag rá ionann trav Trav romhainn mar shampla, a Bheadh ​​cinn an ceann pointeoir trav seasamh ar aghaidh. Anois go atá againn fuair shealbhú ar an chéad eilimint tríd an liosta pointeoir ar a dtugtar, agus an dara gné trí pointeoir ar a dtugtar trav, is féidir linn a scriosadh go sábháilte go chéad eilimint as an chairn gan chailliúint an chuid eile an slabhra mar gheall orainn bheith ar bhealach a tharchur leis an dara gné ar aghaidh trí na pointeoir ar a dtugtar trav. 

Mar sin, anois is féidir linn saor in aisce go nód. Is féidir linn a saor in aisce liosta. Agus ansin go léir is gá dúinn a dhéanamh anois bogadh an liosta go dtí pointe go dtí an áit chéanna ndéanann trav, agus táimid saghas ais nuair a thosaigh muid roimh bhrú orainn 12 ar an gcéad dul, ceart. Tá sé seo díreach nuair a raibh muid. Bhí orainn seo ceithre eilimint chairn. Chuir muid an cúigiú. Bhrú orainn an cúigiú eilimint ar, agus ansin dúinn popped an chuid is mó le déanaí eilimint chuirtear ar ais as. 

Sin i ndáiríre go leor i bhfad léir go bhfuil a cruacha. Is féidir leat iad a chur i bhfeidhm mar arrays. Is féidir leat iad a chur i bhfeidhm le liostaí nasctha. Tá, ar ndóigh, eile bealaí chun iad a chur i bhfeidhm chomh maith. Go bunúsach ar an gcúis ba mhaith linn a úsáid Tá stoic sonraí sa chaoi a chothabháil go bhfuil an bhreisluacha is déanaí Is é an ghné an chéad rud táimid dul go dtí mhaith a fháil ar ais. Tá mé Doug Lloyd, is é seo CS50.