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.