DOUG LLOYD: So as jy het kyk na die video op stapel, hierdie is waarskynlik gaan om te voel soos 'n bietjie van deja vu. Dit gaan 'n baie soortgelyke konsep, net met 'n effense draai op dit. Ons gaan nou praat oor toue. So 'n tou, soortgelyk aan 'n stapel, is 'n ander soort van data struktuur wat ons kan gebruik om te handhaaf data in 'n georganiseerde manier. Soortgelyk aan 'n stapel, dit geïmplementeer kan word as 'n skikking of 'n geskakelde lys. Anders as 'n stapel, die reëls wat ons gebruik om te bepaal wanneer dinge kry bygevoeg en verwyder van 'n tou is 'n bietjie anders. Anders as 'n stapel, wat is 'n LIFO struktuur, laaste in, eerste uit, 'n tou is 'n EIEU struktuur, EIEU, eerste in, eerste uit. Nou toue, het jy waarskynlik 'n analogie toue. As jy al ooit in lyn gewees het op 'n pretpark of by 'n bank, daar is soort van 'n regverdigheid implementering struktuur. Die eerste persoon in die lyn by die bank is die eerste persoon wat kry om die teller te praat. 

Dit sou soort van 'n ras aan die onderkant as die enigste manier jy het die teller by die praat bank was om die laaste persoon in lyn wees. Almal sal wil altyd om die laaste persoon in lyn, en die persoon wat eerste daar was wat wag vir 'n rukkie, kon daar wees vir ure, en ure en ure voordat hulle 'n kans om werklik enige geld by die bank onttrek. En so toue is soort van die regverdigheid implementering struktuur. Maar dit beteken nie noodwendig dat stapels is 'n slegte ding nie, net dat toue is 'n ander manier om dit te doen. So weer 'n tou is eerste in, eerste uit teenoor 'n stapel wat laaste in, eerste uit. Soortgelyk aan 'n stapel, ons het twee operasies dat ons kan uitvoer op toue. Die name is enqueue, wat is om by te voeg 'n nuwe element tot die einde van die tou, en dequeue, wat die oudste verwyder element van die voorkant van die tou. So ons gaan elemente voeg op die einde van die tou, en ons gaan elemente verwyder van die voorkant van die tou. Weereens, met die stapel, is ons die toevoeging elemente by die top van die stapel en die verwydering van elemente Van die top van die stapel. So met enqueue, is dit toe te voeg tot die einde, die verwydering van die voorkant. So die oudste ding daar is altyd die volgende ding om uit te kom as ons probeer en dequeue iets. 

So weer, met toue, kan ons skikking gebaseer implementering en gekoppel-lys gebasseer implementasies. Ons sal weer begin met skikking gebaseer implementasies. Die struktuur definisie lyk redelik soortgelyk. Ons het 'n skikking daar van data tipe waarde sodat dit kan arbitrêre tipes data te hou. Ons weer gaan gebruik heelgetalle in hierdie voorbeeld. 

En net soos met ons skikking gebaseer stapel implementering, want ons is met behulp van 'n skikking, ons noodwendig daardie beperking wat C soort van afdwing op ons, wat is ons moenie enige dinamika in nie ons vermoë om te groei en krimp die skikking. Ons moet besluit aan die begin Wat is die maksimum aantal van die dinge dat ons in hierdie kan sit tou, en in hierdie geval, kapasiteit sou 'n paar pond te wees gedefinieer konstante in ons kode. En vir die doeleindes van hierdie video, is kapasiteit gaan wees 10. 

Ons moet tred te hou van die voorkant van die tou sodat ons weet watter element ons wil dequeue, en ons moet ook tred te hou van iets else-- die aantal elemente dat ons in ons ry. Let ons nie die dop van die einde van die tou, net die grootte van die tou. En die rede vir wat sal hopelik 'n bietjie duideliker in 'n oomblik. Sodra ons voltooi het hierdie tipe definisie ons het 'n nuwe soort data genoem tou, wat ons kan nou verklaar veranderlikes van daardie tipe data. En ietwat verwarrend, het ek besluit om te noem dit tou q, die letter q in plaas van die tipe data q. 

So hier is ons ry. Dit is 'n struktuur. Dit bevat drie lede of drie velde, 'n verskeidenheid van grootte kapasiteit. In hierdie geval, kapasiteit is 10. En dit skikking is gaan heelgetalle te hou. In groen is die voorkant van ons ry, die volgende element te verwyder, en in die rooi sal die grootte van die tou wees, hoeveel elemente is tans bestaande in die tou. So as ons sê q.front gelykes 0 en q.size grootte gelyk 0-- ons is om 0s in die velde. En op hierdie punt, ons is pretty much gereed om te begin werk met ons ry. 

So het die eerste operasie wat ons kan voer is om iets enqueue, om 'n nuwe element te voeg tot die einde van die tou. Wel, wat moet ons doen in die algemene geval? Wel hierdie funksie te enqueue behoeftes om 'n wyser na ons tou te aanvaar. Weereens, as ons verklaar het ons ry wêreldwyd, sou ons nie nodig het om dit te doen noodwendig nie, maar in die algemeen, ons moet pointers te aanvaar datastrukture soos hierdie, want anders, ons verbygaan value-- ons verby in afskrifte van die tou, en so is ons nie eintlik verander die tou wat ons van plan is om te verander. 

Die ander ding wat dit nodig het om te doen is aanvaar 'n data element van die toepaslike tipe. Weereens, in hierdie geval, dit is gaan heelgetalle wees, Maar jy kon arbitrêr verklaar dat die tipe data as waarde en gebruik dit meer algemeen. Dit is die element wat ons wil enqueue, ons wil bydra tot die einde van die tou. Dan wil ons eintlik plaas dat data in die tou. In hierdie geval, plaas dit in die regte plek van ons verskeidenheid, en dan wil ons die grootte verander van die tou, hoeveel elemente wat ons tans het. 

So laat ons begin. Hier is weer, dat die algemene vorm funksie verklaring vir wat enqueue lyk. En hier gaan ons. Kom ons enqueue die aantal 28 in die tou. So, wat gaan ons doen? Wel, die voorkant van ons ry is by 0, en die grootte van ons ry is by 0, en so wil ons waarskynlik te sit die aantal 28 opgestel element getal 0, reg? Dus het ons nou geplaas dat daar in. So nou wat moet ons verander? Ons wil nie om te verander die voorkant van die tou, want ons wil weet wat element ons dalk nodig om later dequeue. So die rede waarom ons het daar voor is 'n soort van 'n aanwyser van wat die oudste ding in die skikking. Wel, die oudste ding in die array-- in Trouens, die enigste ding wat in die skikking reg now-- is 28, wat op verskeidenheid ligging 0. Sodat ons nie wil verander dat die groen nommer, want dit is die oudste element. Inteendeel, ons wil hê dat die grootte te verander. So in hierdie geval, sal ons inkrementeer grootte 1. 

Nou 'n algemene soort van idee van waar die volgende element gaan om te gaan in 'n ry is om die twee getalle te voeg saam, voor en grootte, en dat jy weet waar die volgende element in die ry gaan om te gaan. So nou, laat ons enqueue ander getal. Kom ons enqueue 33. So 33 gaan in om te gaan verskeidenheid ligging 0 plus 1. So in hierdie geval, dit gaan in verskeidenheid plek 1 om te gaan, en nou is die grootte van ons ry is 2. 

Weereens, is ons nie verander die voorkant van ons ry, omdat 28 is nog steeds die oudste element, en ons wil aan- wanneer ons uiteindelik om dequeuing, die verwydering van elemente Van hierdie ry, wil ons weet waar die oudste element is. En dus moet ons altyd in stand te hou sommige aanduiding van waar dit is. So dit is wat die 0 is daar. Dit is wat voor is daar. 

Kom ons in enqueue een element, 19. Ek is seker jy kan raai waar 19 gaan om te gaan. Dit gaan om in te gaan verskeidenheid ligging nommer 2. Dit is 0 plus 2. En nou het die grootte van ons ry is 3. Ons het 3 elemente in dit. So as ons, en ons gaan nie om nou, enqueue ander element, dit sou in verskeidenheid plek te gaan nommer 3, en die grootte van ons ry sou wees 4. So het ons 'n paar elemente waglys nou. Nou laat ons begin om hulle te verwyder. Kom ons dequeue hulle van die tou. 

So soortgelyk aan pop, wat is 'n soort van die analoog van hierdie vir stapels, dequeue moet 'n aanvaar wyser na die queue-- weer tensy dit wêreldwyd is verklaar. Nou wil ons die plek verander van die voorkant van die tou. Dit is waar dit kom soort in die spel, wat voor veranderlike, want as ons verwyder 'n element, ons wil om dit te skuif na die volgende oudste element. 

Dan wil ons daal die grootte van die tou, en dan wil ons die waarde terug dat is verwyder van die tou. Weereens, ons wil nie net weggooi nie. Ons vermoedelik onttrek dit van die queue-- ons dequeuing dit omdat ons omgee nie. So wil ons hierdie funksie om terug te keer 'n data element van die tipe waarde. Weereens, in hierdie geval, waarde is heelgetal. 

So nou, laat ons dequeue iets. Kom ons verwyder 'n element van die tou. As ons sê int x is gelyk aan & q, ampersand q-- weer dit is 'n muis om hierdie q data structure-- wat element gaan word dequeued? In hierdie geval, want dit is 'n eerste in, eerste uit data struktuur, EIEU, die eerste ding wat ons in hierdie sit tou was 28, en so in hierdie geval, ons gaan neem 28 uit die tou, nie 19, en dit is wat ons sou gedoen het as dit was 'n stapel. Ons gaan om te neem 28 uit die tou. 

Soortgelyk aan wat ons gedoen het met 'n stapel, ons is nie eintlik gaan verwyder 28 uit die tou self, ons net gaan om die soort van voorgee dit is nie daar nie. So dit gaan om daar te bly in die geheue, maar ons is net gaan soort van ignoreer deur die beweging die ander twee velde van ons q data struktuur. Ons gaan na die voorkant verander. Q.front gaan nou 1, want dit is nou die oudste element wat ons in ons ry, want ons het alreeds verwyder 28, wat was die voormalige oudste element. 

En nou, ons wil om te verander die grootte van die tou twee elemente in plaas van drie. Nou onthou vroeër het ek gesê wanneer ons wil elemente by die tou, ons sit dit in 'n skikking plek wat is die som van die voorkant en grootte. So in hierdie geval, ons nog steeds om dit die volgende element in die ry, in verskeidenheid plek 3 en ons sal sien dat in 'n sekonde. 

Dus het ons nou dequeued ons eerste element van die tou. Kom ons doen dit weer. Kom ons 'n ander verwyder element van die tou. In die geval, die huidige oudste element is verskeidenheid plek 1. Dit is wat q.front vertel ons. Dat die groen boks vertel ons dat dit is die oudste element. En so sal x 33 geword. Ons sal net soort van vergeet dat 33 bestaan ​​in die skikking, en ons sal nou, die sê dat nuwe oudste element in die ry is op verskeidenheid ligging 2, en die grootte van die tou, die aantal elemente ons het in die tou, is 1. Nou laat enqueue iets, en ek soort het hierdie weg 'n tweede gelede maar as ons wil hê om in die te sit 40 tou, waar is 40 gaan om te gaan? Wel, ons het is om dit in q.front plus tou grootte, en so is dit sinvol om eintlik hier sit 40. Nou sien dat by 'n sekere punt, ons gaan tot aan die einde van die te kry ons verskeidenheid binnekant van q, maar dat vervaag 28 en 33-- hulle is eintlik tegnies oop ruimtes, reg? En so kan ons eventually-- die reël van die toevoeging daardie twee saam op ons kan uiteindelik moet mod deur die grootte van kapasiteit sodat ons kan draai om. 

So as ons by element nommer 10, as ons vervang dit in element nommer 10, sou ons eintlik sit dit in die rigting ligging 0. En as ons gaan verskeidenheid location-- my verskoon, as ons bygevoeg hulle saam, en ons het na die nommer 11 sou wees waar ons sou hê om te sit dit wat nie bestaan ​​nie in hierdie array-- dit sou gaan buite perke. Ons kon mod deur 10 en sit dit opgestel plek 1. So dit is hoe toue werk. Hulle is altyd gaan om te gaan van links na regs en moontlik draai om. En jy weet dat hulle volle as die grootte, wat rooi boks, word gelyk aan kapasiteit. En so nadat ons 40 het by die ry, goed wat ons nodig het om te doen? Wel, die oudste element in die tou is nog 19, sodat ons nie wil verander die voorkant van die tou, maar nou het ons twee elemente in die tou, en so het ons wil verhoog ons grote 1-2. 

Dit is pretty much dit met werk met skikking gebaseer toue, en soortgelyk aan stapel, Daar is ook 'n manier te implementeer 'n tou as 'n geskakelde lys. Nou as hierdie tipe datastruktuur lyk bekend vir julle, dit is nie. Dit is nie 'n een-een gekoppel lys dit is 'n dubbel geskakelde lys. En nou, as 'n eenkant, is dit eintlik moontlik om te implementeer 'n tou as 'n enkel gekoppel lys, maar Ek dink in terme van visualisering, dit eintlik kan help om te sien dit as 'n dubbel geskakelde lys. Maar dit is beslis moontlik om doen dit as 'n enkel geskakelde lys. 

So laat ons 'n blik op wat dit lyk. As ons wil enquue-- So nou weer ons oor te skakel na 'n gekoppelde-lys gebaseer hier model. As ons wil enqueue, ons wil om 'n nuwe element by te voeg, asook wat moet ons doen? Wel, die eerste van alles, omdat Ons voeg tot die einde en die verwydering van die begin, ons waarskynlik wil verwysings na beide die stand kop en die stert van die geskakelde lys? Stert is 'n ander term vir die einde van die geskakelde lys, die laaste element in die geskakelde lys. En dit sal waarskynlik weer voordelig wees om ons te as hulle globale veranderlikes. Maar nou, as ons wil 'n nuwe voeg element wat het ons te doen? Wat ons net [? malak?] of 'n dinamiese toeken ons nuwe node vir onsself. En dan, net soos wanneer ons enige voeg element om 'n dubbel geskakelde lys, net om of-- sorteer daardie laaste drie stappe hier is net alles oor die verskuiwing van die wysers op die regte manier sodat die element kry bygevoeg die ketting sonder om te breek die ketting of maak 'n soort van fout of om 'n soort van 'n ongeluk gebeur waardeur ons per ongeluk Orphan sommige elemente van ons ry. Hier is wat dit kan lyk. Ons wil die element te voeg 10 aan die einde van hierdie tou. So die oudste element hier word verteenwoordig deur kop. Dit is die eerste ding wat ons het in hierdie hipotetiese tou hier. En stert, 13, is die mees onlangs bygevoeg element. En so as ons wil enqueue 10 in hierdie ry, wil ons om dit te sit na 13. En so gaan ons dinamiese toeken ruimte vir 'n nuwe node en kyk vir null om seker te maak Ons het nie 'n geheue mislukking. Dan gaan ons plaas 10 in daardie knoop, en nou moet ons versigtig wees om oor hoe ons te organiseer pointers sodat ons nie breek die ketting. 

Ons kan 10 se vorige veld stel om terug te verwys na die ou stert, en aangesien '10 sal die nuwe stert op 'n sekere punt Teen die tyd dat al hierdie kettings verbind, niks gaan kom na 10 nou. En so 10 se volgende wyser sal verwys na nul en dan na ons dit doen, nadat ons het verbind 10 agtertoe om die ketting, kan ons die ou hoof, of, verskoning te neem my die ou stert van die tou. Die ou einde van die tou, 13, en maak dit wys tot 10. En nou, op hierdie punt, ons het waglys die nommer 10 in die tou. Al wat ons nou moet doen, is net beweeg die stert om te wys op 10 in plaas van 13. 

Dequeuing is eintlik baie soortgelyk aan die knal uit 'n stapel wat geïmplementeer as 'n geskakelde lys as jy die stapels video gesien het. Al wat ons moet doen is om te begin by die begin, vind die tweede element, bevry die eerste element, en dan skuif die hoof om te verwys na die tweede element. Waarskynlik beter om dit te visualiseer net om ekstra duidelik daaroor wees. So hier is ons ry weer. 12 is die oudste element in ons ry, die hoof. 10 is die nuutste element in ons ry, ons stert. 

En so wanneer ons wil om 'n element dequeue, ons wil die oudste element verwyder. So, wat doen ons? Wel, ons het 'n traversal wyser wat begin by die kop, en ons beweeg dit so dat dit wys na die tweede element van hierdie queue-- iets deur te sê trav gelyk trav pyl volgende, byvoorbeeld, sou trav daar beweeg om aan te dui 15, wat, na ons dequeue 12, of na ons verwyder 12, sal geword het van die destydse oudste element. 

Nou het ons 'n houvas op die eerste element via die wyser hoof en die tweede element via die wyser trav. Ons kan nou gratis kop, en dan kan ons sê niks kom voor 15 nie. So kan ons 15 se vorige verander wyser om te verwys na nul en ons het net beweeg die kop oor. En daar gaan ons. Nou het ons suksesvol dequeued 12, en nou is ons het 'n ander tou van 4 elemente. Dit is pretty much al daar is om te toue, beide array gebaseerde en gekoppel-lys gebasseer. Ek is Doug Lloyd. Dit is CS 50.