DOUG LLOYD: Nii et kui olete vaatasin videot korstnat, see on ilmselt läheb tunda nagu natuke deja vu. See läheb väga sarnane kontseptsioon, lihtsalt kerge väänata seda. Me läheme praegu rääkida umbes järjekorrad. Nii järjekorras, mis on sarnane pinu on teine ​​selline andmestruktuur et saame kasutada, et säilitada andmed organiseeritud viisil. Sarnaselt korstna seda saab rakendada massiiv või ahelloend. Erinevalt korstna reeglid mida me kasutame, et teha kindlaks siis, kui asjad lisada ja eemaldada järjekorras on natuke erinev. Erinevalt virna, mis on LIFO struktuuri, kesta sisse, esimesena välja, järjekord on FIFO struktuuri, FIFO, esimene, esimene välja. Nüüd järjekorrad, siis ilmselt on analoogia järjekorrad. Kui sa oled kunagi olnud joone lõbustuspargi või pangas, seal on omamoodi õigluse rakendamise struktuur. Esimene inimene joone pank on esimene inimene kes saab rääkida teller. 

Oleks omamoodi võidujooks põhja kui ainus võimalus sul rääkida teller juures pank pidi olema viimane inimene line. Igaüks oleks alati tahtnud olema viimane inimene line, ja inimene, kes oli seal esimene kes on oodanud juba mõnda aega, võiks seal olla mitu tundi, ja tunni ja tunni enne kui nad on võimalus tegelikult tühista raha pangas. Ja nii järjekorrad on omamoodi õigluse rakendamise struktuur. Aga see ei tähenda tingimata et korstnad on halb, lihtsalt et järjekorrad on üks võimalus seda teha. Nii jälle järjekord on esimene, esimene välja, võrreldes virna, mis kestab aasta, Esimene välja. Sarnaselt korstna meil on kaks tegevust et me ei tegutse järjekorrad. Nimed on Lisa järjekorda, mida on lisada uus element lõpuni järjekorda, ja dequeue, mis on kustutada vanim elemendi ees järjekorda. Nii et me läheme lisada elemente koridori lõpus järjekorda, ja me ei kavatse eemaldada elemendid esiosast järjekorda. Jällegi on virnas, olime lisades elemente riidale ja eemaldamist elemendid alates ülemisest lehest. Nii Lisa järjekorda, see on lisades Lõpuks eemaldamist ees. Nii vanim asi seal Alati on järgmine asi välja tulema, kui me püüame ja dequeue midagi. 

Nii jälle koos järjekorrad, saame massiivi põhinev rakendused ja seotud põhineva nimekirja rakendusi. Hakkame jälle massiivi baasil rakendusi. Struktuuri määratlemine tundub päris sarnased. Meil on veel hulgaliselt seal andmete tüübi väärtus, nii et see võib olla meelevaldne andmetüüpe. Me jälle kavatse kasutada täisarvud selles näites. 

Ja just nagu meie massiivi põhinev stack rakendamist, sest me oleme kasutades massiiv, me tingimata on see piirang, et C tüüpi ning jõustab meile, mis on meie ei ole mingit dünaamikat meie võime kasvada ja kahaneb massiivi. Peame otsustama alguses Mis on maksimaalne arv asju et saame panna selle järjekorda, ja sel juhul, võimsus peaks olema mingi nael määratletud pidevat meie koodi. Ja Käesolevas video, võimsus saab olema 10. 

Meil on vaja jälgida ees järjekorda nii et me teame, mis element tahame dequeue, ja me peame ka jälgida midagi else-- elementide arv et meil on meie järjekorda. Pange tähele, et me ei jälgimine lõpu järjekorda, vaid suuruse järjekorda. Ja põhjus, et loodetavasti saada natuke selgem kohe. Kui oleme valmis Seda tüüpi määratlust, meil on uus andmetüüp nimetatakse järjekorda, mida me saame nüüd Kinnitan muutujaid, et andmete tüübi. Ja mõneti eksitavalt, ma olen otsustanud nimetame seda järjekorda q täht q asemel andmetüüpi q. 

Nii et siin on meie järjekorda. See on struktuur. See sisaldab kolm liiget või kolm valdkondades, massiivi suurus võimsust. Sel juhul võimsus on 10. Ja see rida on läheb hoidke täisarvud. Green on ees meie järjekorda, siis Järgmine element, mis tuleb eemaldada, ja punane saab suuruse järjekorras, kui palju elemente on praegu olemasolevate järjekorras. Nii et kui me ütleme q.front võrdsete 0, ja q.size suurus võrdub 0-- me panna 0. neile väljadele. Ja sel hetkel, me oleme päris palju valmis alustama tööd oma järjekorda. 

Nii et esimene operatsioon saame täita on Lisa järjekorda midagi, lisada uus element lõppu järjekorda. Noh, mida me peame teha üldise puhul? Noh see funktsioon Lisa järjekorda vajadustele aktsepteerima viit meie järjekorda. Jällegi, kui me oleksime deklareeritud Meie järjekorda maailmas, me ei vaja seda teha tingimata, kuid üldiselt on meil tuleb leppida viiteid to andmestruktuuride niimoodi, sest teisiti, me mööda value-- me oleme kulgeb koopiad järjekorda, ja nii me tegelikult ei muutuvas järjekorras, et me kavatseme muuta. 

Teine asi, mida ta vajab, et teha on nõus andmeelemendis vajalikku tüüpi. Ka sellisel juhul on see saab olema täisarvud, aga sa võiks meelevaldselt Kinnitan andmete liiki kui väärtus ja kasutada seda üldisemalt. See on element tahame Lisa järjekorda, tahame lisada lõpus järjekorda. Siis me tegelikult tahame pange need andmed järjekorda. Sel juhul pannes selle õigesse meie massiiv, ja siis me tahame muuta suurust järjekorra, kui palju elemente me praegu on. 

Nii alustame. Siin on jällegi, et üldiselt kujul funktsiooni deklaratsioon mida Lisa järjekorda tunduda. Ja siin me läheme. Olgem Lisa järjekorda arv 28 järjekorda. Mida me siis teeme? Noh, ees meie järjekord temperatuuril 0 ja suurus meie järjekorda on 0, ja nii me ilmselt tahan panna arvu 28 massiivi element number 0, eks? Nii et me oleme nüüd panna, et seal. Nüüd, mida me peame muutma? Me ei taha, et muuta ees järjekorras, sest me tahame teada, milline element võiks olla vaja dequeue hiljem. Nii et põhjus on meil ees on on omamoodi indikaator, mis on vanimaid asi massiivi. Noh vanim asi array-- sisse Tegelikult ainus asi massiivi õigus now-- on 28, mis on kell massiivi 0. Nii et me ei taha muuta, et roheline number, sest see on vanim element. Pigem soovime suurust muuta. Nii et kui, siis me juurdekasvu suurus 1. 

Nüüd üldine omamoodi idee, kus Järgmine element on minemas järjekorras on lisada need kaks numbrit kokku, ees ja suurus, ja et ütlen teile, kus järgmise element järjekorras on minemas. Nüüd oletame Lisa järjekorda teisele numbrile. Olgem Lisa järjekorda 33. Nii 33 läheb minema massiivi asukoha 0 pluss 1. Nii et sel juhul läheb minema massiivi asukohta 1 ja nüüd suurus meie järjekord on 2. 

Jällegi, me ei muutu ees meie järjekorda, sest 28 on ikka Vanim element, ja me tahan mina-- kui me lõpuks saada to dequeuing, eemaldades elemendid Sellest järjekorda, me tahame teada, kus vanim element on. Ja nii on meil alati vaja säilitada mõned näitaja, kui see on. Nii see on, mida 0 on seal. Seda ees on seal. 

Lähme sisse Lisa järjekorda veel üks element, 19. Ma olen kindel, et te võite arvata kus 19 on minemas. See lähe massiivi asukoha number 2. Ongi 0 + 2. Ja nüüd suurus meie järjekord on 3. Meil on 3 elemente. Nii et kui me olime, ja me ei kavatse et just nüüd, Lisa järjekorda teise element, see läheks massiivi asukohta number 3 ja suurus meie järjekorda oleks 4. Nii oleme enqueued mitmest elemendist nüüd. Nüüd alustame nende kõrvaldamiseks. Olgem dequeue neid järjekorda. 

Nii sarnaneb pop, mis on omamoodi analoogsignaali käesoleva virnade, dequeue peab aktsepteerima kursor queue-- uuesti, kui see on ülemaailmselt kuulutatud. Nüüd tahame asukohta muuta selle ees järjekorda. See on koht, kus see omamoodi kaasas mängu, et ees muutuja, sest kui me eemaldada element, me tahame liikuda selle järgmisele vanim element. 

Siis me tahame vähendada suuruse järjekorras, ja siis me tahame naasta väärtus mis eemaldati järjekorda. Jällegi, me ei taha lihtsalt loobuda. Me ilmselt ei kaevandavad see alates queue-- me oleme dequeuing, sest me hoolime sellest. Nii et me tahame seda funktsiooni tagasi andmeelemendis tüüpi väärtuse. Ka sellisel juhul väärtus ei täisarv. 

Vaatame nüüd dequeue midagi. Olgem mõne elemendi eemaldamiseks järjekorda. Kui me ütleme, int x võrdub & q, ampersand q-- jälle see kursor sellele q andmeid structure-- mida element läheb dequeued? Sel juhul, kuna see on esimene aastal, esimene välja andmestruktuur, FIFO, esimene asi, mida me panna see järjekorras oli 28, ja nii sel juhul, me läheme 28 välja järjekorras, mitte 19, mis on see, mida me oleks teinud, kui see oli pakk. Me läheme 28 out of järjekorda. 

Sarnaselt mida tegime virna, me ei ole tegelikult kustutamas 28 järjekorrast ise, me lihtsalt läheb selline on teeselda seda seal ei ole. Nii see läheb sinna jääda mälu, kuid me oleme lihtsalt läheb selline ignoreerida liigutades Teised kaks suunda meie q andmeid struktuuri. Me läheme muuta ees. Q.front nüüd lähen olla 1, sest see on nüüd vanim element oleme meie järjekorda, sest me oleme juba eemaldatud 28, mis oli endise vanim element. 

Ja nüüd, me tahame muuta suuruse järjekorras kahest osast kolme asemel. Nüüd mäletan varem ütlesin, kui me tahan lisada elemente järjekorda, paneme selle massiivi asukohta mis on summa ees ja suurus. Nii et kui me ikka panna see, järgmise elemendi järjekorras, arvesse massiivi asukohast 3, ja Me näeme, et teist. 

Nii et me oleme nüüd dequeued meie Esimene element järjekorrast. Teeme seda uuesti. Olgem eemaldada teise element järjekorrast. Juhul, praegune vanim element on hulgaliselt kohale 1. Seda q.front ütleb. See roheline kast ütleb meile, et see on vanim element. Ja nii, x muutub 33. Me lihtsalt selline unustada et 33 on olemas massiiv, ja me öelda, et nüüd on Uue vanim element järjekorras on massiivi asukoha 2 ja suurus järjekorra, elementide arv meil sabas, on 1. Nüüd Lisa järjekorda midagi, ja ma omamoodi andis selle ära teise tagasi aga kui me tahame panna 40 sisse järjekorda, kus on 40 kavatse minna? Noh me oleme hakanud seda in q.front pluss järjekorda suurus, ja nii on mõistlik tegelikult panna 40 siin. Nüüd märkate, et Mingil hetkel, me ei kavatse saada lõpuks meie massiivi sees q, kuid pleekinud välja 28 ja 33-- nad tegelikult tehniliselt avatud ruumi, eks? Ja nii me eventually-- Selle reegli lisamise Nende kahe together-- meil võib lõpuks vaja mod suurusest võimsusega et saaksime ümbritsev. 

Nii et kui me saame element number 10, kui me oleme asendades selle elemendi number 10, olime tegelikult panin selle massiivi 0. Ja kui me ei kavatse massiivi location-- vabandage, kui lisasime neid koos, ja saime number 11 oleks, kui meil oleks panna see, mida ei eksisteeri selles array-- see läheb auti. Võiksime mod 10 ja panna see massiiv asukohta 1. Nii see on, kuidas järjekorrad tööta. Nad alati saab minna vasakule paremale ja võimalusel ümbritsev. Ja sa tead, et nad on täis kui suurus, mis punase kasti, muutub võrdne võimsus. Ja nii pärast oleme lisanud 40 kuni järjekorda, hästi, mida me peame tegema? Noh, vanim element Järjekorras on veel 19, nii et me ei taha muuta ees järjekorras, kuid nüüd on meil kaks elementide järjekorda, ja nii me tahame suurendada meie suuruste 1-2. 

See on päris palju seda töötavad massiivi põhinev järjekorrad jms korstnat, seal on ka viis rakendada järjekorda ahelloend. Nüüd, kui need andmed struktuuritüüpidest tundub tuttav, siis on. See ei ole üksi seotud nimekirja, see on kahekordselt seotud nimekirja. Ja nüüd, kui kõrvale on tegelikult võimalik rakendada järjekorras kui üksikult seotud nimekirja, kuid Ma arvan, et nii visualiseerimine, tegelikult võib aidata näha seda kui kahekordselt seotud nimekirja. Aga see on kindlasti võimalik seda teha nii ühekaupa seotud nimekirja. 

Nii saab tutvuda mida see tunduda. Kui me tahame enquue-- nii et nüüd jälle oleme üleminek on seotud nimekiri mudelit siin. Kui me tahame Lisa järjekorda, me tahame lisada uus element, samuti Mida me peame tegema? Well, kõigepealt sellepärast lisame lõpuni ja eemaldamist Alguses me ilmselt tahame säilitada viiteid nii pea ja saba seotud nimekirja? Saba on teine ​​termin lõppu ahelloendid, Viimase element seotud nimekirja. Ja need ilmselt, jälle olla kasulik meile kui nad on globaalmuutujad. Aga nüüd, kui me tahame, et lisada uus element, mida me peame tegema? Mida me lihtsalt [? malak?] või dünaamiliselt eraldada meie uus sõlm ise. Ja siis, just nagu siis, kui me lisada element kahekordselt ahelloendid me, lihtsalt sorteerida of-- need viimased kolm sammud siin on lihtsalt kõike liigutades osuti on õigesti nii et element saab lisada kett lõhkumata kett või teha mingi viga või on mingi õnnetus juhtuda, millega me kogemata harva mõned elemendid meie järjekorda. Siin on, mida see võib tunduda. Me tahame, et lisada element 10 lõpuni seda järjekorda. Nii vanim element siin on esindatud pea. See on esimene asi, mida me panna sellesse hüpoteetiline järjekorda siin. Ja saba, 13, on kõige viimati lisatud element. Ja kui me tahame Lisa järjekorda 10 sisse Selles järjekorras, me tahame panna selle pärast 13. Ja nii me läheme dünaamiliselt eraldada ruumi uue tipu ja kontrollida null veenduda meil ei ole mälu rike. Siis me ei kavatse pane 10 sinna sõlme, ja nüüd me peame olema ettevaatlikud kuidas me korraldame viiteid nii et me ei riku kett. 

Meil on võimalik valida 10 eelmise valdkonnas punkti tagasi vana saba, ja kuna '10 saab uue saba mingil hetkel selleks ajaks kõik need ketid on ühendatud, midagi on tulemas Pärast 10 kohe. Ja nii 10 järgmise pointer toob välja tühjaks, ja siis pärast me seda teeme, kui me oleme ühendatud 10 tahapoole kett, saame vana head, või, vabandust mind, vana saba järjekorda. Vana lõpus järjekorda, 13, ja teha seda punkti 10. Ja nüüd, sel hetkel, on meil enqueued arv 10 sellesse järjekorda. Kõik me peame tegema nüüd on siis liiguta saba punkti 10 asemel 13. 

Dequeuing on tegelikult väga sarnane popping korstnatest, mis on rakendatakse ahelloend Kui olete näinud korstnad video. Kõik me peame tegema, on alustada juures hakanud, leida teine ​​element, tasuta esimene element, ja seejärel liikuda juht osutada teine ​​element. Tõenäoliselt parem visualiseerida seda lihtsalt olla eriti selge see. Nii et siin on meie järjekorda uuesti. 12 on vanim element meie järjekorda juht. 10 on uusim element meie järjekorda, meie saba. 

Ja nii, kui me tahame to dequeue element, Me tahame, et eemaldada vanim element. Mida me siis teeme? Noh seadsime läbipääsusüsteemid pointer mis algab pea, ja me liikuda nii, et see juhib teise elemendi Selle queue-- midagi öelda trav võrdub trav noolt, näiteks oleks liikuda trav seal käsk 15, mis pärast me dequeue 12, või pärast me eemaldada 12, tahe saada siis vanim element. 

Nüüd on meil kinni esimene element kaudu pointer juht ja teine ​​element kaudu pointer matk. Nüüd on võimalik tasuta peas, ja siis saame Rääkimata tuleb enne 15 enam. Nii saame muuta 15 senine kursor punkti tühjaks, ja me lihtsalt liigutada pea üle. Ja me läheme. Nüüd on meil edukalt dequeued 12, ja nüüd me on teise järjekorda 4 elementi. See on päris palju kõik seal on järjekorrad, nii massiivi põhinev ja seotud põhineva nimekirja. Ma olen Doug Lloyd. See on CS 50.