DOUG LLOYD: Mar sin, má tá tú faire ar an físeán ar chairn, is dócha go bhfuil sé seo ag dul chun mothú cosúil le beagán de VU deja. Tá sé seo ag dul go dtí coincheap an-chosúil, díreach le casadh beag ar sé. Táimid ag dul chun labhairt anois faoi scuainí. Mar sin, scuaine, cosúil le Stack, Is de struchtúr sonraí eile de chineál ar gur féidir linn a úsáid a choimeád ar bun sonraí ar bhealach eagraithe. Cosúil le Stack, is féidir é a chur i bhfeidhm mar eagar nó liosta nasctha. Murab ionann agus Stack, na rialacha go linn a úsáid chun a chinneadh nuair rudaí a fháil leis agus a chur as Tá scuaine le beagán difriúil. Murab ionann agus Stack, a Is struchtúr LIFO, go deireanach i, an chéad amach, tá scuaine le FIFO struchtúr, FIFO, den chéad uair i, an chéad amach. Anois scuainí, is dócha bhfuil analaí scuainí. Má tá tú riamh i líne ag páirc spraoi nó i mbanc, níl saghas ar cothroime a chur i bhfeidhm struchtúr. An chéad duine sa líne ag is é an banc an chéad duine a fhaigheann a labhairt leis an teller. 

Bheadh ​​sé saghas rás go bun más rud é an t-aon bhealach fuair tú a labhairt leis an teller ag an banc a bhí le bheith ar an duine deireanach sa líne. Bheadh ​​gach duine ag iarraidh i gcónaí a bheith ar an duine deireanach sa líne, agus an duine a bhí ann ar dtús a bhí ag fanacht ar feadh tamaill, d'fhéadfadh a bheith ann ar feadh uair an chloig, agus uair an chloig, agus uair an chloig sula mbeidh seans a iarbhír aon airgead a tharraingt siar ag an mbanc. Agus mar sin tá scuainí saghas na Struchtúr cothroime a chur i bhfeidhm. Ach ní chiallaíonn gá go go bhfuil cruacha droch-rud, ach go bhfuil scuainí ar bhealach eile a dhéanamh. Mar sin arís tá scuaine túisce isteach is túisce amach, i gcomparáid Stack a mhairfidh i, amach ar dtús. Cosúil le Stack, tá dhá oibríochtaí gur féidir linn a dhéanamh ar scuainí. Is iad na hainmneacha Enqueue, a bhfuil a chur gné nua go dtí deireadh an scuaine, agus Díchiúáil, a bhfuil a bhaint as an duine is sine eilimint ó thaobh tosaigh an scuaine. Mar sin, táimid ag dul chun eilimintí chur isteach ar an deireadh na scuaine, agus táimid ag dul chun eilimintí bhaint ó thaobh tosaigh an scuaine. Arís, leis an chairn, bhí muid ag cur gnéithe dtí an barr an chairn agus eilimintí a bhaint ó bharr an chairn. Mar sin, le Enqueue, tá sé ag cur leis an deireadh, a bhaint as an tosaigh. Mar sin, an rud is sine i ann Is é i gcónaí ar an chéad rud eile le teacht amach má iarracht muid agus rud éigin Díchiúáil. 

Mar sin, arís, le scuainí, is féidir linn implementations eagar-bhunaithe agus nasctha-liosta implementations atá bunaithe. Beidh muid tús arís le implementations eagar-bhunaithe. An sainmhíniú struchtúr Breathnaíonn leor den chineál céanna. Ní mór dúinn sraith eile ann de luach cineál sonraí, ionas gur féidir é a shealbhú cineálacha sonraí treallach. Táimid ag dul arís a úsáid slánuimhreacha sa sampla seo. 

Agus díreach cosúil lenár sraith-bhunaithe a chur chun feidhme Stack, mar gheall orainn ag baint úsáide as eagar, táimid ag gá go tá go teorann C chineál de forfheidhmiú ar ar orainn, a bhfuil muid a nach bhfuil aon fuinneamh inár cumas chun fás agus Laghdaigh an eagar. Ní mór dúinn cinneadh a dhéanamh ag an tús cad é an líon uasta na rudaí gur féidir linn a chur isteach sa scuaine, agus sa chás seo, Bheadh ​​cumas éigin punt sainithe i gcónaí in ár cód. Agus chun críocha an físeán, tá cumas ag dul a bheith 10. 

Ní mór dúinn súil a choinneáil ar an os comhair an scuaine mar sin tá a fhios againn a bhfuil eilimint ba mhaith linn a Díchiúáil, agus ní mór dúinn freisin súil a choinneáil ar else-- rud éigin ar líon na gnéithe go bhfuil muid in ár scuaine. Fógra nach bhfuil muid ag súil a choinneáil ó dheireadh na scuaine, ach an méid de na scuaine. Agus an chúis go mbeidh súil againn bheith le beagán níos soiléire i láthair. Nuair a bheidh againn críochnaithe sainmhíniú seo cineál, ní mór dúinn a cineál nua sonraí ar a dtugtar scuaine, a féidir linn anois dhearbhú athróg den chineál sonraí. Agus beagán confusingly, tá mé cinneadh déanta chun glaoch scuaine seo q, an litir q ionad an gcineál sonraí q. 

Mar sin, tá anseo ár n-scuaine. Tá sé an struchtúr. Tá trí chomhaltaí nó trí páirceanna, le sraith de ACMHAINNE méid. Sa chás seo, tá CUMAS 10. Agus tá sé seo sraith ag dul go dtí slánuimhreacha a shealbhú. I glas é an os comhair ár scuaine, an eilimint in aice a bhaint, agus i dearg Beidh an méid de na scuaine, cé go leor gnéithe atá i láthair na huaire atá ann cheana féin sa scuaine. Mar sin, má deirimid ionann q.front Ionann 0, agus méid q.size 0-- tá muid ag 0s a chur isteach na réimsí. Agus ag an bpointe seo, tá muid go leor i bhfad réidh chun tús a obair lenár scuaine. 

Mar sin, an chéad oibríocht is féidir linn dhéanamh rud éigin a Enqueue, a chur ar eilimint nua a chur an deireadh an scuaine. Bhuel cad is gá dúinn a a dhéanamh i gcás go ginearálta? Bhuel riachtanais an fheidhm seo Enqueue glacadh le pointeoir chuig ár scuaine. Arís, má bhí a dhearbhú linn a ár scuaine ar fud an domhain, Ní bheadh ​​gá dúinn a dhéanamh seo a gá, ach go ginearálta, táimid ag Ní mór glacadh le leideanna struchtúir sonraí mar seo, mar gheall ar shlí, táimid ag rith ag value-- tá muid dul in cóipeanna de na scuaine, agus mar sin nach bhfuil muid ag athrú go hiarbhír an scuaine bhfuil sé i gceist againn a athrú. 

Is é an rud eile ní mór é a dhéanamh glacadh eilimint sonraí a den chineál iomchuí. Arís, sa chás seo, tá sé ag dul a bheith slánuimhreacha, ach d'fhéadfaí tú treallach dhearbhú go bhfuil an cineál sonraí mar luach agus úsáid níos ginearálta. Sin an ghné ba mhaith linn a Enqueue, ba mhaith linn a chur leis an deireadh an scuaine. Ansin, ba mhaith linn i ndáiríre a áit go bhfuil na sonraí sa scuaine. Sa chás seo, é a chur sa suíomh ceart ar ár sraith, agus ansin ba mhaith linn a athrú ar an méid na scuaine, cé mhéad gnéithe linn a tá i láthair na huaire. 

Sin a ligean le tús a chur leis. Seo, arís, go ginearálta dearbhú Foirm fheidhm d'méid a d'fhéadfadh Enqueue cuma mhaith. Agus anseo táimid ag dul. A ligean ar Enqueue an uimhir 28 isteach sa scuaine. Mar sin, cad tá muid ag dul a dhéanamh? Bhuel, is é an os comhair ár scuaine ag 0, agus an méid ár scuaine Is ag 0, agus mar sin ba mhaith linn is dócha a chur an uimhir 28 i líon eilimint eagar 0, ceart? Mar sin, tá muid a chur anois go i ann. Mar sin, anois cad is gá dúinn a athrú? Nílimid ag iarraidh a athrú an os comhair an scuaine, mar ba mhaith linn a fháil amach cad eilimint d'fhéadfadh gá dúinn a Díchiúáil níos déanaí. Mar sin, ar an gcúis atá againn tosaigh ann Is saghas tháscaire ar cad atá an rud is sine sa eagar. Bhuel an rud is sine sa array-- i Go deimhin, an rud amháin sa sraith ceart Is now-- 28, a bhfuil ag suíomh eagar 0. Mar sin, ní bhfuil muid ag iarraidh a athrú ar an líon sin glas, mar gheall ar go bhfuil an ghné is sine. Ina ionad sin, ba mhaith linn a athrú ar an méid. Mar sin, sa chás seo, beidh muid a Méid incrimint go 1. 

Anois saghas ginearálta smaoineamh i gcás na Tá eilimint seo chugainn ag dul chun dul i scuaine Tá a chur leis an dá huimhreacha le chéile, tosaigh agus méid, agus beidh a insint duit i gcás an chéad Tá eilimint sa scuaine ag dul chun dul. Mar sin, anois a ligean ar Enqueue uimhir eile. A ligean ar Enqueue 33. Mar sin, tá 33 ag dul chun dul isteach suíomh eagar 0 móide 1. Mar sin, sa chás seo, tá sé ag dul chun dul isteach suíomh eagar 1, agus anois tá an méid ar ár scuaine 2. 

Arís, nach bhfuil muid ag athrú an os comhair ár scuaine, toisc go 28 tá sé fós ar an eilimint is sine, agus táimid ag Ba mhaith linn a fháil sa deireadh nuair to-- a dequeuing, eilimintí a bhaint as an scuaine, ba mhaith linn go mbeadh a fhios áit a bhfuil an ghné is sine. Agus mar sin ní mór dúinn i gcónaí a choimeád ar bun roinnt tháscaire ar áit a bhfuil sin. Mar sin tá go cad é an 0 ann. Go bhfuil an méid is tosaigh ann. 

A ligean ar i Enqueue gné amháin níos mó, 19. Tá mé cinnte gur féidir leat buille faoi thuairim i gcás ina 19 ag dul chun dul. Tá sé seo ag dul chun dul isteach eagar uimhir suíomh 2. Sin 0 móide 2. Agus anois tá an méid ar ár scuaine 3. Tá 3 ghné ann. Mar sin, má bhí muid chun, agus ní táimid ag dul go deas anois, Enqueue gné eile, bheadh ​​sé dul isteach i suíomh eagar uimhir 3, agus an méid ár scuaine bheadh ​​4. Mar sin, tá muid enqueued eilimintí éagsúla anois. Anois, a ligean ar tús a chur chun iad a bhaint. A ligean ar iad Díchiúáil as an scuaine. 

Mar sin, cosúil leis an pop, a bhfuil saghas de aschur seo le stacks, Ní mór Díchiúáil glacadh le pointeoir leis an queue-- arís, ach amháin má tá sé dearbhaithe ar fud an domhain. Anois, ba mhaith linn a athrú ar an suíomh an os comhair an scuaine. Tá sé seo nuair a thagann sé saghas i spraoi, is athróg tosaigh, mar aon uair amháin againn a bhaint gné, ba mhaith linn a aistriú go dtí an ghné seo chugainn is sine. 

Ansin, ba mhaith linn a laghdú an méid de na scuaine, agus ansin ba mhaith linn a thabhairt ar ais ar an luach go raibh a bhaint as an scuaine. Arís, nach bhfuil muid ag iarraidh a scriosadh ach é. Táimid ag dócha ag aisti sé as an queue-- táimid dequeuing sé toisc go cúram dúinn faoi. Mar sin, ba mhaith linn an fheidhm seo a thabhairt ar ais eilimint sonraí a bhfuil luach de chineál. Arís, sa chás seo, tá luach slánuimhir. 

Mar sin, anois a ligean ar Díchiúáil rud éigin. A ligean ar a bhaint gné as an scuaine. Má deirimid slánuimhir x cothrom & q, ampersand q-- arís go bhfuil pointeoir a ghabhann leis an q sonraí structure-- cén eilimint ag dul a bheith dequeued? Sa chás seo, toisc go bhfuil sé an chéad isteach is túisce amach struchtúr sonraí, FIFO, an chéad rud a chuir muid isteach sa Bhí scuaine 28, agus mar sin sa chás seo, táimid ag dul a ghlacadh 28 as an scuaine, ní 19, a bhfuil cad ba mhaith linn a dhéanamh má ba é seo Stack. Táimid ag dul a ghlacadh 28 amach as an scuaine. 

Cosúil leis an méid a rinne muid le Stack, ní bhíonn againn i ndáiríre ag dul a scriosadh 28 as an scuaine féin, táimid ag dul díreach a chineál de ligean nach bhfuil sé ann. Mar sin, tá sé ag dul chun fanacht ann i gcuimhne, ach tá muid díreach ag dul go dtí chineál ar neamhaird a dhéanamh air ag gluaiseacht an dá réimsí eile dár q sonraí struchtúr. Táimid ag dul a athrú ar an tosaigh. Q.front ag dul anois 1, toisc go bhfuil anois an ghné is sine atá againn inár scuaine, mar tá muid bainte cheana féin 28, a raibh an ghné iar sine. 

Agus anois, ba mhaith linn a athrú an méid de na scuaine go dhá ghné ionad triúir. Anois cuimhneamh níos luaithe dúirt mé nuair a chuirimid ag iarraidh chun eilimintí chur leis an scuaine, chuir muid sé i suíomh eagar a bhfuil an suim tosaigh agus méid. Mar sin, sa chás seo, tá muid ag cur go fóill é, an ghné eile sa scuaine, i suíomh eagar 3, agus beidh orainn a fheiceáil go bhfuil sa dara. 

Mar sin, tá muid anois ar ár dequeued chéad eilimint as an scuaine. A ligean ar é a dhéanamh arís. A ligean ar a bhaint eile eilimint as an scuaine. I gcás, ar an láthair is sine Is eilimint suíomh eagar 1. Sin an méid a insíonn q.front dúinn. Insíonn go bosca glas dúinn go sin é an ghné is sine. Agus mar sin, beidh x bheith 33. Beidh muid díreach de chineál ar dearmad go 33 ann sa eagar, agus beidh orainn a rá go bhfuil anois, an eilimint nua is sine sa scuaine Is ag suíomh eagar 2, agus an méid an scuaine, líon na n-eilimintí atá againn sa scuaine, tá 1. Anois, a ligean ar Enqueue rud éigin, agus mé saghas thug shiúl dara ó shin, ach más mian linn a chur isteach ar an 40 scuaine, nuair a tá 40 ag dul chun dul? Bhuel tá muid ag chur i q.front móide scuaine méid, agus mar sin a dhéanann sé ciall a iarbhír a chur ar 40 anseo. Anois faoi deara go bhfuil ag pointe éigin, táimid ag dul a fháil go dtí deireadh na ár sraith taobh istigh de q, ach go faded amach 28 agus 33-- tá siad i ndáiríre, go teicniúil spásanna oscailte, ceart? Agus mar sin, is féidir linn a eventually-- go riail a chur leis dá together-- fhéadfadh dheireadh muid Ní mór go mod ag an méid na hacmhainne ionas gur féidir linn a wrap timpeall. 

Mar sin, má fhaigheann muid go eilimint uimhir 10, má tá muid ina ionad i líon eilimint 10, ba mhaith linn i ndáiríre a chur i suíomh eagar 0. Agus má bhí muid ag dul go dtí location-- eagar gabh mo leithscéal, má chuir muid suas iad le chéile, agus fuair muid chun líon Bheadh ​​11 a bheith i gcás ba mhaith linn a chur é, nach bhfuil ann sa array-- bheadh ​​sé a bheith ag dul as bounds. D'fhéadfadh muid a mod ag 10 agus a chur sé i suíomh eagar 1. Mar sin, go conas a oibríonn scuainí. Tá siad ag dul i gcónaí chun dul ó chlé go deas agus b'fhéidir wrap timpeall. Agus tá a fhios agat go bhfuil siad más méid iomlán, go bosca dearg, thiocfaidh chun bheith cothrom le toilleadh. Agus mar sin tar éis againn chur leis go dtí an 40 scuaine, go maith cad is gá dúinn a dhéanamh? Bhuel, an eilimint is sine sa scuaine fós 19, mar sin ní féidir linn a iarraidh a athrú an os comhair an scuaine, ach anois tá dhá eilimintí sa scuaine, agus mar sin ba mhaith linn a mhéadú ár méid 1-2. 

Sin go leor i bhfad é le ag obair le scuainí sraith-bhunaithe, agus cosúil leis Stack, Is bealach ann freisin chun scuaine mar liosta nasctha a chur i bhfeidhm. Anois, má an gcineál struchtúr sonraí Breathnaíonn eolas a thabhairt duit, tá sé. Níl sé liosta nasctha ina n-aonar, tá sé ina liosta nasctha doubly. Agus anois, mar leataobh, tá sé is féidir i ndáiríre a chur i bhfeidhm scuaine mar liosta nasctha ina n-aonar, ach I mo thuairimse, i dtéarmaí léirshamhlú, d'fhéadfadh sé cabhrú i ndáiríre chun amharc ar seo mar liosta nasctha doubly. Ach tá sé cinnte is féidir a é seo a dhéanamh mar liosta nasctha ina n-aonar. 

Mar sin, a ligean ar bheith ag féachaint ar cad a d'fhéadfadh sé seo cuma mhaith. Más mian linn a enquue-- mar sin anois, arís tá muid athrú chuig nasctha-liosta múnla bunaithe anseo. Más mian linn a Enqueue, ba mhaith linn a chur ar eilimint nua, go maith cad is gá dúinn a dhéanamh? Bhuel, ar an gcéad dul síos, mar gheall ar táimid ag cur leis an deireadh agus a bhaint as an ag tosú, táimid ag is dócha ag iarraidh a leideanna chun an dá an a choimeád ar bun ceann agus an eireaball an liosta nasctha? Tail á téarma eile do an deireadh an liosta nasctha, an ghné dheireanach sa liosta nasctha. Agus beidh na is dócha, arís, a bheith tairbheach dúinn má tá siad athróga domhanda. Ach anois más mian linn a chur ar nua eilimint cad atá againn a dhéanamh? Cad muid díreach [? Malak?] nó dinimiciúil leithdháileadh ar ár nód nua dúinn féin. Agus ansin, díreach cosúil nuair linn a chur ar aon eilimint chuig liosta a chuirimid nasctha doubly, ach ní mór a shórtáil of-- na trí céimeanna seo caite anseo bhfuil ach faoi gach gluaiseacht an leideanna ar an mbealach ceart ionas go bhfaigheann an eilimint a leanas le an slabhra gan briseadh an slabhra nó a dhéanamh de chineál éigin botún nó a bhfuil de chineál éigin timpiste tharlóidh trína táimid ag thaisme dílleachta roinnt gnéithe dár scuaine. Seo an méid a d'fhéadfadh sé seo cuma mhaith. Ba mhaith linn a chur leis an eilimint 10 go dtí deireadh an scuaine. Mar sin, an ghné is sine anseo Tá ionadaíocht ag ceann. Sin an chéad rud a chuir muid isteach sa scuaine hipitéiseach anseo. Agus eireaball, 13, an chuid is mó bhreisluacha eilimint déanaí. Agus mar sin más mian linn a Enqueue 10 i an scuaine, ba mhaith linn a chur sé tar éis 13. Agus mar sin táimid ag dul a dinimiciúil spás a leithdháileadh le haghaidh nód nua agus a sheiceáil le haghaidh null chun a chinntiú nach bhfuil againn teip cuimhne. Ansin táimid ag dul chun cuir 10 isteach sa nód, agus anois ní mór dúinn a bheith cúramach faoi ​​conas táimid ag eagrú leideanna mar sin ní féidir linn a bhriseadh an slabhra. 

Is féidir linn a leagtar ar 10 s réimse roimhe a chur in iúl ar ais go dtí an eireaball d'aois, agus beidh ó '10 a bheith ar an eireaball nua ag pointe áirithe ag an am a gach ceann de na slabhraí ceangailte, aon rud ag dul chun teacht tar éis 10 ceart anois. Agus mar sin 10 ar pointeoir seo chugainn Beidh pointe a margadh saothair, agus ansin tar éis dhéanaimid é seo, tar éis tá muid ceangailte 10 siar go dtí an slabhra, is féidir linn a chur ar an ceann d'aois, nó, leithscéal dom, an eireaball d'aois ar an scuaine. An deireadh d'aois ar an scuaine, 13, agus é a dhéanamh pointe go dtí 10. Agus anois, ag an bpointe seo, ní mór dúinn enqueued an uimhir 10 isteach sa scuaine. Gach gá dúinn a dhéanamh anois é a bhogadh ach an eireaball a chur in iúl go 10 in ionad 13. 

Is Dequeuing ndáiríre an-chosúil leis popping as Stack go bhfuil curtha i bhfeidhm mar liosta nasctha má tá tú ag féachaint ar na físeáin gcruacha. Gach gá dúinn a dhéanamh ná tús a chur ag an ag tosú, teacht ar an dara gné, saor in aisce ar an chéad eilimint, agus ansin bogadh an ceann a chur in iúl go dtí an dara gné. Is dócha níos fearr a shamhlú é ach a bheith breise soiléir faoi. Mar sin, tá anseo ar ár scuaine arís. Is é 12 an eilimint is sine inár scuaine, an ceann. Is 10 an eilimint is nua inár scuaine, ár eireaball. 

Agus mar sin nuair is mian linn chun Díchiúáil gné, ba mhaith linn a bhaint as an ngné is sine. Mar sin, cad a dhéanaimid? Bhuel leag muid pointeoir traversal a thosaíonn ag ceann, agus sinn ag dul dó ionas go mbeidh sé pointí ar an dara gné de seo queue-- rud éigin ag rá trav ionann trav arrow romhainn, mar shampla, Bheadh ​​bogadh trav ann a chur in iúl go 15, a, tar éis Díchiúáil táimid ag 12, nó tar éis muid a bhaint 12 a bheidh, a bheith ar an ghné sin-is sine. 

Anois tá muid fuair a shealbhú ar an gcéad eilimint tríd an ceann pointeoir agus an dara gné tríd an trav pointeoir. Is féidir linn ceann anois saor in aisce, agus ansin is féidir linn Deir Tagann aon rud roimh an 15 níos mó. Mar sin, is féidir linn a athrú 15 roimhe pointeoir a chur in iúl a margadh saothair, agus muid ag bogadh díreach an ceann os a chionn. Agus ansin muid ag dul. Anois, tá muid go rathúil dequeued 12, agus anois táimid ag tá scuaine eile de 4 eilimintí. Sin go leor i bhfad go léir tá le scuainí, dá eagar-bhunaithe agus nasctha-liosta bunaithe. Tá mé Doug Lloyd. Is é seo an CS 50.