DOUG Lloyd: Joten jos olet katseli videon pino, tämä on todennäköisesti aio tuntea kuten hieman deja vu. Se tulee hyvin samanlainen käsite, vain hieman kierre sitä. Aiomme puhua nyt noin jonoja. Niin jono, samanlainen pino, on toisenlainen tietorakenteen että voimme käyttää säilyttää tiedot järjestäytyneesti. Samanlainen pino, se voidaan toteuttaa kuten array tai linkitetty lista. Toisin kuin pino, säännöt että käytämme määrittää kun asiat saavat lisätään ja poistetaan jono ovat hieman erilainen. Toisin kuin pino, joka on LIFO rakenne, last in, first out, jono on FIFO rakenne, FIFO, first in, first out. Nyt jonot, luultavasti on analogisesti jonoja. Jos olet joskus ollut jonossa huvipuisto tai pankissa, siellä on eräänlainen oikeudenmukaisuuden täytäntöönpanojaostosta. Ensimmäinen henkilö jonossa pankki on ensimmäinen henkilö kuka saa puhua pankkivirkailija. 

Olisi tavallaan rodun pohjaan, jos ainoa tapa sinun täytyy puhua Teller at pankki oli olla viimeinen henkilö linjassa. Kaikki haluavat aina olevan viimeinen henkilö linjassa, ja henkilö, joka oli siellä ensin joka on odottanut aikaa, voisi olla siellä tuntikausia, ja tuntia, ja tuntia ennen kuin ne on mahdollisuus todella nostaa rahaa pankissa. Ja niin jonot ovat tavallaan oikeudenmukaisuus täytäntöönpanojaostosta. Mutta se ei välttämättä tarkoita että pinot ovat huono asia, vain että jonot ovat toinen tapa tehdä se. Joten jälleen jono on ensimmäinen, ensimmäinen ulos, vs. pino joka kestää vuonna, first out. Samanlainen pino, meillä on kaksi toimintaa että voimme tehdä on jonoja. Nimet ovat enqueue, joka on lisätä uusi elementti jonon, ja dequeue, joka on poistaa vanhimman elementti jonon. Joten aiomme lisätä elementtejä päälle jonon, ja aiomme poistaa elementtejä edestä jonossa. Jälleen kanssa pino, olimme lisäämällä elementtejä pinon päälle ja poistamalla tekijät ylhäältä pinon. Joten enqueue, se lisäämällä lopussa, poistaa edestä. Joten vanhin juttu siellä on aina seuraava asia tulla ulos jos yritämme ja dequeue jotain. 

Joten jälleen, jossa jonot, voimme array-pohjainen toteutukset ja linkitetty-lista perustuu toteutuksissa. Aloitamme uudelleen array-pohjainen toteutukset. Rakenteen määrittely näyttää melko samanlaisia. Meillä on toinen joukko siellä tietojen tyyppi arvo, joten se voi olla mielivaltaista tietotyyppejä. Olemme jälleen aio käyttää kokonaisluvut tässä esimerkissä. 

Ja aivan kuten meidän array-pohjainen pino täytäntöönpanon, koska käytämme array, me välttämättä on, että rajoitus, että C tällaista ja valvoo meitä, mikä on meidän ei ole dynaamisuutta meidän kyky kasvaa ja kutistua jono. Meidän on päätettävä alussa mikä on suurin määrä asioita että voimme tähän jono, ja tässä tapauksessa, kapasiteetti olisi noin punta määritelty jatkuva meidän koodi. Ja tämän video, kapasiteetti tulee olemaan 10. 

Meidän täytyy seurata jonon joten tiedämme, mitkä elementti haluamme dequeue, ja meidän on myös seurata jotain else-- alkioiden lukumäärä että meillä on jonossa. Huomaa, emme pitää kirjaa lopussa jonon, vain koko jonon. Ja syy, joka toivottavasti tullut hieman selkeämpi hetki. Kun olemme saattaneet Tämän tyyppinen määritelmä, meillä on uusi tietotyyppi nimeltään jono, joka voimme nyt julistaa muuttujat tietojen tyyppi. Ja hieman harhaanjohtavasti, olen päättänyt kutsua tätä jonoon q, kirjain q sijasta tietotyyppi q. 

Joten tässä on meidän jono. Se on rakenne. Se sisältää kolme jäsentä tai kolme kentät, taulukon koko KAPASITEETTI. Tässä tapauksessa, kapasiteetti on 10. Ja tämä joukko on aikoo järjestää kokonaislukuja. Vihreä on edessä meidän jonossa, seuraava elementti poistettava, ja punaisella on koko jonon, kuinka monta elementtiä hetkellä olemassa olevat jonossa. Joten jos sanomme q.front tasavertaisten 0, ja q.size koko vastaa 0-- me laitamme 0s osaksi näillä aloilla. Ja tässä vaiheessa, olemme melko paljon valmis aloittamaan työtämme jonoon. 

Joten ensimmäinen operaatio voimme tehdä on laittaa jonoon jotain, lisätä uuden elementin jonon. No mitä meidän tehdä yleisessä tapauksessa? No tämä toiminto laittaa jonoon tarpeisiin hyväksymään osoitin meidän jonoon. Jälleen, jos meillä oli julistanut meidän jono maailmanlaajuisesti, meidän ei tarvitse tehdä tätä väistämättä, mutta yleisesti ottaen, me täytyy hyväksyä viitteitä ja tietorakenteita näin, koska muuten, olemme ohi value-- olemme ohimennen kopioita jonossa, ja niin emme todella muuttuu jono että aiomme muuttaa. 

Toinen asia se tarvitsee vain hyväksyä tieto on sopivaa tyyppiä. Jälleen tässä tapauksessa, se on olemaan kokonaislukuja, mutta voit mielivaltaisesti julistaa tietotyyppi kuin arvo ja käyttää tätä yleisemmin. Se on elementti haluamme laittaa jonoon, haluamme lisätä loppuun jonossa. Sitten me todella haluavat paikka, että tiedot jonossa. Tässä tapauksessa, laitat sen oikea sijainti meidän array, ja sitten haluamme muuttaa kokoa jonossa, kuinka monta elementtiä me tällä hetkellä. 

Joten pääset alkuun. Tässä on, jälleen, että yleinen Form Function ilmoitus mitä enqueue voisi näyttää. Ja tässä sitä mennään. Katsotaanpa laittaa jonoon numero 28 jonoon. Joten mitä me teemme? No, edessä meidän jono on 0, ja koko meidän jonossa on 0, ja niin me luultavasti halua laittaa numero 28 array elementti numero 0, eikö? Joten olemme nyt sijoitettu, että siellä. Joten nyt mitä meidän täytyy muuttaa? Emme halua muuttaa jonon, koska haluamme tietää, mitä elementti meidän on ehkä dequeue myöhemmin. Joten syystä olemme Edessä on eräänlainen indikaattori mitä vanhin asia jono. No vanhin asia array-- vuonna Itse asiassa ainoa asia array oikeassa now-- on 28, joka on klo array sijainti 0. Joten emme halua muuttaa että vihreä numero, koska se on vanhin elementti. Pikemminkin haluamme muuttaa kokoa. Joten tässä tapauksessa, käymme Porrasvälin 1. 

Nyt yleinen eräänlainen käsitys siitä, mihin seuraava elementti ei mene jonoon on lisätä näiden kahden numerot yhdessä, edessä ja koko, ja että kerron sinulle missä seuraava elementti jonossa on menossa. Joten Nyt laittaa jonoon toiseen numeroon. Katsotaanpa laittaa jonoon 33. Joten 33 on menossa mennä array sijainti 0 + 1. Joten tässä tapauksessa, se tulee mennä array sijainti 1, ja nyt koko meidän jono on 2. 

Jälleen, emme muuttuvat edessä meidän jonossa, koska 28 on edelleen vanhin elementti, ja me haluavat to-- kun me lopulta saada ja dequeuing, poistamalla osia Tästä jonosta, haluamme tietää jossa vanhin osa on. Ja niin me aina tarvitse säilyttää jotkut indikaattori, jos se on. Niin, että mitä 0 on siellä. Sitähän edessä on siellä. 

Katsotaanpa vuonna enqueue yksi elementti, 19. Olen varma, että voit arvata jossa 19 on menossa. Se tulee mennä array Sijainti numero 2. Se 0 plus 2. Ja nyt koko meidän jono on 3. Meillä on 3 elementtejä se. Joten jos me, ja emme aio juuri nyt, laittaa jonoon toinen elementti, se mennä array sijainti numero 3, ja koko meidän jonossa olisi 4. Joten olemme enqueued useita tekijöitä nyt. Nyt aloitamme niiden poistamiseksi. Katsotaanpa dequeue ne jonosta. 

Niin samankaltaisia ​​pop, joka on eräänlainen analogiset tämän pinojen, dequeue tarvitsee hyväksyä osoitin queue-- uudelleen, ellei se maailmanlaajuisesti julistettu. Nyt haluamme muuttaa sijainti n jonon. Tästä se tavallaan tulee peliin, että edessä muuttuja, koska kerran poistamme elementti, haluamme siirtää sen seuraavalle vanhin elementti. 

Sitten haluamme vähentää koko jonon, ja sitten haluamme palauttaa arvo joka poistettiin jonosta. Jälleen, emme halua vain hävittää sen. Olemme oletettavasti purat se queue-- olemme dequeuing sitä, koska emme välitä siitä. Joten haluamme tämän toiminnon palata tieto tyypin arvo. Jälleen tässä tapauksessa arvo on kokonaisluku. 

Joten Nyt dequeue jotain. Katsotaanpa poistaa elementti jonosta. Jos sanomme int x vastaa & Q, et-merkki q-- jälleen se osoitin tähän q tiedot structure-- mitä elementti aiotaan dequeued? Tässä tapauksessa, koska se on ensimmäinen in, first out tietorakenne, FIFO, ensimmäinen asia me otetaan tämä jono oli 28, ja niin tässä tapauksessa, aiomme ottaa 28 pois jonossa, ei 19, joka on mitä olisimme tehneet jos tämä oli pino. Aiomme ottaa 28 ulos jonon. 

Samanlainen kuin mitä teimme kanssa pino, emme ole oikeastaan menossa poistaa 28 jonosta itse, olemme juuri menossa eräänlainen ja teeskennellä se ei ole siellä. Joten se tulee siellä muistiin, mutta olemme vain menossa sellainen sivuuttaa sitä liikuttamalla Kahdella muulla alalla meidän q tietojen rakenne. Aiomme muuttaa edessä. Q.front on nyt menossa olla 1, koska se on nyt vanhin osa meillä on jono, koska olemme jo poistettu 28, joka oli entinen vanhin elementti. 

Ja nyt haluamme muuttaa koko jonon kahteen elementtejä kolmen sijaan. Nyt muistaa aiemmin sanoin, kun haluat lisätä elementtejä jono, me laittaa se joukko paikalla joka on summa etu- ja koosta. Joten tässä tapauksessa, olemme yhä laskemisesta se, seuraava osa jonossa, osaksi array sijainti 3, ja näemme, että toinen. 

Joten olemme nyt dequeued meidän ensimmäisen elementin jonosta. Tehdään se uudestaan. Katsotaanpa poistaa toinen elementti jonosta. Vuonna tapauksessa nykyinen vanhin elementti on array paikka 1. Sitähän q.front kertoo. Että vihreän laatikon kertoo, että se vanhin elementti. Ja niin, X tulee 33. Me vain eräänlainen unohtaa että 33 olemassa jono, ja me sanomme, että nyt, uusi vanhin elementti jonossa on joukko sijainti 2, ja koko jonossa, elementtien määrä meillä on jonossa, on 1. Nyt laittaa jonoon jotain, ja minä eräänlainen antoi tämän pois toinen sitten, mutta jos haluamme laittaa 40 osaksi jono, jossa on 40 menossa? No olemme laittoi pallon vuonna q.front plus jonossa koko, ja niin on järkevää todella laittaa 40 tänne. Nyt huomaa, että jossain vaiheessa, aiomme päästä loppuun meidän valikoima sisällä q, mutta hiipui pois 28 ja 33-- he todella, teknisesti aukiot, eikö? Ja niin, voimme eventually-- että sääntö lisätä nämä kaksi together-- me voi lopulta täytyy mod koon kapasiteetin jotta voimme Ulottumamitan. 

Joten jos saamme elementtiin numero 10, jos olemme korvaamalla se elementti numero 10, olimme tosiasiallisesti se array sijainti 0. Ja jos me aioimme array location-- anteeksi, jos lisäsimme niitä yhteen, ja saimme numero 11 olisi, jos olisimme laittaa se, joka ei ole tässä array-- se olisi menossa ulos pelikentältä. Voisimme mod 10 ja laittaa se array paikka 1. Niin, että miten jonot toimivat. He aina mene vasemmalta oikealle ja mahdollisesti kääri ympärille. Ja te tiedätte, että he täysi jos koko, että punainen laatikko, tulee yhtä suuri kapasiteetti. Ja niin sen jälkeen olemme lisänneet 40 jono, hyvin mitä meidän täytyy tehdä? No, vanhin elementti jonossa on edelleen 19, joten emme halua muuttaa jonon, mutta nyt meillä on kaksi elementtejä jonossa, ja niin haluamme lisätä meidän koko 1-2. 

Se on aika paljon se kanssa array-pohjainen jonot, ja samanlainen pino, on myös tapa toteuttamaan jono linkitettynä listana. Nyt jos tämä tieto rakenne tyyppi näyttää tutulta, se on. Se ei ole yksin linkitetyn listan, se on kaksin verroin linkitetty lista. Ja nyt, koska syrjään, se on todella mahdollista toteuttaa jono kuin yksittäin linkitetty lista, mutta Mielestäni kannalta visualisointi, se todella voi auttaa katsella tätä kaksin verroin linkitetty lista. Mutta se on ehdottomasti mahdollista tehdä tämän yksin linkitetyn listan. 

Joten vilkaista mitä tämä voisi näyttää. Jos haluamme enquue-- niin nyt, jälleen olemme vaihtamalla linkitetty-lista mallia täällä. Jos haluamme laittaa jonoon, haluamme lisätä uusi elementti, hyvin mitä meidän täytyy tehdä? No, ensinnäkin, koska lisäämme loppuun ja poistamalla alkaa, emme todennäköisesti haluavat säilyttää viitteitä sekä pää ja pyrstö linkitetyn listan? Häntä on toinen termi loppuun linkitetyn listan, viimeinen elementti linkitetty lista. Ja nämä luultavasti, uudelleen, hyödyttää meitä jos ne ovat globaaleja muuttujia. Mutta nyt jos haluamme lisätä uuden elementti mitä meidän täytyy tehdä? Mitä me vain [? Malak?] tai dynaamisesti kohdentaa uusi solmu itsellemme. Ja sitten, aivan kuten silloin yhdenkään elementti kaksinkertaisesti linkitetty lista me, vain lajitella of-- Nuo viimeiset kolme vaihetta täällä ovat vain kaikki muuttoa viitteitä oikealla tavalla niin että elementti saa lisätä ketju rikkomatta ketjua tai tehdä jonkinlainen virhe tai ottaa jonkinlainen onnettomuus tapahtua jolloin me vahingossa orpo joitakin osia meidän jonossa. Tässä mitä tämä voisi näyttää. Haluamme lisätä elementtiin 10 loppuun tämän jonon. Joten vanhin elementti täällä edustaa pää. Se on ensimmäinen asia laitoimme tähän hypoteettinen jono täällä. Ja hännän, 13, on kaikkein viimeksi lisätyt elementti. Joten jos haluamme laittaa jonoon 10 kielelle tämä jono, haluamme laittaa sen jälkeen 13. Ja niin aiomme dynaamisesti jakaa tilaa uusi solmu ja tarkista for varmistaa meillä ei ole muisti vika. Sitten aiomme pannaan 10 tuohon solmu, ja nyt meidän on oltava varovainen miten järjestämme osoittimet joten emme katkaisemiseksi. 

Voimme asettaa 10: n edellinen kenttä osoittamaan takaisin vanhaan häntää, ja koska '10 on uusi häntä jossain vaiheessa mennessä kaikki nämä ketjut on kytketty, mikään ei tulossa kun 10 nyt. Ja niin 10 seuraava osoitin tulee kohta null, ja sitten kun me teemme tämän, kun olemme liitetty 10 taaksepäin ketjun, voimme ottaa vanha pää, tai tekosyy minua, vanha hännän jonossa. Vanha jonon, 13, ja sen osoittamaan 10. Ja nyt, tässä vaiheessa, olemme enqueued numero 10 tähän jonoon. Kaikki meidän täytyy tehdä nyt on vain siirtää tail viitata 10 sijasta 13. 

Dequeuing on oikeastaan hyvin samankaltainen popping pinosta joka on toteutetaan linkitettynä listana jos olet nähnyt pinot video. Meidän tarvitsee vain alkaa alkaa, löytää toinen elementti, vapauttaa ensimmäinen elementti, ja sitten siirtyä pää osoittamaan toinen elementti. Luultavasti parempi visualisoida sitä vain olla erityisen selkeä siitä. Joten tässä on meidän jono uudelleen. 12 on vanhin elementti meidän jonossa, pää. 10 on uusin elementti meidän jonossa, meidän häntä. 

Ja niin kun haluamme jotta dequeue elementti, haluamme poistaa vanhimman elementti. Joten mitä me teemme? No asetamme läpikäynti osoitin että alkaa pää, ja siirrymme niin, että se viittaa toinen elementti Tämän queue-- jotain sanomalla Trav vastaa trav nuolta, esimerkiksi, siirtyisi trav siellä osoittamaan 15, joka, sen jälkeen kun me dequeue 12, tai sen jälkeen poistamme 12, tulee tulee sitten vanhin elementti. 

Nyt meillä otteen ensimmäinen elementti kautta osoitin pää ja toinen elementti kautta osoitin Trav. Voimme nyt vapaa pää, ja sitten voimme sano mitään tulee ennen 15 enää. Jotta voimme muuttaa 15: n edellinen osoitin osoittamaan null, ja me vain siirtää pään yli. Ja siellä mennään. Nyt meillä on onnistuneesti dequeued 12, ja nyt me on toinen jono 4 elementtejä. Se on aika paljon kaikki on jonoja, molemmat array-pohjainen ja linkitetty-lista perustuu. Olen Doug Lloyd. Tämä on CS 50.