DOUG LLOYD: Svo ef þú hefur horfði á vídeó á mánudaginn, þetta er líklega að fara að líða eins smá deja vu. Það er að fara að mjög svipuðum toga, bara með smá snúa á það. Við erum að fara að tala nú um biðraðir. Svo biðröð, svipað stafla, er annars konar gögn uppbygging að við getum notað til að viðhalda gögn í skipulegum hætti. Líkur á stafla, það er hægt að innleiða sem fylki eða tengda listanum. Ólíkt stafla, reglur sem við notum til að ákvarða þegar hlutirnir fá bætt og fjarlægð frá biðröð eru svolítið öðruvísi. Ólíkt stafla, sem er LIFO uppbyggingu, endast í, fyrst út, biðröð er FIFO uppbyggingu, FIFO, fyrst inn, fyrst út. Nú biðraðir, þú sennilega hafa hliðstæðan að biðröð. Ef þú hefur einhvern tíma verið í samræmi við skemmtigarður eða í banka, það er tegund af sanngirni framkvæmd uppbyggingu. Fyrsta manneskjan í takt við bankinn er sá fyrsti hver fær að tala við Teller. 

Það væri tegund af kapp til botns, ef eina leiðin þú got til að tala við Teller í síðasta Bankinn átti að vera síðasta manneskja í línu. Allir myndu alltaf vilja að vera síðasta manneskja í línu, og sá sem var þar fyrst sem hefur verið að bíða um stund, mætti ​​þar tímunum saman, og tíma, sem og tímum áður en þeir hafa tækifæri til að í raun og veru draga allir peningar í bankanum. Og svo biðraðir eru tegund af sanngirni framkvæmd uppbyggingu. En það þýðir ekki endilega að þýða að stafla eru slæmur hlutur, bara sem biðraðir eru önnur leið til að gera það. Svo aftur biðröð er fyrst inn fyrst út, á móti og stafla sem síðastur inn, fyrst út. Líkur á stafla, höfum við tvær aðgerðir sem við getum gert á biðröðum. Nöfn eru enqueue, sem er að bæta við a nýr þáttur til loka biðröð, og dequeue, sem er að fjarlægja elsta þáttur frá the andlit af the biðröð. Þannig að við erum að fara að bæta þætti á the endir af the biðröð, og við erum að fara að fjarlægja þætti frá the andlit af the biðröð. Aftur, með stafla, við vorum að bæta þættir til the toppur af the stafla og fjarlægja þætti frá efsta hluta stafla. Svo með enqueue, það er að bæta við enda, fjarlægja að framan. Svo elsta hlutur þarna er alltaf næsti hlutur að koma út ef við reynum og dequeue eitthvað. 

Svo aftur, með biðröð, við getum array byggir gerð og tengd-listi byggir útfærslur. Við munum byrja aftur með array byggir gerð. Uppbygging skilgreining lítur mjög svipað. Við höfum annað array þar af gögnum tegund gildi, svo það er hægt að halda handahófskennt gögn gerðum. Við erum aftur að fara að nota heilar tölur í þessu dæmi. 

Og rétt eins og með okkar array byggir stafla framkvæmd, vegna þess að við erum að nota er array, við endilega hafa þessi takmörkun sem C góður af knýja á okkur, sem er að við ekki hafa allir kraft í okkar getu til að vaxa og minnka fylkisins. Við verðum að ákveða í upphafi hvað er hámarksfjöldi hlutum sem við getum sett inn í þetta biðröð, og í þessu tilfelli, getu væri einhver pund skilgreint stöðug í númerið okkar. Og að því er varðar þetta video, getu er að fara að vera 10. 

Við þurfum að halda utan um framan á biðröð svo við vitum hver þáttur við viljum dequeue, og við þurfum líka að halda utan um eitthvað else-- fjölda staka sem við höfum í biðröð okkar. Taka við erum ekki að halda utan í lok biðröð, bara stærð biðröð. Og ástæðan fyrir því mun vonandi orðið svolítið skýrari á augnabliki. Þegar við höfum lokið þessi tegund skilgreining, við höfum nýtt gögn tegund heitir biðröð, sem við getum nú lýsa breytur þeirrar gögn tegund. Og nokkuð villast, hef ég ákveðið að kalla þetta biðröð q, bréf q stað gögn tegund q. 

Svo hér er biðröð okkar. Það er uppbygging. Það inniheldur þrjá fulltrúa eða þrjá sviðum, fylki af stærð getu. Í þessu tilfelli, getu er 10. Og þetta array er fara að halda heiltölur. Í græna er framan á biðröð okkar, Næsta þáttur til að fjarlægja, og í rauðu mun vera á stærð við biðröð, hversu margir þættir eru nú núverandi í biðröð. Þannig að ef við segjum q.front jafngildir 0, og q.size stærð jafngildir 0-- við erum að setja 0s í þessum sviðum. Og á þessum tímapunkti, við erum ansi mikið tilbúinn til að byrja að vinna með biðröð okkar. 

Svo fyrsta aðgerð við getum framkvæma er að enqueue eitthvað, til að bæta við nýjum þáttum til að the endir af the biðröð. Jæja hvað þurfum við að gera í almennu máli? Jæja þessi aðgerð enqueue þörfum að samþykkja bendi biðröð okkar. Aftur, ef við hefðum lýst biðröð okkar á heimsvísu, við myndum ekki þurfa að gera þetta endilega, en almennt, við þarf að samþykkja ábendingum að gögn uppbygging eins og þetta, því annars, við erum liggur við value-- við erum liggur í afrit af biðröð, og svo erum við í raun ekki að breyta biðröð að við ætlum að breyta. 

The annar hlutur sem það þarf að gera er að taka a gögn þáttur viðeigandi tegund. Aftur, í þessu tilfelli, það er að fara að vera heiltölur, en þú gætir geðþótta lýsa gögn tegund sem verðmæti og nota þetta almennt. Það er þáttur sem við viljum enqueue, við viljum bæta við lok biðröð. Þá viljum í raun að setja þessi gögn í biðröð. Í þessu tilviki, setja hana í rétt staðsetning array okkar, og þá viljum við breyta stærð í biðröð, hversu margir þættir við nú hafa. 

Svo skulum við hefjast handa. Hér er, aftur, að almennt form virka yfirlýsingu fyrir hvað enqueue gæti litið út. Og hér erum við að fara. Skulum enqueue fjölda 28 í biðröð. Svo hvað erum við að fara að gera? Jæja, the andlit af biðröð okkar er á 0, og stærð biðröð okkar er á 0, og þannig að við viljum líklega að setja fjöldi 28 í array þáttur númer 0, ekki satt? Þannig að við höfum nú komið fyrir að í það. Svo nú hvað við þurfum að breyta? Við viljum ekki að breyta framan biðröð, vegna þess að við viljum vita hvað þáttur við gætum þurft að dequeue síðar. Svo ástæða þess að við höfum framan það er tegund af vísbending um hvað er elsta hlutur í fylkinu. Jæja elsta hlutur í array-- í staðreynd, það eina í array rétt now-- er 28, sem er á array stað 0. Þannig að við viljum ekki að breyta því grænt númer, því það er elsta þáttur. Frekar viljum við breyta stærð. Þannig að í þessu tilfelli, munum við hækka stærð í 1. 

Nú almennt konar hugmynd um hvar Næsta þáttur er að fara að fara í biðröð er að bæta þessa tvo tölur saman, framan og stærð, og að segja þér hvar næsta þáttur í biðröð er að fara að fara. Svo nú skulum enqueue annað númer. Skulum enqueue 33. Svo 33 er að fara að fara í array staðsetningu 0 plús 1. Þannig að í þessu tilfelli, það er að fara að fara í array stað 1, og nú er stærð biðröð okkar 2. 

Aftur, við erum ekki að breyta að framan af biðröð okkar, vegna 28 er enn elsta þáttur, og við viljum to-- þegar við komum loksins að dequeuing, fjarlægja þætti frá þessari biðröð, viljum við að vita þar sem elsta þáttur er. Og svo þurfum við alltaf að halda sumir vísbending um hvar sem er. Svo er það það sem 0 er þar fyrir. Það er það sem að framan er fyrir. 

Skulum í enqueue eitt frumefni, 19. Ég er viss um að þú getur giska þar 19 er að fara að fara. Það er að fara að fara í array staðsetningu númer 2. Það er 0 plús 2. Og nú er á stærð við biðröð okkar 3. Við höfum 3 þætti í því. Þannig að ef við á, og við erum ekki að fara til núna, enqueue annar þáttur, það myndi fara í array stað númer 3, og the stærð af biðröð okkar væri 4. Þannig að við höfum enqueued atriðum núna. Nú skulum byrja að fjarlægja þá. Skulum dequeue þá frá biðröð. 

Svo líkur að skjóta, sem er tegund hliðstæðum um þetta fyrir stafla, dequeue þarf að sætta sig við bendi á queue-- aftur, nema það er á heimsvísu lýst. Nú viljum við að breyta staðsetningu á the andlit af the biðröð. Þetta er þar sem það kemur svona í leik, sem að framan breyta, vegna þess að þegar við fjarlægja þáttur, sem við viljum að færa það yfir á næsta elsta frumefni. 

Þá viljum við minnka stærð biðröð, og þá viljum við skila gildi sem var fjarlægt úr biðröð. Aftur, við viljum ekki bara henda því. Við væntanlega erum útdráttur það frá queue-- við erum dequeuing það vegna þess að við hugsa um það. Þannig að við viljum þessi aðgerð til að fara aftur a gögn þátturinn af gerðinni gildi. Aftur, í þessu tilfelli, gildi er heil tala. 

Svo nú skulum dequeue eitthvað. Skulum við fjarlægja stak úr biðröð. Ef við segjum int x er jafnt og q, merkið q-- aftur er það bendi til þessa q gögnum structure-- hvað þáttur er að fara að vera dequeued? Í þessu tilfelli, vegna þess að það er fyrsta inn, fyrst út gögn uppbygging, FIFO, það fyrsta sem við setjum inn í þetta biðröð var 28, og svo í þessu tilviki, við erum að fara að taka 28 af biðröð, ekki 19, sem er hvað við hefðum gert ef þetta væri stakkur. Við erum að fara að taka 28 af biðröð. 

Svipað og við gerðum við stafla, við erum í raun ekki að fara að eyða 28 frá biðröð sig, við erum bara að fara að eins konar af þykjast það er ekki þar. Svo það er að fara að vera þar í minni, en við erum bara fara að eins konar hunsa það með því að færa hinir tveir reitir af q gögnum okkar uppbyggingu. Við erum að fara að breyta framan. Q.front er nú að fara að vera 1, því það er nú elsta þátturinn sem við höfum í okkar biðröð, því að við höfum nú þegar eytt 28, sem var fyrrum elsta þáttur. 

Og nú viljum við að breyta stærð biðröð að tveimur þáttum í stað þriggja. Nú man áðan sagði ég þegar við langar að bæta þætti í biðröð, við að setja það í fjölda stað sem er summa framan og stærð. Þannig að í þessu tilfelli erum við enn að setja það er næsta þáttur í biðröð, í array stað 3, og við munum sjá að í annað. 

Þannig að við höfum nú dequeued okkar Fyrsti þátturinn af biðröð. Við skulum gera það aftur. Skulum við fjarlægja annað þáttur frá biðröð. Í tilviki, núverandi elsta þáttur er array staðsetningu 1. Það er það sem q.front segir okkur. Að grænt kassi segir okkur að það er elsta þáttur. Og svo, x verður 33. Við munum bara svona gleyma að 33 er í fylkinu, og við munum segja að nú, Ný elsta þáttur í biðröð er array stað 2 og stærð biðröð, fjöldi staka við höfum í biðröð, er 1. Nú skulum enqueue eitthvað, og ég konar gaf þetta í burtu annað síðan, en ef við viljum setja 40 inn í biðröð, þar sem er 40 að fara að fara? Jæja við höfum verið að setja það í q.front plús biðröð stærð, og svo gerir það vit í að í raun að setja 40 hér. Nú taka eftir því að á sumir benda, við erum að fara að fá til the endir af array okkar inni af Q, en það dofna út 28 og 33-- þeir eru í raun, tæknilega opið rými, ekki satt? Og svo getum við eventually-- að regla um að bæta þessir tveir together-- við getum loksins að unga fólkið af stærð getu svo við getum sett um. 

Þannig að ef við fáum að frumefni númer 10, ef við erum skipta um það í frumefni númer 10, við myndum reyndar að setja það í array stað 0. Og ef við ætluðum að array location-- afsaka mig, Ef við settum þá upp saman, og við fengum að tala 11 myndi vera þar sem við þyrfti að setja það, sem er ekki til í þessum array-- það væri að fara út af mörk. Við gætum unga fólkið um 10 og setja það í array stað 1. Svo er það hvernig biðraðir vinna. Þeir eru alltaf að fara að fara frá vinstri til hægri og hugsanlega sett um. Og þú veist að þeir eru að fullu ef stærð, sem rauða kassanum, verður jafnt getu. Og svo eftir að við höfum bætt 40 við biðröð, vel hvað við þurfum að gera? Jæja, elsta þáttur í biðröð er enn 19, þannig að við viljum ekki að breyta framan biðröð, en nú höfum við tvö þættir í biðröð, og svo við viljum auka stærð okkar frá 1 til 2. 

Það er ansi mikið um það með vinna með array byggir biðröð, og svipað stafla, Það er líka leið að innleiða biðröð sem tengda listanum. Nú ef þessi gögn uppbygging tegund lítur þekki þig, það er. Það er ekki ein tengda listanum, það er tvöfalt tengda listanum. Og nú, eins og innskot, það er í raun hægt að hrinda í framkvæmd biðröð sem eintengdan lista, en Ég hugsa í skilmálar af visualization, það í raun gæti hjálpað til að skoða þetta sem tvöfalt tengda listanum. En það er örugglega hægt að gera þetta sem stakar tengda listanum. 

Svo skulum við hafa a líta á hvað þetta gæti litið út. Ef við viljum að enquue-- svo nú aftur við erum að skipta yfir tengda-listanum undirstaða líkan hér. Ef við viljum að enqueue, við viljum til að bæta við nýjum þáttum, vel hvað þurfum við að gera? Jæja, fyrst af öllu, vegna þess að við erum að bæta við enda og fjarlægja úr farin, við líklega viljum halda ábendingum til bæði höfuð og hala af tengda listanum? Tail vera annað orð fyrir the endir af the tengda listanum, síðasta þáttur í tengda listanum. Og þetta mun líklega, aftur, vera gagnleg fyrir okkur ef þeir eru alþjóðlegt breytur. En nú ef við viljum bæta við nýjum þáttur hvað eigum við að gera? Það sem við bara [? Malak?] eða breytilega úthluta nýjum hnút okkar fyrir okkur sjálf. Og þá, eins og þegar við bætum einhverju þáttur til tvöfalt tengda listanum við, bara að raða of-- þessir síðustu þrjú skref hér eru bara allt um að færa það ábendingum á réttan hátt þannig að þátturinn fær bætt við keðja án þess að brjóta keðju eða gera einhvers konar mistök eða hafa einhvers konar slys gerast þar sem við tilviljun munaðarlaus sumir þættir biðröð okkar. Hér er það sem þetta gæti litið út. Við viljum bæta þáttur 10 til loka þessa biðröð. Svo elsta þáttur hér er táknuð með höfuð. Það er það fyrsta sem við setjum í þessum ímynduðu biðröð hér. Með halanum, 13, er mest nýlega bætt þáttur. Og svo ef við viljum enqueue 10 í þetta biðröð, viljum við að setja það á eftir 13. Og svo við erum að fara að virk úthluta pláss fyrir nýja hnút og athuga null til að tryggja við höfum ekki minni bilun. Þá erum við að fara að setja 10 í hnút, og nú þurfum við að vera varkár um hvernig við skipuleggjum ábendingum þannig að við brjóta ekki keðju. 

Við getum sett 10 er fyrri sviði að benda aftur á gamla hala, og síðan '10 verður Ný hala á einhverjum tímapunkti með þeim tíma öllum þessum keðjur eru tengd, ekkert að fara að koma eftir 10 núna. Og svo 10 er næsta bendi mun benda á núll, og þá eftir að við að gera þetta, eftir að við höfum tengdur 10 aftur til að keðja, við getum tekið gamla höfuð, eða, afsökun mér, gamla hali biðröð. Gamla lok biðröð, 13, og gera það benda til að 10. Og nú, á þessum tímapunkti, höfum við enqueued númer 10 í þessum biðröð. Allt sem við þurfum að gera núna er bara að færa hala til að benda á 10 í stað þess að 13. 

Dequeuing er í raun mjög svipuð pabbi frá stafla sem er útfærður sem tengt listanum ef þú hefur séð stafla vídeó. Allt sem við þurfum að gera er að byrja á að farin, finna annað frumefni, losa fyrsta þáttur, og þá færa höfuðið til að benda á annað frumefni. Líklega betra að sjón það bara til að vera sérstaklega skýr um það. Svo hér biðröð okkar aftur. 12 er elsta þáttur í biðröð okkar, höfuð. 10 er nýjasta þáttur í biðröð okkar, hali okkar. 

Og svo þegar við viljum að dequeue stak, við viljum að fjarlægja elsta frumefni. Svo hvað eigum við að gera? Jæja við sett Traversal músina sem byrjar á höfuðið, og við að færa það svo að það bendir til annað frumefni þetta queue-- eitthvað með því að segja Trav jafngildir Trav arrow næst, til dæmis, myndi færa Trav það til að benda á 15, sem, eftir að við dequeue 12, eða eftir að við fjarlægja 12, verður verða þá elsta þáttur. 

Nú höfum við fengið að halda á fyrsta þáttur um músina höfuðið og Annað þáttur gegnum músina Trav. Við getum nú ókeypis höfuð, og þá getum við segir ekkert kemur fyrir 15. lengur. Þannig að við getum breytt 15 er fyrri bendillinn að benda á núll, og við að færa bara höfuð yfir. Og það sem við förum. Nú höfum við tekist dequeued 12, og nú erum við hafa annað biðröð 4 þætti. Það er ansi mikið allt það er að biðraðir, bæði array byggir og tengd-listi byggir. Ég er Doug Lloyd. Þetta er CS 50.