DOUG LLOYD: Så om du har såg videon på stacken, Detta är förmodligen kommer att känna som en liten bit av deja vu. Det kommer att en mycket liknande koncept, bara med en liten twist på det. Vi kommer att prata nu om köer. Så en kö, som liknar en stapel, är en annan typ av datastruktur att vi kan använda för att upprätthålla data på ett organiserat sätt. Liknar en stapel, det kan genomföras som en matris eller en länkad lista. Till skillnad från en stapel, regler som vi använder för att avgöra När det blir till och tas bort från en kö är lite annorlunda. Till skillnad från en stapel, som är en LIFO-struktur, sist in, först ut, är en kö en FIFO struktur, FIFO, först in, först ut. Nu köer, du förmodligen har en analogi med köer. Om du någonsin har varit i linje med en nöjespark eller en bank, Det är typ av en så kallad fairness genomförandestruktur. Den första personen i kön på banken är den första personen vem som får tala till teller. 

Det skulle vara en slags tävling till botten om det enda sättet du fick tala med teller vid bank skulle vara den sista personen i kön. Alla skulle alltid vill att vara den sista personen i linje, och den person som var där först som har väntat på ett tag, kunde vara där i timmar, och timmar och timmar innan de har en chans att faktiskt återkalla några pengar på banken. Och så köer är typ av rättvisa genomförandestruktur. Men det betyder inte nödvändigtvis att staplar är en dålig sak, bara att köerna är ett annat sätt att göra det. Så återigen en kö är först in, först ut, jämfört med en stapel som sist in först ut. Liknar en stapel, Vi har två operationer att vi kan utföra på köer. Namnen är enqueue, vilket är att tillsätta ett nytt element till slutet av kön, och avköa, vilket är för att ta bort det äldsta elementet från framsidan av kön. Så vi kommer att lägga till element på änden av kön, och vi kommer att ta bort element från framsidan av kön. Återigen, med stapeln, vi tillsätta element till toppen av stacken och ta bort element från toppen av stacken. Så med enqueue, det bidrar till slutet, avlägsnande från fronten. Så äldsta sak där är alltid nästa sak att komma ut om vi försöker och avköa något. 

Så återigen, med köer, vi kan arraybaserade implementeringar och länkade lista baserad implementationer. Vi börjar igen med array-baserade implementeringar. Definitionen strukturen ser ganska likartade. Vi har en annan array det av datatyp värde, så det kan hålla godtyckliga datatyper. Vi återigen kommer att använda heltal i detta exempel. 

Och precis som med vår array-baserade stack genomförandet, eftersom vi använder en array, vi nödvändigtvis har denna begränsning att C typ av upprätt på oss, som är vi har inte någon dynamik i vår förmåga att växa och krympa arrayen. Vi måste bestämma i början vad som är det maximala antal saker att vi kan sätta in detta kö, och i detta fall, kapacitet skulle vara någon pund definierad konstant i vår kod. Och för detta video, kapaciteten kommer att bli 10. 

Vi måste hålla reda på framsidan av kön så vi vet vilket element Vi vill avköa, och vi måste också hålla reda på något else-- antalet element som vi har i vår kö. Lägg märke till att vi inte hålla reda i slutet av kön, bara storleken på kön. Och anledningen till det kommer förhoppningsvis blivit lite tydligare i ett ögonblick. När vi har avslutat denna definition typ, vi har en ny datatyp kallas kö, som vi kan nu deklarera variabler av den datatypen. Och något förvirrande, har jag beslutat att kalla detta kö q, bokstaven q i stället för datatypen q. 

Så här är vår kö. Det är en struktur. Den innehåller tre ledamöter eller tre fält, en matris med storlek kapacitet. I det här fallet är KAPACITET 10. Och denna matris är kommer att hålla heltal. I grönt är framsidan av vår kö, den nästa element som skall avlägsnas, och i rött kommer att vara storleken på kön, hur många element är närvarande existerande i kön. Så om vi säger q.front jämlikar 0, och q.size storlek lika 0-- vi sätter 0s i dessa områden. Och på denna punkt, vi är ganska mycket redo att börja arbeta med vår kö. 

Så den första operationen kan vi göra är att köa något, att lägga ett nytt element i slutet av kön. Och vad behöver vi göra i det allmänna fallet? Väl denna funktion köa behov att acceptera en pekare till vår kö. Återigen, om vi hade förklarat vår kö globalt, Vi skulle inte behöva göra detta nödvändigtvis, men i allmänhet, vi måste acceptera pekare till datastrukturer så här, för annars, vi passerar value-- vi är passerar i kopior av kö, och så att vi inte är faktiskt förändras kön som vi har för avsikt att ändra. 

Den andra saken som behövs för att göra är acceptera ett dataelement av lämplig typ. Återigen, i detta fall är det kommer att vara heltal, men du kunde godtyckligt förklara datatyp som värdet och använda denna mer allmänt. Det är elementet vill vi köa, vi vill lägga till i slutet av kön. Då kan vi verkligen vill Placera att data i kön. I det här fallet, placera den i korrekt placering av vår samling, och sedan vill vi ändra storlek av kön, hur många element vi för närvarande har. 

Så låt oss komma igång. Här är återigen den allmänna formulär funktionsdeklarationen för vad enqueue kan se ut. Och nu kör vi. Låt oss köa numret 28 in i kön. Så vad ska vi göra? Tja, är framsidan av vår kö vid 0, och storleken på vår kö är 0, och så vill vi nog sätta antalet 28 i array elementnummer 0, eller hur? Så vi har nu lagt det där. Så nu vad vi behöver ändra? Vi vill inte ändra framsidan av kön, eftersom vi vill veta vad elementet Vi kanske behöver avköa senare. Så anledningen till att vi har framsidan finns är typ av en indikator på vad som är det äldsta sak i arrayen. Tja äldsta sak i array-- i Faktum är att den enda i gruppen rätt now-- är 28, som är på array plats 0. Så vi vill inte ändra på det gröna nummer, eftersom det är den äldsta elementet. Snarare vill vi ändra storleken. Så i det här fallet, vi ska öka storleken till ett. 

Nu har en allmän slags uppfattning om var nästa element kommer att gå i en kö är att lägga till dessa två siffror tillsammans, fram och storlek, och som kommer att tala om var nästa elementet i kön kommer att gå. Så nu ska vi köa ett annat nummer. Låt oss köa 33. Så 33 kommer att gå in i array plats 0 plus 1. Så i detta fall, det kommer att gå in array plats 1, och nu storleken på vår kö är 2. 

Återigen, vi ändrar inte framsidan av vår kö, eftersom 28 är fortfarande den äldsta elementet, och vi vill att-- när vi får så småningom att dequeuing, ta bort element från denna kö, vill vi veta där den äldsta elementet är. Och så måste vi alltid att behålla någon indikation på var det är. Så det är vad det 0 är där för. Det är vad fronten är där för. 

Låt oss i enqueue ytterligare en beståndsdel, 19. Jag är säker på att du kan gissa där 19 kommer att gå. Det kommer att gå in array plats nummer två. Det är 0 plus två. Och nu storleken på vår kö är 3. Vi har 3 element i den. Så om vi skulle, och vi kommer inte just nu, köa ett annat element, Det skulle gå in array plats nummer 3, och storleken på vår kö skulle vara 4. Så vi har kö flera element nu. Nu börjar ta bort dem. Låt oss avköa dem från kön. 

Så lik pop, som är typ av analogen av denna för staplar, dequeue måste acceptera en pekare till queue-- igen, om det inte är globalt deklarerade. Nu vill vi ändra platsen av den främre delen av kön. Det är här det slags kommer i spelet, den fronten variabel, eftersom när vi tar bort ett element, vill vi att flytta den till den näst äldsta elementet. 

Då kan vi vill minska storleken på kön, och sedan vill vi att returnera värdet som togs bort från kön. Återigen, vill vi inte bara kasta det. Vi förmodligen utvinner det från queue-- vi dequeuing det eftersom vi bryr oss om det. Så vi vill här funktionen för att återvända en dataelement av typen värde. Återigen, i det här fallet, är värdet heltal. 

Så nu ska vi avköa något. Låt oss ta bort ett element från kön. Om vi ​​säger int x lika & q,-tecken q-- igen som är en pekare till denna q uppgifter structure-- vad elementet kommer att ur kön? I detta fall, eftersom det är ett första in, först ut datastruktur, FIFO, det första vi lagt ned på detta kön var 28, och så i detta fall, vi kommer att ta 28 av kön, inte 19, vilket är vad vi skulle ha gjort om det var en stapel. Vi kommer att ta 28 av kön. 

I likhet med vad vi gjorde med en bunt, kan vi faktiskt inte kommer att ta bort 28 ur kön i sig, Vi kommer bara att typ av låtsas att det inte finns. Så det kommer att stanna kvar i minnet, men vi är bara kommer att typ av ignorera det genom att flytta de andra två områden av vår Q-data struktur. Vi ska ändra på framsidan. Q.front kommer nu att vara en, eftersom det är nu den äldsta elementet vi har i vår kö, eftersom vi redan har tagit bort 28, som var den tidigare äldsta elementet. 

Och nu vill vi ändra storleken på kön till två element i stället för tre. Nu minns tidigare sagt jag när vi vill lägga till element i kön, Vi lägger det i en array plats som är summan av främre och storlek. Så i det här fallet, är vi fortfarande sätta det, nästa element i kön, i array plats 3, och Vi ser att i en sekund. 

Så vi har nu ur kön vår första element från kön. Låt oss göra det igen. Låt oss ta en annan elementet från kön. I fallet, den nuvarande äldsta elementet är array plats 1. Det är vad q.front berättar. Det gröna rutan berättar att det är det äldsta elementet. Och så kommer x att bli 33. Vi ska bara slags glömma att 33 existerar i arrayen, och vi kommer att säga att nu, den ny äldsta elementet i kön är array plats 2, och storleken av kön, antalet element vi har i kön, är 1. Nu ska köa något, och jag sorts gav detta bort en sekund sedan, men om vi vill sätta 40 i kö, där är 40 kommer att gå? Jo vi har skjutit det i q.front plus köstorleken, och så är det klokt att faktiskt sätta 40 här. Nu märker att åtmin någon gång kommer vi att komma till slutet av vår samling inne i q, men det tonas ut 28 och 33-- de är faktiskt, tekniskt öppna ytor, eller hur? Och så kan vi eventually-- denna regel att lägga dessa två together-- vi kan så småningom behöver mod av storleken på kapacitet så att vi kan linda runt. 

Så om vi får till elementet nummer 10, om vi är ersätta den i elementet nummer 10, skulle vi faktiskt lägga den i array plats 0. Och om vi skulle array location-- ursäkta mig, om vi lagt upp dem tillsammans, och vi fick till nummer 11 skulle vara där vi skulle behöva sätta den, vilket inte existerar i denna array-- Det skulle vara att gå out of bounds. Vi kunde mod med 10 och sätta det array plats 1. Så det är hur köerna fungerar. De kommer alltid att gå från vänster till höger och eventuellt lindas runt. Och du vet att de är full om storlek, att röd ruta, blir lika med kapaciteten. Och så när vi har lagt 40 till kö, och vad behöver vi göra? Tja, det äldsta elementet i kön är fortfarande 19, så att vi inte vill ändra framsidan av kön, men nu har vi två element i kön, och så vi vill öka vår storlek 1-2. 

Det är ganska mycket det med arbeta med arraybaserade köer, och liknande att stapla, det är också ett sätt att implementera en kö som en länkad lista. Nu om denna datastruktur typ ser bekant för dig, är det. Det är inte en enskilt länkad lista, Det är en dubbelt länkad lista. Och nu, som en sidoreplik, är det faktiskt är möjligt att genomföra en kö som ett enskilt länkad lista, men Jag tänker i termer av visualisering, det faktiskt kan bidra till att visa detta som en dubbellänkad lista. Men det är definitivt möjligt att gör detta som ett enskilt länkad lista. 

Så låt oss ta en titt på vad detta kan se ut. Om vi ​​vill enquue-- så nu, återigen vi är byta till en länkad-lista baserad modell här. Om vi ​​vill köa, vi vill att lägga ett nytt element, och Vad behöver vi göra? Jo, först och främst, eftersom Vi lägger till slutet och avlägsnande från början, vi förmodligen vill behålla pekare till både huvudet och svansen på den länkade listan? Tail är en annan term för I slutet av den länkade listan, det sista elementet i den länkade listan. Och dessa kommer förmodligen, igen, vara till nytta för oss om de är globala variabler. Men nu om vi vill lägga till en ny elementet vad har vi att göra? Vad vi bara [? Malak?] eller dynamiskt fördela vår nya noden för oss själva. Och sedan, precis som när vi lägger något elementet till en dubbellänkad lista som vi, bara att sortera of-- dessa tre sista stegen här är bara handlar om att flytta pekare på rätt sätt så att elementet läggs till kedjan utan att bryta kedjan eller göra någon form av misstag eller har någon form av olycka hända där vi av misstag överge vissa delar av vår kö. Här är vad detta skulle kunna se ut. Vi vill lägga till elementet 10 till slutet av denna kö. Så den äldsta elementet här representeras av huvudet. Det är det första vi lägger in i detta hypotetiska kö här. Och svans, 13, är den mest nyligen lagt element. Och så om vi vill köa 10 i denna kö, vill vi uttrycka det efter 13. Och så vi kommer att dynamiskt allokera utrymme för en ny nod och kontrollera null för att se vi har inte ett minnesfel. Då vi kommer att placera 10 till denna nod, och nu måste vi vara försiktiga om hur vi organiserar pekare så att vi inte bryter kedjan. 

Vi kan sätta 10 tidigare fält att peka tillbaka till den gamla svansen, och sedan '10 kommer att vara ny svans vid något tillfälle vid tiden alla dessa kedjorna är anslutna, ingenting kommer att komma efter 10 just nu. Och så 10 nästa pekare kommer att peka på null, och sedan när vi gör detta, efter att vi har anslutna 10 bakåt till kedjan, vi kan ta den gamla huvudet, eller ursäkt mig, den gamla svansen hos kön. Den gamla slutet av kön, 13, och gör det pekar på 10. Och nu, på denna punkt, vi har kö nummer 10 i denna kö. Allt vi behöver göra nu är bara att flytta svans för att peka på 10 i stället för till 13. 

Dequeuing är faktiskt mycket lik popping från en stapel som är implementeras som en länkad lista Om du har sett staplar video. Allt vi behöver göra är att börja på början, hitta den andra delen, frigöra det första elementet, och sedan flytta huvudet att peka på det andra elementet. Förmodligen bättre för att visualisera det bara för att vara extra tydlig med det. Så här är vår kö igen. 12 är det äldsta elementet i vår kö, huvudet. 10 är den nyaste elementet i vår kö, vår svans. 

Och så när vi vill att avköa ett element, vi vill ta bort det äldsta elementet. Så vad gör vi? Jo vi sätter ett genomgångs pekare som börjar i spetsen, och vi flyttar den så att den pekar på det andra elementet av detta queue-- något genom att säga trav lika trav pilen bredvid, till exempel, skulle flytta trav där för att peka på 15, som, efter att vi avköa 12, eller när vi tar bort 12, kommer blir den då äldsta elementet. 

Nu har vi fått tag på den första elementet via pekaren huvudet och det andra elementet via pekaren trav. Vi kan nu gratis huvud, och då kan vi säger ingenting kommer före den 15 längre. Så vi kan ändra 15 tidigare pekare att peka på null, och vi rör oss bara huvudet över. Och det går vi. Nu har vi framgångsrikt ur kön 12, och nu är vi har en annan kö av 4 element. Det är ganska mycket alla Det finns köer, både array-baserade och länkade lista baserad. Jag är Doug Lloyd. Detta är CS 50.