DOUG LLOYD: Dus als je hebt keek naar de video op stapel, Dit is waarschijnlijk te voelen als een beetje van deja vu. Het gaat om een ​​zeer vergelijkbaar concept, alleen met een lichte draai aan het. We gaan nu over wachtrijen. Dus een wachtrij, gelijkend op een stapel, is een ander soort gegevensstructuur die we kunnen gebruiken om te behouden data op een georganiseerde manier. Net als een stapel, het kan worden toegepast als een matrix of een gekoppelde lijst. In tegenstelling tot een stapel, de regels die we gebruiken om te bepalen wanneer dingen toegevoegd en verwijderd uit een wachtrij zijn een beetje anders. In tegenstelling tot een stapel, die een LIFO structuur last in, first out, een wachtrij is een FIFO structuur, FIFO, first in, first out. Nu wachtrijen, u waarschijnlijk hebben een analogie met wachtrijen. Als je ooit in de lijn geweest bij een pretpark of bij een bank, er is een soort van een fairness uitvoeringsstructuur. De eerste persoon in de rij bij de bank is de eerste persoon wie krijgt om de teller te spreken. 

Het zou een soort van race naar beneden als de enige manier je moet de teller bij het spreken bank was de laatste persoon in de rij zijn. Iedereen zou willen altijd om de laatste persoon in de rij, en de persoon die als eerste was er die heeft gewacht voor een tijdje, zou er voor uren, en uren en uren voordat ze een kans hebben om daadwerkelijk geen geld bij de bank te trekken. En zo wachtrijen zijn soort van de billijkheid uitvoeringsstructuur. Maar dat betekent niet noodzakelijk dat stapels zijn een slechte zaak, maar dat de wachtrijen zijn een andere manier om het te doen. Dus nogmaals een wachtrij is first in, first out, tegenover een stapel die last in, first out. Net als een stapel, we hebben twee operaties die we kunnen uitvoeren op wachtrijen. De namen zijn enqueue, dat is toe te voegen een nieuw element aan het einde van de wachtrij, en dequeue, dat is het oudste verwijderen element vanaf de voorkant van de wachtrij. Dus we gaan om elementen toe te voegen op het einde van de wachtrij, en we gaan om elementen te verwijderen vanaf de voorkant van de wachtrij. Opnieuw, met de stack, werden we voegen elementen naar de top van de stack en het verwijderen van onderdelen van de bovenkant van de stapel. Dus met enqueue, is het toe te voegen aan Uiteindelijk verwijderen van voren. Dus de oudste ding er is altijd het volgende ding om uit te komen als we proberen en dequeue iets. 

Dus nogmaals, met wachtrijen, kunnen wij array-gebaseerde implementaties en gekoppeld-lijst gebaseerde implementaties. We zullen weer beginnen met array-gebaseerde implementaties. De structuurdefinitie ziet er redelijk vergelijkbaar. We hebben een andere array er gegevens soort waarde, dus het kan willekeurige data types te houden. We zijn weer gaan gebruiken integers in dit voorbeeld. 

En net als met onze array-gebaseerde stack implementatie, omdat we met behulp van een array, we noodzakelijkerwijs hebben die beperking dat soort C van dwingt ons, die we hebben geen dynamiek in niet onze vermogen om te groeien en krimpen van de array. We moeten beslissen begin Wat is het maximum aantal dingen dat we in deze kunnen zetten wachtrij, en in dit geval, capaciteit zou wat zijn pond gedefinieerde constante in onze code. En voor de toepassing van deze video, wordt vermogen gaat worden 10. 

We moeten houden van de voorkant van de wachtrij zodat we weten welke element we willen dequeue, en we moeten ook bijhouden iets else-- het aantal elementen dat we in onze rij. Merken we niet bijhouden het einde van de wachtrij, net de grootte van de wachtrij. En de reden daarvoor zal hopelijk word een beetje duidelijker in een moment. Zodra we hebben afgerond dit type definitie wij hebben een nieuw type data genaamd wachtrij, die we kunnen nu verklaren variabelen van dat type data. En enigszins verwarrend, heb ik besloten te roepen deze wachtrij q, de letter q in plaats van het type data q. 

Dus hier is onze wachtrij. Het is een structuur. Het bevat drie leden of drie velden, een array van grootte capaciteit. In dit geval, de capaciteit is 10. En deze array is gaat integers te houden. In het groen is de voorkant van onze wachtrij, de volgende element te verwijderen, en rode de grootte van de wachtrij, hoeveel elementen zijn bestaande uit de wachtrij. Dus als we zeggen q.front gelijken 0 en q.size grootte gelijk 0-- We zetten 0s in die gebieden. En op dit punt, we zijn vrij veel klaar om te beginnen werken met onze wachtrij. 

Dus de eerste operatie kunnen we uit te voeren is om iets enqueue, een nieuw element aan het einde van de wachtrij. Nou wat hebben we nodig om te doen in het algemene geval? Nou deze functie enqueue behoeften een pointer naar onze wachtrij accepteren. Nogmaals, als we had verklaard onze wachtrij wereldwijd, zouden we niet nodig om dit te doen se, maar in het algemeen, we moeten pointers accepteren datastructuren als dit, want anders, we langs value-- we passeren in kopieën van de wachtrij, en zo zijn we eigenlijk niet veranderen de rij die we willen veranderen. 

De andere wat het moet doen is accepteren een data-element van hetzelfde type. Ook in dit geval is het naar gehele getallen, maar je kon willekeurig verklaren het type gegevens als waarde en deze meer in het algemeen. Dat is het element dat we willen enqueue, we willen toevoegen aan het einde van de wachtrij. Dan eigenlijk willen we plaatst die gegevens in de wachtrij. In dit geval, te plaatsen in de juiste locatie van ons aanbod, en dan willen we de grootte te veranderen van de wachtrij, hoeveel elementen we momenteel. 

Dus laten we aan de slag. Hier is, nogmaals, dat de algemene vorm functie verklaring voor wat enqueue eruit zou kunnen zien. En hier gaan we. Laten enqueue het aantal 28 in de wachtrij. Dus wat gaan we doen? Nou, de voorkant van onze wachtrij op 0, en de grootte van onze wachtrij is op 0, en dus willen we waarschijnlijk te zetten de nummer 28 in de array-element nummer 0, toch? Dus we hebben nu geplaatst dat daar. Dus nu wat hebben we nodig om te veranderen? We willen niet veranderen de voorkant van de wachtrij, omdat we willen weten wat element we zouden moeten later dequeue. Dus de reden dat we er vooraan is een soort van een indicator van wat er de oudste ding in de array. Nou, de oudste zaak van de array-- in Sterker nog, het enige wat in de array juiste now-- is 28, wat in serie locatie 0. Dus we willen niet veranderen groen nummer, want dat is de oudste element. Integendeel, we willen de grootte te veranderen. Dus in dit geval, zullen we increment grootte 1. 

Nu een algemene soort idee van waar de volgende element gaat om te gaan in een wachtrij is om deze twee nummers toe te voegen samen voorzijde en grootte, en dat zal u vertellen waar de volgende element in de wachtrij zal gaan. Dus laten we nu enqueue ander nummer. Laten enqueue 33. Dus 33 is in te gaan op om te gaan scala locatie 0 plus 1. Dus in dit geval, het gaat in de serie locatie 1 te gaan, en nu de omvang van onze wachtrij is 2. 

Nogmaals, we zijn niet veranderen de voorzijde van onze wachtrij, omdat 28 blijft de oudste element, en we willen to-- toen we uiteindelijk krijgen dequeuing te verwijderen elementen uit deze wachtrij, willen we weten waarbij het oudste element. En dus moeten we altijd behouden enkele indicator van de plaats waar dat is. Dus dat is wat de 0 is er voor. Dat is wat de voorkant is er voor. 

Laten we in enqueue één element, 19. Ik weet zeker dat je kan raden waar de 19 zal gaan. Het gaat in te gaan scala locatie nummer 2. Dat is 0 plus 2. En nu de omvang van onze wachtrij is 3. We hebben 3 elementen daarin. Dus als we, en we gaan niet om nu, enqueue een ander element, het zou in serie locatie gaan nummer 3, en de grootte van onze wachtrij zou 4. Daarom hebben we een aantal elementen enqueued nu. Laten we nu eens beginnen om ze te verwijderen. Laten dequeue ze uit de wachtrij. 

Dus vergelijkbaar met pop, dat is een soort van de analoog daarvan voor stapels, dequeue moet een accepteren wijzer naar het queue-- weer, tenzij het wereldwijd is verklaard. Nu willen we de locatie te veranderen van de voorkant van de wachtrij. Dit is waar het vandaan komt soort in het spel, dat voor de variabele, want zodra we verwijderen een element, we willen om het te verplaatsen naar de volgende oudste element. 

Dan willen we verlagen de grootte van de wachtrij, en dan willen we de waarde terug die is verwijderd uit de wachtrij. Nogmaals, willen we niet gewoon gooi hem weg. We vermoedelijk zijn extraheren het uit de queue-- we dequeuing het omdat we de zorg over het. Dus we willen deze functie terug te keren een data-element van het type waarde. Ook in dit geval waarde integer. 

Dus laten we nu dequeue iets. Laten we het verwijderen van een element uit de wachtrij. Als we zeggen int x evenaart & q, ampersand q-- nogmaals, dat is een verwijzing naar deze q gegevens structure-- wat element zal worden dequeued? In dit geval, omdat het een eerste in, first out datastructuur, FIFO, het eerste wat we in dit gezet wachtrij was 28, en dus in dit geval, we gaan nemen 28 van de de wachtrij, niet 19, wat we zouden hebben gedaan als dit was een stapel. We gaan nemen 28 uit de wachtrij. 

Vergelijkbaar met wat we hebben gedaan met een stapel, we zijn niet echt gaan verwijderen 28 uit de wachtrij zelf, we gaan gewoon om vriendelijk van te doen alsof het er niet is. Dus het gaat om daar te blijven in het geheugen, maar we zijn gewoon gaat soort negeren door het bewegen de andere twee gebieden van onze q data structuur. We gaan naar het front te veranderen. Q.front gaat nu 1 zijn, omdat nu de oudste element hebben wij in onze wachtrij, omdat we al hebt verwijderd 28, dat was de voormalige oudste element. 

En nu willen we veranderen de grootte van de wachtrij twee elementen in plaats van drie. Nu herinner ik eerder gezegd toen we wilt elementen toe te voegen aan de wachtrij, we zetten in een array locatie waarbij de som van de voorste en grootte. Dus in dit geval, zijn we nog steeds zetten het, het volgende element in de wachtrij, in serie locatie 3, en we zullen zien dat in een tweede. 

Dus we hebben nu onze dequeued eerste element uit de wachtrij. Laten we het nog eens doen. Laten we een ander te verwijderen element uit de wachtrij. In het geval van de huidige oudste element serie locatie 1. Dat is wat q.front ons vertelt. Dat groene doos vertelt ons dat dat is de oudste element. En zo is, zal x 33 geworden. We zullen gewoon een soort van vergeten die 33 bestaat in de array, en we zullen nu zeggen dat de nieuwe oudste element in de wachtrij is op scala locatie 2, en de grootte van de rij, het aantal elementen we hebben in de wachtrij, is 1. Laten we nu enqueue iets, en ik soort gaf deze weg een tweede geleden, maar als we willen in de om te zetten 40 wachtrij, waar is 40 gaat om te gaan? Nou we zijn zetten het in q.front plus wachtrijgrootte, en dus is het zinvol om eigenlijk om hier te zetten 40. Nu merken dat bij een bepaald punt, we gaan aan het einde aan te krijgen ons aanbod binnenkant van q, maar dat vervaagde 28 en 33-- ze zijn eigenlijk, technisch open ruimtes, toch? En zo kunnen we eventually-- die regel toe te voegen die twee together-- we kunnen uiteindelijk mod moet door de grootte van de capaciteit dus we kunnen wikkelen. 

Dus als we naar element nummer 10, als we vervangen in element nummer 10, zouden we eigenlijk zet het in serie locatie 0. En als we zouden gaan scala locatie-- me niet kwalijk, als we toegevoegd ze samen, en we kregen te nummer 11 zou zijn waar we zouden moeten zetten het, die niet bestaat in deze array-- het zou gaan out of bounds. We konden mod 10 en zet in serie locatie 1. Dus dat is hoe wachtrijen werken. Ze altijd gaan om te gaan van links naar rechts en eventueel wikkelen. En je weet dat ze full als de grootte, dat rode doos, gelijk aan de capaciteit. En dus nadat we 40 heeft toegevoegd aan de wachtrij, tja, wat moeten we doen? Nou, de oudste element in de wachtrij nog 19, zodat we niet willen veranderen de voorkant van de wachtrij, maar nu hebben we twee elementen in de wachtrij, en dus willen we verhogen onze grootte 1-2. 

Dat is vrij veel met werken met array-gebaseerde wachtrijen, en dergelijke te stapelen, Er is ook een manier de implementatie van een wachtrij als een gekoppelde lijst. Nu, als dit soort data structuur lijkt u bekend voor, het is. Het is niet een enkelvoudig gelinkte lijst, het is een dubbel gelinkte lijst. En nu, als een terzijde, het is echt mogelijk uit te voeren een wachtrij als een enkelvoudig gelinkte lijst, maar Ik denk in termen van visualisatie, het eigenlijk zou kunnen helpen om te bekijken dit als een dubbel gelinkte lijst. Maar het is zeker mogelijk om doe dit als een afzonderlijk gekoppelde lijst. 

Dus laten we eens een kijkje op wat dit eruit zou kunnen zien. Als we willen enquue-- dus nu weer zijn we overschakelen naar een gekoppelde-lijst gebaseerde hier model. Als we willen enqueue, we willen een nieuw element toe te voegen, goed Wat moeten we doen? Nou, allereerst, omdat we toe te voegen aan het einde en het verwijderen van de begin, we waarschijnlijk willen verwijzingen naar zowel het behouden kop en de staart van de gelinkte lijst? Staart die een andere term voor het einde van de gekoppelde lijst, het laatste element in de gekoppelde lijst. En deze zullen waarschijnlijk, weer gunstig zijn voor ons als ze globale variabelen. Maar nu willen we een nieuwe toe te voegen element wat we moeten doen? Wat we net [? malak?] of dynamisch toewijzen onze nieuwe knooppunt voor onszelf. En dan, net als toen we elke voegen element een dubbel gelinkte lijst wij, gewoon van-- sorteren die laatste drie stappen hier zijn gewoon allemaal over het verplaatsen van de pointers op de juiste wijze zodat het element wordt toegevoegd aan de ketting zonder de ketting of het maken van een soort van fout of het hebben van een soort van ongeval gebeuren waarbij we per ongeluk verweesde sommige elementen van onze wachtrij. Hier is wat dit eruit zou kunnen zien. We willen het element toe te voegen 10 aan het einde van de wachtrij. Dus de oudste element hier wordt vertegenwoordigd door het hoofd. Dat is het eerste wat we zetten in deze hypothetische wachtrij hier. En staart 13, het meest recent toegevoegde element. En dus als we willen enqueue 10 in deze wachtrij, willen we het te zetten na 13. En dus gaan we naar dynamisch toewijzen ruimte voor een nieuw knooppunt en controleer op nul om ervoor te zorgen we hebben geen geheugen mislukking. Dan gaan we Plaats 10 in dat knooppunt, en nu moeten we voorzichtig zijn over hoe organiseren we pointers zodat we niet breken de keten. 

Wij kunnen 10 van de vorige veld instellen om terug te verwijzen naar de oude staart, en aangezien '10 zullen de nieuwe staart op een bepaald punt tegen de tijd al deze kettingen zijn verbonden, niets gaat komen na 10 nu. En zo 10 de volgende pointer zal wijzen op null, en dan nadat we dit doen, nadat we hebben verbonden 10 naar achteren om de keten, kunnen we de oude hoofd, of, excuus nemen me, de oude staart van de wachtrij. Het oude einde van de wachtrij, 13, en maken het wijzen naar 10. Nu, op dit punt, we enqueued het nummer 10 in deze wachtrij. Alles wat we nu moeten doen is gewoon bewegen de staart te wijzen op 10 in plaats van 13. 

Dequeuing is eigenlijk zeer vergelijkbaar met popping een stapel die is geïmplementeerd als een gekoppelde lijst als je de stapels video gezien heb. Alles wat we moeten doen is beginnen bij de begin, vindt het tweede element, bevrijden het eerste element, en verplaats de kop te wijzen aan het tweede element. Waarschijnlijk beter om het te visualiseren alleen maar om extra duidelijk over zijn. Dus hier is onze wachtrij weer. 12 is het oudste element in onze wachtrij, het hoofd. 10 is het nieuwste element in onze rij, onze staart. 

En dus als we willen een element dequeue, we willen de oudste element te verwijderen. Dus wat doen we? Wel stellen we een traversal pointer dat begint bij de kop, en gaan we het zo dat het verwijst naar het tweede element van deze queue-- iets door te zeggen trav gelijk trav pijl naast bijvoorbeeld zou trav daarheen te verhuizen om te wijzen op 15, die, na dequeue 12, of na het verwijderen we 12, zal uitgegroeid tot de toenmalige oudste element. 

Nu hebben we een greep op de eerste element via de pointer kop en het tweede element via de pointer Trav. We kunnen nu gratis hoofd, en dan kunnen we zeggen niets komt voor 15 meer. Dus we kunnen 15 eerdere veranderen pointer om te wijzen op null, en we bewegen het hoofd over. En daar gaan we. Nu met succes hebben we dequeued 12, en nu zijn we nog een rij van 4 elementen. Dat is vrijwel alle er wachtrijen, zowel-array gebaseerde en gekoppeld-lijst op basis. Ik ben Doug Lloyd. Dit is CS 50.