Doug LLOYD: Taigi, jei jūs stebėjo apie kamino vaizdo įrašą, Tai tikriausiai vyksta jaustis kaip trupučiu deja vu. Tai vyksta labai panašiai koncepcija, tik su šiek tiek Tvist į jį. Mes ketiname kalbėti dabar apie eiles. Taigi, eilėje, panašus į rietuvę yra kitas duomenų struktūros rūšies kad mes galime naudoti siekiant išlaikyti duomenis organizuotu būdu. Panašus į kaminą, jis gali būti įgyvendintas kaip masyvą ar susietą sąrašą. Skirtingai nuo kamino, taisyklės kad mes naudojame nustatyti kai viskas bus įtraukti ir pašalinti iš eilėje yra šiek tiek kitoks. Skirtingai nuo kamino, kuris yra LIFO struktūra, paskutinis in, first out, eilėje yra FIFO struktūra, FIFO, first in, first out. Dabar eilės, tikriausiai turi eilėms analogiją. Jeigu jūs kada nors buvo linija atrakcionų parkas ar banke, ten tarsi sąžiningumo įgyvendinimo struktūrą. Pirmasis asmuo atitinka bent bankas yra pirmasis asmuo, kuris gauna kalbėti su kasininkas. 

Būtų rūšiuoti lenktynėse į apačią, jei tik taip jūs turite kalbėti su ne kasininkas bankas turėjo būti paskutinis žmogus linija. Visi visada norėtų būti paskutinis asmuo linija, ir asmuo, kuris buvo pirmasis , kuris buvo laukti tam tikrą laiką, gali būti ten valandų, ir valandos, ir valandos kol jie turi galimybę iš tikrųjų atsiimti pinigus banke. Ir taip eiles Rūšiuoti iš teisingumo įgyvendinimo struktūrą. Bet tai nebūtinai reiškia, kad kaminai yra blogas dalykas, tiesiog kad eiles yra dar vienas būdas tai padaryti. Taigi vėl eilė first in, first iš, palyginti su kamino, kuris paskutinis, pirmasis iš. Panašus į kaminą, mes turime dvi operacijas kad mes galime atlikti ant eilėse. Pavadinimai į eilę, kuri yra pridėti naujas elementas į eilės galą, ir dequeue, kuris yra pašalinti seniausias elementas iš eilės priekyje. Taigi mes ketiname pridėti elementus ant iš eilės galą, ir mes ketiname pašalinti elementus nuo eilės priekyje. Vėl, su kamino, mes buvo pridedant elementai prie kamino viršaus ir pašalinti elementus iš kamino viršuje. Taigi su į eilę, tai pridėti prie pabaiga, pašalinant iš priekio. Taigi seniausias dalykas yra visada yra kitas dalykas išeiti, jei mes stengiamės ir dequeue kažką. 

Taigi dar kartą, su eilėse, mes galime masyvo pagrindu diegimas ir susijusi sąrašas pagrįstas diegimo. Pradėsime vėl su masyvo pagrindu diegimas. Struktūra apibrėžimas atrodo gana panašūs. Mes turime dar vieną masyvo ten duomenų tipo verte, todėl ji gali turėti savavališkai duomenų tipus. Mes vėl ketiname naudoti sveikieji skaičiai šiame pavyzdyje. 

Ir kaip su mūsų masyvo pagrindu kamino įgyvendinimas, nes mes naudojant masyvas, mes būtinai turi šį apribojimą, kad C tipo iš įgyvendina mums, kuri yra mes Neturime į dinamiškumą mūsų gebėjimas augti ir trauktis masyvo. Mes turime nuspręsti pradžioje Koks yra didžiausias skaičius dalykų kad mes galime įdėti į šį eilėje, ir šiuo atveju, pajėgumai galėtų būti kai svaras apibrėžta pastovus mūsų kodą. Ir dėl šio tikslais Vaizdo, talpa bus 10. 

Mums reikia sekti iš eilės priekiniai todėl mes žinome, kuris elementas norime dequeue, ir mes taip pat turime sekti kažkas else-- elementų skaičių kad mes turime mūsų eilėje. Atkreipkite dėmesį, mes ne sekti iš eilės galą, tiesiog iš eilės dydžio. Ir dėl šios priežasties, tikimės, bus tapo šiek tiek aiškiau akimirką. Kai baigėme Šio tipo apibrėžimas, mes turime naują duomenų tipą vadinamas eilė, kurioje mes galime dabar deklaruoti kintamuosius to duomenų tipo. Ir šiek tiek klaidinančiai, aš nusprendžiau skambinti šį eilės q raidė q vietoj duomenų tipas q. 

Taigi čia yra mūsų eilė. Tai struktūra. Jame yra trys nariai ar trijų laukai, kurio dydis TALPA masyvo. Šiuo atveju, talpa yra 10. Ir tai masyvas yra ketina surengti sveikieji skaičiai. Žalia yra mūsų eilėje priekio Kitas elementas turi būti pašalintas, ir raudonai bus eilėje dydis, kiek elementai šiuo metu yra esamų eilėje. Taigi, jei mes sakome q.front nelygiaverčiai 0, ir q.size dydis lygus 0-- mes išleisti 0s į šiose srityse. Ir šiuo metu, mes gana daug pasiruošę pradėti dirbti su mūsų eilėje. 

Taigi pirmoji operacija mes galime atlikti yra į eilę kažką, pridėti naują elementą iš eilės pabaigos. Na ką mes turime daryti bendruoju atveju? Na ši funkcija į eilę poreikius priimti žymiklį į mūsų eilėje. Vėlgi, jei būtume paskelbė Mūsų eilė pasaulyje, mes ne reikia tai padaryti nebūtinai, bet apskritai, mes reikia priimti patarimų su duomenų struktūromis kaip šis, nes kitaip, mes pro šalį value-- mes einančios kopijų eilėje, ir todėl mes ne iš tikrųjų keičiasi eilė, kad mes ketiname pakeisti. 

Kitas dalykas, reikia padaryti, tai priimti duomenų elementas atitinkamo tipo. Vėlgi, šiuo atveju, tai bus sveikieji skaičiai, bet galima savavališkai paskelbti duomenų tipą kaip vertės ir naudoti tai apskritai. Štai elementas norime į eilę, norime pridėti prie eilės galą. Tada mes iš tikrųjų norime padėkite, kad duomenys eilėje. Šiuo atveju, įdėti jį Koreguoti vietą mūsų masyvas, ir tada mes nori pakeisti dydį iš eilės, tai kiek mes elementai Šiuo metu. 

Taigi pradėkime. Čia, vėlgi, kad apskritai forma funkcija deklaracija už tai, ką į eilę gali atrodyti. Ir čia mes einame. Leiskite į eilę skaičių 28 į eilę. Taigi, ką mes ketiname daryti? Na, mūsų eilėje priekyje yra 0, ir mūsų eilėje dydžio yra 0, ir todėl mes tikriausiai norite įdėti numeris 28 išsirikiavo elementų skaičius 0, tiesa? Taigi dabar mes vietoje, kad ten. Taigi, ką mums reikia pakeisti? Mes nenorime keisti iš eilės priekyje, nes mes norime žinoti, ką elementą mes gali tekti dequeue vėliau. Taigi priežastis, turime priekinio ten yra tarsi to, ką rodiklis seniausias dalykas masyvo. Na seniausias dalykas array-- į Tai vienintelis dalykas, masyve teisė now-- yra 28, kuris yra ne masyvo 0 vietoje. Taigi, mes nenorime pakeisti, kad žalioji skaičių, nes tai seniausias elementas. Atvirkščiai, mes norime pakeisti dydį. Taigi šiuo atveju, mes prieaugio dydį iki 1. 

Dabar apskritai tarsi idėja, kur Kitas elementas ketina eiti eilėje yra pridėti šiuos du skaičius kartu, priekiniai ir dydis, ir kad bus kur pasakys kitą elementas eilėje ketina eiti. Taigi, dabar tegul į eilę kitą numerį. Leiskite į eilę 33. Taigi 33 ketina eiti į masyvas vietą 0 ir 1. Taigi šiuo atveju, tai vyksta eiti į masyvą vietoje 1 ir dabar mūsų eilė dydis yra 2. 

Vėlgi, mes nekeičiame mūsų eilės priekyje, nes 28 yra vis dar Seniausias elementas, ir mes noriu to-- kai mes galų gale gauti į dequeuing, pašalinti elementus iš šio eilėje, mes norime žinoti kur seniausias elementas yra. Ir taip mes visada reikia išlaikyti kai kur tai rodiklis. Štai ką 0 yra ten. Štai ką priekyje yra ten. 

Leiskite 's Įtraukti į eilę dar vienas elementas, 19. Aš tikiu, kad jūs galite atspėti kur 19 ketina eiti. Jis ketina eiti į masyvas vietą numeris 2. Štai 0 plius 2. Ir dabar mūsų eilėje dydis yra 3. Mes turime 3 elementus jį. Taigi, jei mes, ir mes neketiname kad dabar, į eilę kitą elementą, jis būtų eiti į masyvą vietoje numeris 3, ir mūsų eilėje dydis būtų 4. Taigi mes enqueued keletą elementų dabar. Dabar pradėkime juos pašalinti. Leiskite dequeue juos iš eilės. 

Taigi panaši į pop, kuris yra tarsi iš šis analogas už rietuvių, dequeue reikia priimti rodyklę į queue-- vėl, nebent tai visame pasaulyje deklaruoti. Dabar mes norime pakeisti vietą iš eilės priekyje. Tai kur jis tarsi ateina į žaidimą, kad priekinio kintamasis, nes kai mes pašaliname elementas, mes norime perkelti į kitą ankstesnį elementą. 

Tada mes norime sumažinti iš eilės dydžio, ir tada mes grįžti nori vertę , kuris buvo pašalintas iš eilėje. Vėlgi, mes nenorime tiesiog jį išmeskite. Mes turbūt yra išgauti jis iš queue-- mes dequeuing, nes mums rūpi tai. Taigi mes norime šią funkciją grąžinti duomenų elemento tipo vertę. Vėl, šiuo atveju, yra sveikas skaičius, vertė. 

Taigi, dabar tegul dequeue kažką. Leiskite pašalinti elementą iš eilės. Jei mes sakome, int x lygus & Q, Ampersand q-- vėl tai rodyklė į šį q duomenis structure-- kas elementas bus dequeued? Šiuo atveju, nes jis yra pirmasis in, first out duomenų struktūros, FIFO, pirmas dalykas, mes įdėti į šį eilėje buvo 28, ir taip, šiuo atveju, mes ketiname imtis 28 iš eilėje, o ne 19, kuri yra tai, ką mes padarėme, jei tai buvo kamino. Mes ketiname imtis 28 iš eilės. 

Panašus į ką mes padarėme su kamino, mes ne iš tikrųjų ketina ištrinti 28 iš tos pačios eilės, mes tik ketina rūšies iš apsimesti, kad nėra. Taigi jis ketina ten pasilikti atmintyje, bet mes tiesiog ketina rūšies ignoruoti jį juda kiti du laukai mūsų q duomenų struktūra. Mes ketiname pakeisti priekyje. Q.front dabar ketiname būti 1, nes dabar seniausias elementas mes turime mūsų eilė, nes mes jau pašalinta 28 kuris buvo buvęs seniausias elementas. 

Ir dabar, mes norime pakeisti iš eilės dydžio kad vietoj trijų du elementus. Dabar prisiminti anksčiau sakiau, kai mes norite pridėti elementus į eilę, mes įdėti jį į masyvą vietoje kuris yra priešais ir dydžio suma. Taigi šiuo atveju, mes vis dar išleidimą ji, kitą elementas eilėje, į matricos vietą 3, ir matysime, kad per sekundę. 

Taigi dabar mes dequeued mūsų Pirmasis elementas iš eilės. Darom dar kartą. Leiskite pašalinti kitą elementas iš eilės. Ir tuo atveju,, dabartinis seniausia elementas yra masyvo 1 vieta. Štai ką q.front pasakoja. Tai žalia dėžutė pasakoja, kad tai seniausias elementas. Ir taip, x taps 33. Mes tiesiog rūšies pamiršti kad 33 egzistuoja masyvo, ir mes pasakyti, kad ir dabar, Naujas seniausias elementas eilėje yra bent masyvo vietoje 2, ir dydžio iš eilės, iš elementų skaičius turime eilėje, yra 1. Dabar galime į eilę kažką, ir aš rūšiuoti davė tai toli antras prieš bet jei norime įdėti 40 į eilėje, kur 40 ketinate eiti? Na mes jau išleisti jį į q.front plius eilės dydžio, ir todėl prasminga iš tikrųjų įdėti 40 čia. Dabar pastebėti, kad ne Tam tikru momentu, mes ketiname patekti į pabaigos Mūsų masyvo viduje q, bet numirė 28 ir 33-- jie iš tikrųjų, techniškai atviros erdvės, tiesa? Ir taip, mes galime eventually-- kad pridedant taisyklė tie du together-- mes galiausiai gali reikia mod pajėgumų dydį todėl galime apvyniokite aplink. 

Taigi, jei mes gauname elementą numeris 10, jei mes pakeisti ją į elemento numeris 10, mes norime iš tikrųjų įdėti jį į masyvą vietoje 0. Ir jei mes ketiname masyvas taško, o atsiprašau, jei mes pridėjome juos kartu, ir mes turime numeris 11 būtų, jei mes turime įdėti ji, kuris neegzistuoja šiame array-- ji būtų vakarėliai ribų. Galėtume mod 10 ir įdėti jis išsirikiavo 1 vieta. Štai kaip eiles dirbti. Jie visada bus eiti iš kairės į dešinę ir galbūt apvyniokite aplink. Ir jūs žinote, kad jie pilnas, jei dydis, kad raudonas langelis, tampa lygi talpos. Ir taip, kai mes pridėjome 40 į eilė, gerai, ką mes turime daryti? Na, seniausias elementas eilėje vis dar yra 19, todėl mes nenorime keisti iš eilės priekyje, bet dabar mes turime du elementai eilėje, ir todėl mes nori padidinti Mūsų dydis nuo 1 iki 2. 

Tai gana daug su dirbant su masyvo pagrindu eilėse, ir panašios sukrauti, Taip pat yra būdas įgyvendinti eilę kaip susijusi sąrašą. Dabar, jei tai duomenų struktūra tipas atrodo pažįstamas, ji yra. Tai ne pavieniui susijusi sąrašas tai dvigubai susijusi sąrašas. Ir dabar, kaip panaikinti, ji yra realiai įmanoma įgyvendinti eilėje kaip vieną susietą sąrašą, tačiau Manau, kalbant apie vizualizacija, ji iš tikrųjų gali padėti, kad galėtumėte peržiūrėti tai kaip dvigubai susietą sąrašą. Bet tai tikrai galima tai padaryti kaip vieną susietą sąrašą. 

Taigi leiskite turėti pažvelgti ką tai galėtų atrodyti. Jei norime enquue-- todėl dabar vėl mes pereiti prie susietą sąrašą grįstą modelį čia. Jei norime į eilę, mes norime pridėti naują elementą, gerai ką mes turime daryti? Na, visų pirma, dėl to, mes pridedant prie pabaigos ir pašalinti iš Pradžioje mes tikriausiai nori išlaikyti patarimų tiek vadovas ir susietą sąrašą uodega? Liekamosios yra kitas terminas linkowanego sąrašo pabaigoje, paskutinis elementas susijęs sąrašą. Ir tai tikriausiai, vėl būti naudingas mums jei jie yra globalių kintamųjų. Bet dabar, jei mes norime pridėti naują elementas, ką mes turime daryti? Ką mes tiesiog [? Malak?] arba dinamiškai skirti mūsų naują mazgas sau. Ir tada, tiesiog patinka, kai mes pridėti bet elementas su dviguba susijęs sąrašo mes, tereikia rūšiuoti of-- tie paskutiniai trys žingsniai čia tik visa informacija apie perstumiant rodykles į teisingą kelią taip, kad elementas, bus pridėta prie grandinė nesulaužant grandinę arba padaryti tam tikrą klaidą rūšiuoti ar tam tikra avarijos rūšiuoti atsitiktų, kuriuo mes netyčia našlaičio Kai kurie iš mūsų eilėje elementus. Štai ką tai galėtų atrodyti. Mes norime pridėti elementą 10 su šio eilėje pabaigoje. Taigi seniausias elementas čia atstovauja galvos. Tai pirmas dalykas, mes įdėti į šį hipotetinį eilėje čia. Ir uodega, 13, yra neseniai papildė elementas. Ir todėl, jei mes norime į eilę 10 į Ši eilė, mes norime jį po 13. Ir taip mes ketiname dinamiškai skirti vietos naują mazgas ir patikrinkite null įsitikinti, mes neturime atminties nepakankamumas. Tada mes ketiname vieta 10 į tą mazgą, ir dabar mes turime būti atsargūs apie tai, kaip mes organizuojame patarimų todėl mes negalime nutraukti grandinę. 

Mes galime nustatyti 10 anketa ankstesnis laukas atkreipti atgal į senąją uodegos, ir nuo '10 bus nauja uodega tam tikru momentu tuo metu, kai visi šie grandinės prijungtas, nieko ketina ateiti po 10 dabar. Ir taip 10 naujos žymeklis bus nurodyti NULL, ir tada, kai mes tai padaryti po to, kai mes prijungtas 10 atgal į grandinėje, mes galime imtis seną galvą, ar, atsiprašau man senasis uodega eilėje. Senas pabaiga eilėje, 13, ir padaryti jį punkto iki 10. Ir dabar, šiuo metu, turime enqueued skaičių 10 į šią eilę. Visi mes turime padaryti dabar yra tiesiog perkelti Uodega atkreipti dėmesį į 10, o ne 13. 

Dequeuing yra iš tikrųjų labai panašus į Popping iš kamino, kuris yra įgyvendinama kaip susijęs sąrašą Jei mačiau šūsnis vaizdo. Visi mes turime padaryti, tai pradėti ne pradedant, rasti antrą elementą, nemokamai pirmąjį elementą, ir tada pereiti į galvą į tašką prie antrojo elemento. Tikriausiai geriau vizualizuoti tiesiog būti papildomų aišku apie tai. Taigi čia mūsų eilė dar kartą. 12 yra seniausias elementas mūsų eilėje, galvą. 10 yra naujausias elementas mūsų eilėje, mūsų uodegos. 

Ir todėl, kai mes norime į dequeue elementas, norime pašalinti seniausias elementas. Taigi, ką mes galime padaryti? Na mes nustatyti Sankryþos žymiklį kuris prasideda ne galvos, ir mes perkelti jį taip, kad jis pažymi prie antrojo elemento tai queue-- kažką sakydamas Trav lygus trav rodyklę, pavyzdžiui, būtų perkelti Trav ten rodo 15, kuris, po to, kai mes dequeue 12, arba kai mes pašalinti 12, bus tapti tada seniausia elementas. 

Dabar mes turime sulaikyti pirmas elementas per rodykle galvos ir antrasis elementas per rodykle Trav. Dabar mes galime nemokamą galvą, o tada mes galime pasakyti nieko ateina prieš 15 nebėra. Taigi, mes galime pakeisti 15 ankstesnės rodyklė rodytų į NULL, ir mes tiesiog perkelti per galvą. Ir mes einame. Dabar mes turime sėkmingai dequeued 12, ir dabar mes turi kitą 4 elementų eilę. Štai beveik visi ten yra eiles, tiek masyvo pagrindu ir susiję sąrašas pagrįstas. Aš Doug Lloyd. Tai CS 50.