Doug LLOYD: Torej, če ste gledal video na kupu, To je verjetno, da se počutijo kot malo deja vu. To se dogaja na zelo podoben konceptu, Samo z rahlim zavojem na njej. Bomo zdaj govorili o čakalnih vrst. Torej čakalne vrste, podobno kot kup, je še ena vrsta strukture podatkov da bomo lahko uporabili za vzdrževanje Podatki v organiziran način. Podobno kup, ga je mogoče izvajati kot matrika ali povezani seznam. Za razliko od dimnika, pravila ki jih uporabljamo za določanje ko se stvari dodal in odstraniti iz čakalne vrste so nekoliko drugačni. Za razliko od dimnika, ki je struktura LIFO, zadnji noter, prvi ven, čakalna vrsta je FIFO struktura, FIFO, prvi noter, prvi ven. Zdaj čakalne vrste, ste verjetno imajo analogijo do čakalnih vrst. Če ste že kdaj bili v vrsti zabaviščni park ali na banki, tam je neke vrste pravičnosti izvedbenih strukturo. Prva oseba v vrsti banka je prva oseba kdo bo govoril na pripovedovalec. 

To bi bilo nekako dirki do dna, če je edini način moraš govoriti z pripovedovalec na banka naj bi bila zadnja oseba v vrsti. Vsi bi vedno želeli da je zadnja oseba v vrsti, in oseba, ki je bila tam prvič ki je čakala nekaj časa, bi bilo tam več ur, in ure in ure preden so imeli priložnost, da dejansko umakne denar na banki. In tako čakalne vrste so nekako od pravičnost izvedbene strukture. Ampak ne, da ne pomeni nujno da so nizov slaba stvar, samo da so čakalne vrste še en način, da to storite. Torej spet čakalna vrsta je prvi noter, prvi ven, v primerjavi dimnika, ki traja leta, prvi ven. Podobno kup, imamo dve operaciji da bomo lahko nastopili na čakalnih vrst. Imena so enqueue, ki je dodati nov element na koncu prioritetnem vrstnem redu, in dequeue, ki je odstraniti najstarejši Element s sprednje vrsti. Torej bomo dodali elemente na koncu prioritetnem vrstnem redu, in bomo odstranili elemente od prednjega dela vrsti. Ponovimo, da skladovnici, smo dodali Elementi na vrhu kupa in odstranjevanje elementov z vrha dimnika. Torej z enqueue, to je tako, da Konec, odstranjevanje od spredaj. Torej najstarejše stvar v tam Vedno je naslednja stvar da pridejo ven, če bomo poskušali in dequeue nekaj. 

Torej še enkrat, s čakalnih vrst, smo lahko temelji na matrični izvedb in vezan seznam, ki temelji izvedb. Bomo spet začeli z izvedb, ki temelji na matriki. Definicija struktura izgleda precej podobno. Imamo še en niz tam podatkov tipa vrednosti tako da lahko imajo poljubne vrste podatkov. Mi bo spet uporabljati celih števil v tem primeru. 

In tako kot z našimi izvedba dimnika, ki temelji na matrika, ker smo uporabo obrazca matrika, smo nujno imajo to omejitev, da C vrsta od uveljavlja na nas, ki smo nimajo nobene dinamiko v našem sposobnost, da rastejo in se skrči array. Odločiti se moramo na začetku kar je največje število stvari da bomo lahko v to čakalna vrsta, in v tem primeru, Zmogljivost bi nekateri pound opredeljena stalnica v našem kodeksu. In za namene tega video, kapaciteta se bo 10. 

Moramo slediti sprednji del čakalne vrste tako da bomo vedeli, kateri element želimo dequeue, in moramo tudi, da bi spremljali nekaj else-- število elementov da imamo v naši vrsti. Opazili nismo sledenja Ob koncu prioritetnem vrstnem redu, samo velikost vrsti. In razlog za to bo, upajmo, postane malo bolj jasno v trenutku. Ko smo zaključili ta opredelitev tipa, imamo nov tip podatkov imenovane čakalne vrste, kar smo lahko zdaj razglasi spremenljivke te vrste podatkov. In nekoliko zmedeno, sem se odločil, poklicati te čakalne vrste q, črka q namesto podatkovnega tipa q. 

Torej, tukaj je naša čakalne vrste. To je struktura. Vsebuje tri člane ali tri polja, paleto velikosti ZMOGLJIVOSTI. V tem primeru, zmogljivost pa je 10. In to array je dogaja, da imajo cela števila. V zeleno je sprednji del našega vrsti je Naslednji element je treba odstraniti, in rdeče bo velikost prioritetnem vrstnem redu, koliko elementi so trenutno Obstoječa v čakalni vrsti. Torej, če rečemo q.front Ene 0 in velikost q.size enaka 0-- smo dajanje 0s na teh področjih. In na tej točki, da smo precej pripravljeni, da začnejo delati z našo vrsto. 

Torej prva operacija moremo izvesti je enqueue nekaj, da dodate nov element Konec vrsti. No, kaj moramo storiti v splošnem primeru? No, ta funkcija enqueue potrebe da sprejme kazalec na naši vrsti. Še enkrat, če smo razglasila naša čakalne vrste v svetu, mi ne bi bilo treba to storiti nujno, vendar na splošno smo morali sprejeti kazalce do podatkovnih struktur kot je ta, ker v nasprotnem primeru smo mimo value-- smo poteka v kopijah čakalni vrsti, in tako ne bomo dejansko spreminja čakalne vrste, da želimo spremeniti. 

Druga stvar, ki jo moramo storiti, je sprejeti podatkovni element ustreznega tipa. Še enkrat, v tem primeru, da je bo cela števila, vendar pa si lahko poljubno razglasi podatkovni tip kot vrednost in bolj na splošno uporabljati. To je element želimo enqueue, želimo dodati na koncu vrste. Potem smo dejansko želijo postaviti, da so podatki v čakalni vrsti. V tem primeru je dajanje v pravilna lega našega matrike, in potem želimo spremeniti velikost v čakalni vrsti, koliko elementov smo trenutno imajo. 

Torej začnimo. Tukaj je, še enkrat, da je splošna Izjava funkcija oblika Za kaj bi enqueue izgledal. In gremo. Oglejmo enqueue številko 28 v čakalno vrsto. Torej, kaj bomo storili? No, sprednji del našega vrsti je pri 0 ° C, in velikost našega vrsti je na 0, in tako smo verjetno želeli postaviti številka 28 število Elementa 0, kajne? Tako smo zdaj postavljeni, da je tam. Torej, zdaj kaj moramo spremeniti? Mi ne želimo spremeniti sprednji del čakalne vrste, ker želimo vedeti, kaj element bomo morda morali kasneje dequeue. Torej razlog imamo spredaj tam je nekakšen pokazatelj, kaj je najstarejša stvar v matriki. No najstarejša stvar v array-- v Dejstvo, edina stvar v matriki desno now-- je 28, ki je na matrično mestu 0. Torej, ne želimo, da spremeniti to zeleno številko, ker to je najstarejši element. Nasprotno, želimo spremeniti velikost. Torej, v tem primeru bomo prirastek velikosti do 1. 

Zdaj splošno neke ideje, v kateri se Naslednji element je šla v vrsti je, da se ti dve številki skupaj spredaj in velikost, in da vam bom povedala, kje je naslednji element v vrsti bo šel. Torej, zdaj pa enqueue drugo številko. Oglejmo enqueue 33. Torej, 33 je šel v Niz lokacija 0 in 1. Torej, v tem primeru, da se dogaja da gredo v matrično lokaciji 1, in zdaj je velikost našega čakalne vrste je 2. 

Spet smo ne spreminja sprednji del naše čakalne vrste, ker 28 je še vedno Najstarejši element, in smo želim to-- ko smo na koncu dobili da dequeuing, odstranjevanje elementov iz te čakalne vrste, želimo vedeti kjer najstarejši element. In zato smo vedno morali ohraniti nekatere pokazatelj, kje je to. Torej, to je tisto, 0 je tam. To je tisto, spredaj je tam. 

Naj v enqueue ena več elementov, 19. Prepričan sem, da lahko uganiti kjer 19 je šla. To se dogaja, da gredo v Niz lokacija številka 2. To je 0 plus 2. In zdaj je velikost našega vrsti je 3. Imamo 3 elementov v njem. Torej, če smo bili, da, in ne bomo do zdaj, enqueue še en element, da bi šel v matrično lokacijo številka 3, in velikost našega vrsti bi bilo 4. Torej smo enqueued več elementov zdaj. Zdaj pa začnimo, da jih odstranite. Dajmo jim dequeue iz čakalne vrste. 

Torej podobno pop, ki je nekako analoga tega za kupe, dequeue treba kratkoročno sprejeti kazalec na queue-- spet, razen če je to globalno razglašena. Sedaj želimo spremeniti lokacijo sprednje vrsti. To je, če je nekako gre v igro, da prednja spremenljivka, ker ko smo odstranili element, želimo da ga premaknete na naslednjo najstarejši element. 

Potem želimo zmanjšati velikost prioritetnem vrstnem redu, nato pa želimo vrniti vrednost ki je bil odstranjen iz vrste. Še enkrat, ne želimo, da ga preprosto zavreči. Mi verjetno se izkopavajo da iz queue-- sva ga dequeuing ker nam ni vseeno za njega. Zato želimo to funkcijo, da se vrnete podatkovni element tipa vrednosti. Še enkrat, v tem primeru, vrednost je celo število. 

Torej, zdaj pa dequeue nekaj. Oglejmo odstraniti element iz čakalne vrste. Če rečemo, int x enak & q, ampersand -Q- še enkrat, da je kazalec na tej q podatkov structure-- kaj element se bo dequeued? V tem primeru, ker gre za prvi noter, prvi ven strukture podatkov, FIFO, prva stvar, ki jo dal v to čakalna vrsta je 28, in tako v tem primeru, bomo vzeli 28 od čakalne vrste, ne pa 19, kar je za kaj mi pa bi storili, če je bil ta kup. Bomo vzeli 28 od čakalne vrste. 

Podoben temu, kar smo naredili z Sveženj, smo dejansko ni dogaja, da se črta 28 iz vrste samega smo le, da bo vrste od pretvarjati, da ni tam. Tako se dogaja, da tam ostanejo v spomin, vendar smo le tekoč, da ga nekako ignorirati s premikanjem drugi dve področji našega q podatkov struktura. Bomo spremenili spredaj. Q.front se zdaj dogaja, da je 1, ker je sedaj najstarejši element imamo v našem čakalne vrste, saj smo že odstranili 28, ki je bil nekdanji najstarejši element. 

In zdaj, želimo spremeniti velikost vrsti dveh elementov, namesto treh. Zdaj pa ne pozabite, prej sem rekel, ko smo želite dodati elemente v čakalno vrsto, mi smo jih postavili v mestu matrike ki je vsota spredaj in velikosti. Torej, v tem primeru, smo še vedno dajanje da, naslednji element v čakalni vrsti, v matrično lokacijo 3, in bomo videli, da je v sekundi. 

Tako smo zdaj dequeued naše Prvi element iz vrste. Dajmo še enkrat. Oglejmo odstraniti drugo element iz čakalne vrste. V primeru, trenutno najstarejši element je matrika lokacija 1. To je tisto, kar q.front nam pove. To zeleno polje nam pove, da da je najstarejši element. In tako bo x postala 33. Bomo le nekako pozabil da 33 obstaja v matriki, in bomo rekli, da je sedaj, Novi najstarejši element v vrsti je na diod mestu 2, in velikost po prioritetnem vrstnem redu, število elementov imamo v čakalni vrsti, je 1. Zdaj pa enqueue nekaj, in jaz nekako to dal proč drugo nazaj, vendar če želimo postaviti 40 Into The čakalne vrste, kjer je 40 šli? Pa smo se ga je dala v q.front plus čakalne vrste velikosti, in zato je smiselno, da se dejansko dal 40 tukaj. Zdaj opazili, da na neki točki, gremo priti do konca naša matrika znotraj q, ampak da zbledijo 28 in 33-- oni so dejansko, tehnično odprti prostori, kajne? In tako bomo lahko eventually-- to pravilo dodajanja ti dve together-- bomo lahko sčasoma morali mod z velikostjo zmogljivosti tako da bomo lahko ovijte okoli. 

Torej, če želimo priti do elementa številka 10, če smo ga nadomešča v številu elementov 10, bi bili dejansko dal v matrično mestu 0. In če smo bili, da bo Niz me location-- oprostite, če jih bomo sešteli skupaj, in smo prišli do števila 11 bi bilo, ko bi morali dati je, ki ne obstaja v tem array-- da bi šli ven iz igrišča. Mi lahko mod s 10. in dal je v matrično lokaciji 1. Torej, to je, kako čakalne vrste delo. Oni gredo vedno z leve na desno in morda ovijte okoli. In veš, da oni celoti, če velikost, da rdeči škatli, postane enako kapaciteto. In tako, ko smo dodali 40 do čakalne vrste, dobro kaj moramo storiti? No, najstarejši element v vrsti še 19, zato ne želimo spremeniti sprednji del čakalne vrste, ampak zdaj imamo dva Elementi v čakalni vrsti, in zato želimo povečati naše velikosti od 1 do 2. 

To je precej ga z delo s temelji na matrični čakalnih vrst, in podobno nakladanje, obstaja tudi način izvajati čakalne vrste kot povezan seznam. Zdaj, če je ta vrsta podatkovne strukture izgleda znano, da vas je. To ni posamično povezani seznam, to je dvojno povezani seznam. In zdaj, kot prahi, je dejansko mogoče izvajati čakalna vrsta kot posamezno povezani seznam, vendar Mislim, da v smislu vizualizacije, to lahko dejansko pomaga, da si ogledate to kot dvojno povezani seznam. Vendar je vsekakor mogoče To storite tako, kot posamezno povezani seznam. 

Torej, kaj je imeti poglej kaj bi to izgledal. Če želimo enquue-- tako da sedaj spet smo prehod na povezanem seznamu Modelska tukaj. Če želimo enqueue, želimo dodati nov element, dobro Kaj moramo storiti? No, najprej, ker smo dodali do konca in odstranitev iz začenja, bomo verjetno želijo ohraniti napotke za oba glava in rep povezani seznam? Rep pa drug izraz za Konec povezani seznam, zadnji element v povezanem seznamu. In to se bo verjetno še enkrat, bo koristno za nas če so globalne spremenljivke. Ampak zdaj, če želimo dodati novo element kaj moramo storiti? Kaj smo pravkar [? Malak?] ali dinamično dodeliti našo novo vozlišče za nas. In potem, samo všeč, ko smo dodali koli element z dvojno povezanega seznama mi, morali razvrstiti of-- ti zadnji trije koraki tukaj so prav vsi približno gibljejo kazalci na pravilen način tako da dobi element doda veriga ne da bi poškodovali verigo ali izdelavo nekakšne napake ali imajo neke vrste nesreč zgodilo pri čemer smo po naključju sirote nekatere elemente naše vrste. Evo, kaj bi to izgledal. Želimo, da dodate element 10 na koncu te vrste. Torej najstarejši element tukaj predstavlja glavi. To je prva stvar, ki smo mu v tem hipotetičnem čakalne vrste tukaj. In rep, 13, je najbolj Nedavno dodani element. In zato, če želimo, da enqueue 10 v to čakalno vrsto, želimo, da bi ga po 13. In tako bomo dinamično dodeliti prostor za novo vozlišče in preverite null se prepričajte, nimamo okvare spomina. Potem bomo postaviti 10 v to vozlišče, in zdaj moramo biti previdni o tem, kako organizirati kazalce tako da ne bomo prekinili verigo. 

Mi lahko nastavite 10 na prejšnje polje izpostaviti nazaj na staro rep, in ker '10 bo Nov rep na neki točki do takrat, ko vsi ti verige so povezani, nič ne dogaja, da pridejo po 10 zdaj. In tako 10 ali na naslednji kazalec bo opozarjajo na ničlo, in potem, ko smo to naredili, ko smo jih povezan 10 nazaj do verige lahko vzamemo stare glavo, oziroma izgovora me, stari rep čakalne vrste. Stara konec čakalne vrste, 13, in da je poudariti, da 10. In zdaj, na tej točki, imamo enqueued številko 10 v tej vrsti. Vse kar morate storiti zdaj je le premikanje rep do točke na 10 namesto na 13. 

Dequeuing je dejansko Zelo podobna popping iz dimnika, ki je izvaja kot povezan seznam če ste videli video nizov. Vse kar morate storiti je začeti izvajati začenja, najti drugega elementa, sprostiti prvi element, in nato premakniti glavo da kaže na drugi element. Verjetno bolje, da ga vizualizirati samo, da je ekstra jasno o tem. Torej, tukaj je naša čakalne vrste znova. 12 je najstarejši element V naši vrsti, glavi. 10 je najnovejši element V naši vrsti, naši rep. 

In tako, ko želimo da dequeue element, želimo odstraniti najstarejši element. Torej, kaj naj naredimo? No, smo si zastavili prečkanje kazalec ki se začne v glavi, in mi ga premakniti, tako da je opozarja na drugem elementu to queue-- kaj z besedami, trav enaka trav puščico zraven, na primer, bi premakniti trav je poudariti, da 15, ki je, potem ko smo dequeue 12, ali po tem, ko smo odstranili 12, bo postal takrat najstarejši element. 

Zdaj imamo držite na prvi Element preko kazalca glave in drugi element prek kazalca trav. Mi lahko sedaj prosto glavo, in potem bomo lahko pravijo, nič ne pride pred 15. anymore. Tako bomo lahko spremenili 15 je prejšnja kazalec, da kaže na ničlo, in smo samo premaknete nad glavo. In tam gremo. Zdaj imamo uspešno dequeued 12, in zdaj smo še eno čakalno vrsto 4 elementov. To je zal veliko vse je na čakalnih vrst, tako temelji na paleto in vezan seznam, ki temelji. Sem Doug Lloyd. To je CS 50.