DOUG LLOYD: Så hvis du har set videoen på stakken, Dette er sandsynligvis kommer til at føle ligesom en lille smule af deja vu. Det kommer til at en meget lignende koncept, bare med en lille twist på den. Vi kommer til at tale nu om køer. Så en kø, svarende til en stabel, er en anden form for datastruktur at vi kan bruge til at opretholde data på en organiseret måde. Svarende til en stabel, det kan gennemføres som en matrix eller et koblet liste. I modsætning til en stabel, reglerne som vi bruger til at bestemme når tingene bliver tilføjet og fjernet fra en kø er en lille smule anderledes. I modsætning til en stak, som er en LIFO struktur, sidste ind, først ud, en kø er en FIFO struktur, FIFO, først ind, først ud. Nu køer, har du sandsynligvis have en analogi til køer. Hvis du nogensinde har været i overensstemmelse med en forlystelsespark eller i en bank, der er en slags retfærdighed gennemføre struktur. Den første person i kø ved banken er den første person der får lov til at tale til Teller. 

Det ville være en slags løb til bunden, hvis den eneste måde du fik til at tale med teller på banken var at være den sidste person på linje. Alle ville altid ønsker at være den sidste person på linje, og den person, der var der først der har ventet på et stykke tid, kunne være der i timevis, og timer, og timer før de har en chance for rent faktisk trække nogen penge i banken. Og så køerne er sortering af fairness gennemføre struktur. Men det betyder ikke nødvendigvis, at stakke er en dårlig ting, bare at køer er en anden måde at gøre det. Så igen en kø er først ind, først ud, versus en stak som varer i, først ud. Svarende til en stabel, vi har to operationer at vi kan udføre på køer. Navnene er enqueue, som er at tilføje et nyt element til enden af ​​køen, og dequeue, som er at fjerne den ældste element fra forrest i køen. Så vi kommer til at tilføje elementer på enden af ​​køen, og vi vil fjerne elementer fra forrest i køen. Igen, med stakken, vi tilføjer elementer til toppen af ​​stablen og fjerne elementer fra toppen af ​​stakken. Så med enqueue, er det at tilføje til Til sidst fjernes fra forsiden. Så den ældste ting derinde er altid den næste ting til at komme ud, hvis vi prøver og dequeue noget. 

Så igen, med køer, vi kan array-baserede implementeringer og forbundet listen på grundlag implementeringer. Vi starter igen med Array-baserede implementeringer. Definitionen struktur ser temmelig ens. Vi har en anden matrix der af datatypen værdi, så det kan holde vilkårlige datatyper. Vi igen kommer til at bruge heltal i dette eksempel. 

Og ligesom med vores matrix-baseret stabel gennemførelse, fordi vi bruger en array, vi nødvendigvis har denne begrænsning, at C slags af håndhæver på os, som er, at vi ikke har nogen dynamik i vores evne til at vokse og skrumpe array. Vi er nødt til at beslutte, i begyndelsen hvad der er det maksimale antal ting at vi kan sætte ind i denne kø, og i dette tilfælde, kapacitet ville være nogle pund defineret konstant i vores kode. Og for så vidt angår dette video, er kapaciteten vil være 10. 

Vi har brug for at holde styr på Den forrest i køen så vi ved, hvilke elementer vi ønsker at dequeue, og vi har også brug for at holde styr på noget else-- antallet af elementer at vi har i vores kø. Bemærk vi ikke holde styr af enden af ​​køen, lige størrelsen af ​​køen. Og grunden til, der vil forhåbentlig blive lidt klarere i et øjeblik. Når vi har gennemført denne type definition, vi har en ny datatype kaldet kø, som vi nu kan erklære variabler af denne datatype. Og noget forvirrende, har jeg besluttet at kalde dette kø q, bogstavet q stedet for datatypen q. 

Så her er vores kø. Det er en struktur. Den indeholder tre medlemmer eller tre felter, et array af størrelse KAPACITET. I dette tilfælde, kapacitet er 10. Og dette array er kommer til at holde heltal. I er grøn foran vores køen næste element, der skal fjernes, og i rødt bliver størrelsen af ​​køen, hvor mange elementer er i øjeblikket eksisterende i køen. Så hvis vi siger q.front ligemænd 0, og q.size størrelse lig 0-- vi sætter 0'erne i disse områder. Og på dette punkt, vi er ret meget klar til at begynde at arbejde med vores kø. 

Så den første operation, vi kan udføre, er at enqueue noget, at tilføje et nyt element til enden af ​​køen. Nå, hvad skal vi gøre i det generelle tilfælde? Nå denne funktion enqueue behov at acceptere en pointer til vores kø. Igen, hvis vi havde erklæret vores kø globalt, ville vi ikke behøver at gøre det nødvendigvis, men generelt vi nødt til at acceptere pointers til datastrukturer som dette, for ellers, vi passerer ved value-- vi er passerer i kopier af køen, og så vi faktisk ikke ændrer køen, at vi agter at ændre. 

Den anden ting, den har brug for at gøre, er at acceptere en dataelement i den relevante type. Igen, i dette tilfælde, er det vil være heltal, men du kunne vilkårligt erklære datatype som værdi og bruge denne mere generelt. Det er det element, vi ønsker at enqueue, Vi ønsker at tilføje til slutningen af ​​køen. Så vi faktisk ønsker at placere, at data i køen. I dette tilfælde, at placere den i korrekte placering af vores array, og så ønsker vi at ændre størrelsen af køen, hvor mange elementer, vi har i øjeblikket. 

Så lad os komme i gang. Her er, igen, at generelle formular funktion erklæring for hvad enqueue kunne se ud. Og her går vi. Lad os enqueue antallet 28 ind i køen. Så hvad skal vi gøre? Nå, den forreste del af vores kø er ved 0 og størrelsen af ​​vores kø er på 0, og så vi sandsynligvis ønsker at sætte nummer 28 i arrayelement nummer 0, ikke? Så vi har nu placeret, at derinde. Så nu, hvad har vi brug for at ændre? Vi ønsker ikke at ændre forsiden af ​​køen, fordi vi ønsker at vide, hvad element vi måske nødt til at dequeue senere. Så årsagen til at vi har foran der er en slags en indikator for, hvad der er den ældste ting i arrayet. Nå den ældste ting i array-- i Faktisk er den eneste ting i array højre nu-- er 28, hvilket er ved opstilling placering 0. Så vi ønsker ikke at ændre det grønne nummer, fordi det er den ældste element. Snarere, vi ønsker at ændre størrelsen. Så i dette tilfælde, vi får trinstørrelsen til 1. 

Nu en generel form for ide om, hvor næste element kommer til at gå i en kø er at tilføje disse to tal sammen foran og størrelse, og der vil fortælle dig, hvor den næste element i køen kommer til at gå. Så lad os nu enqueue andet nummer. Lad os Sæt i kø 33. Så 33 kommer til at gå ind matrix placering 0 plus 1. Så i dette tilfælde, det vil at gå ind matrix placering 1, og nu størrelsen af ​​vores køen er 2. 

Igen, vi ikke ændrer forsiden af ​​vores køen, fordi 28 er stadig den ældste element, og vi ønsker at-- når vi til sidst får at dequeuing, fjerne elementer fra denne kø, vi ønsker at vide hvor den ældste element er. Og så vi altid nødt til at opretholde nogle indikator for, hvor det er. Så det er hvad de 0 er der for. Det er, hvad foran er der for. 

Lad os i enqueue endnu element, 19. Jeg er sikker på du kan gætte hvor 19 kommer til at gå. Det kommer til at gå ind i matrix placering nummer 2. Det er 0 plus 2. Og nu størrelsen af ​​vores kø er 3. Vi har 3 elementer i det. Så hvis vi skulle, og vi vil ikke til lige nu, enqueue et andet element, det ville gå ind matrix placering nummer 3, og størrelsen af ​​vores kø ville være 4. Så vi har kø flere elementer nu. Lad os nu begynde at fjerne dem. Lad os dequeue dem fra køen. 

Så ligner pop, som er sortering af analogen af ​​dette for stakke, dequeue nødt til at acceptere en pointer til queue-- igen, medmindre det globalt erklærede. Nu ønsker vi at ændre placeringen af forrest i køen. Det er her, det slags kommer i spil, det forreste variabel, fordi når vi fjerner et element, vi ønsker at flytte det til det næste ældste element. 

Så vi ønsker at mindske størrelsen af ​​køen, og så vil vi returnere værdien der blev fjernet fra køen. Igen, vi ikke ønsker at bare kassere det. Vi formentlig er udvinder det fra queue-- vi er dequeuing det, fordi vi bekymrer os om det. Så vi ønsker denne funktion til at vende tilbage en dataelement af typen værdi. Igen, i dette tilfælde, er et helt tal værdi. 

Så lad os nu dequeue noget. Lad os fjerne et element fra køen. Hvis vi siger, int x lig & q, tegnet q-- igen, det er en pointer til denne q data structure-- hvad element vil blive dequeued? I dette tilfælde, fordi det er en første ind, først ud datastruktur, FIFO, den første ting, vi sætter ind i denne køen var 28, og så i dette tilfælde, vi kommer til at tage 28 ud af køen, ikke 19, hvilket er, hvad vi ville have gjort, hvis det var en stak. Vi kommer til at tage 28 ud af køen. 

Svarer til, hvad vi gjorde med en stak, men vi er faktisk ikke ved at slette 28 fra køen selv, vi bare at slags af lade som om det ikke er der. Så det kommer til at blive der i hukommelsen, men vi er bare kommer til at slags ignorere det ved at flytte de to andre områder af vores q data struktur. Vi kommer til at ændre fronten. Q.front nu kommer til at være 1, fordi der nu er den ældste element, vi har i vores kø, fordi vi allerede har fjernet 28, som var den tidligere ældste element. 

Og nu, vi ønsker at ændre størrelsen af ​​køen til to elementer i stedet for tre. Husk nu tidligere sagde jeg, da vi ønsker at tilføje elementer til køen, vi sætte det i et array placering som er summen af ​​den forreste og størrelse. Så i dette tilfælde, er vi stadig sætte det, det næste element i køen, i matrix Sted 3, og Vi vil se, at i en anden. 

Så vi har nu dequeued vores første element fra køen. Lad os gøre det igen. Lad os fjerne en anden element fra køen. I tilfælde, den nuværende ældste element er matrix placering 1. Det er, hvad q.front fortæller os. Det grønne boks fortæller os, at det er den ældste element. Og så vil x blive 33. Vi vil bare slags glemmer at 33 findes i arrayet, og vi vil sige, at nu, at nye ældste element i køen er matrix placering 2, og størrelsen i køen, antallet af elementer vi har i køen, er 1. Lad os nu enqueue noget, og jeg slags gav dette væk et sekund siden, men hvis vi ønsker at sætte 40 ind i kø, hvor er 40 kommer til at gå? Godt vi har været at sætte det i q.front plus køstørrelsen, og så det giver mening at faktisk at sætte 40 her. Nu bemærke, at på et tidspunkt, vil vi at komme til udgangen af vores matrix inde i q, men det falmede ud 28 og 33-- de er faktisk, teknisk åbne rum, ikke? Og så kan vi eventually-- denne regel for at tilføje de to together-- vi kan i sidste ende skal mod ved størrelsen af ​​kapaciteten så vi kan wrap omkring. 

Så hvis vi kommer til element nummer 10, hvis vi er erstatte det i element nummer 10, vi havde faktisk sætte det i matrix placering 0. Og hvis vi skulle vifte Beliggende- undskyld mig, hvis vi tilføjet dem op sammen, og vi fik til nummer 11 ville være, hvor vi ville have til at sætte det, som ikke findes i denne array-- Det ville være at gå ud af banen. Vi kunne MoD med 10 og lægge det i matrix placering 1. Så det er sådan køer virker. De er altid kommer til at gå fra venstre til højre og muligvis wrap omkring. Og du ved, at de er fuld, hvis størrelse, at røde felt, bliver lig med kapaciteten. Og så efter vi har tilføjet 40 til den kø, godt hvad skal vi gøre? Nå, den ældste element i køen er stadig 19, så vi ikke ønsker at ændre forsiden af ​​køen, men nu har vi to elementer i køen, og så vi ønsker at øge vores størrelse fra 1 til 2. 

Det er temmelig meget det med arbejder med array-baserede køer, og lignende til at stable, Der er også en måde at gennemføre en kø som sammenkædet liste. Nu, hvis disse data strukturtype ser bekendt for dig, det er. Det er ikke en enkeltvis linket liste, det er en dobbelt linket liste. Og nu, som en sidebemærkning, er det faktisk er muligt at gennemføre en kø som et enkelt bundet liste, men Jeg tænker i visualisering, det rent faktisk kan bidrage til at se dette som en dobbelt sammenkædet liste. Men det er absolut muligt at gøre dette som en enkelt bundet listen. 

Så lad os få et kig på hvad det kunne se ud. Hvis vi ønsker at enquue-- så nu, igen er vi skifte til en sammenkædet liste baseret model her. Hvis vi ønsker at enqueue, vi ønsker at tilføje et nyt element, godt hvad skal vi gøre? Nå, først og fremmest fordi vi tilføjer til enden og fjernelse fra begynder, vi sandsynligvis ønsker at opretholde pegepinde til både hoved og halen af ​​linkede liste? Hale er et andet ord for slutningen af ​​linkede liste, det sidste element i den linkede liste. Og disse vil formentlig, igen, være til gavn for os hvis de er globale variabler. Men nu, hvis vi ønsker at tilføje en ny element hvad har vi at gøre? Det, vi bare [? Malak?] eller dynamisk allokere vores nye node for os selv. Og så, ligesom når vi tilføje element til en dobbelt sammenkædet liste vi, bare nødt til at sortere of-- de tre sidstnævnte trin her er bare alt om at flytte pejlemærker i den korrekte måde således at elementet bliver tilføjet til kæden uden at bryde kæden eller gøre en slags fejl eller har en slags ulykker ske, hvorved vi ved et uheld forældreløs nogle elementer i vores kø. Her er, hvad det kan se ud. Vi ønsker at tilføje elementet 10 til enden af ​​denne kø. Så den ældste element her er repræsenteret ved hovedet. Det er den første ting, vi sætter i dette hypotetiske kø her. Og hale, 13, er den mest nylig tilføjet element. Og så hvis vi ønsker at enqueue 10 ind denne kø, vi ønsker at sætte det efter 13. Og så vil vi dynamisk allokere plads til en ny node og kontrollere for null for at sikre, vi ikke har en hukommelse fiasko. Så vi kommer til at placere 10 i dette knudepunkt, og nu er vi nødt til at være forsigtige om, hvordan vi organiserer pegepinde så vi ikke bryde kæden. 

Vi kan sætte 10 tidligere felt at pege tilbage til det gamle hale, og da '10 vil blive nye hale på et tidspunkt på det tidspunkt alle disse kæder er forbundet, intet kommer til at komme efter 10 lige nu. Og så 10 næste pointer vil pege til null, og derefter efter vi gør det, efter at vi har tilsluttet 10 bagud til kæden, vi kan tage det gamle hoved, eller, undskyldning mig, den gamle hale i køen. Den gamle ende af køen, 13, og gøre det peger på 10. Og nu, på dette tidspunkt, har vi kø nummer 10 i denne kø. Alt, hvad vi skal gøre nu er bare at flytte hale til at pege på 10 i stedet for til 13. 

Dequeuing er faktisk meget lig popping fra en stak, der er implementeret som en sammenkædet liste hvis du har set den stakke video. Alt, hvad vi skal gøre, er at starte på begynder, find det andet element, frigøre det første element, og derefter flytte hovedet til at pege på det andet element. Sandsynligvis bedre at visualisere det bare for at være ekstra klar over det. Så her er vores kø igen. 12 er den ældste element i vores kø, hovedet. 10 er den nyeste element i vores kø, vores hale. 

Og så når vi ønsker at dequeue et element, Vi ønsker at fjerne det ældste element. Så hvad gør vi? Godt vi sat en traversal pointer der starter i spidsen, og vi flytte det, så det peger på det andet element af denne queue-- noget ved at sige trav lig trav pil næste, for eksempel, ville flytte trav der til at pege på 15, som, efter at vi dequeue 12, eller efter at vi fjerner 12, vil blive den daværende ældste element. 

Nu har vi fået fat på den første element via markøren hovedet og det andet element via markøren trav. Vi kan nu gratis hoved, og så kan vi siger intet kommer før den 15. længere. Så vi kan ændre 15 tidligere pointer til at pege til null, og vi bare flytte hovedet over. Og der går vi. Nu har vi med succes dequeued 12, og nu er vi har en anden kø af 4 elementer. Det er temmelig meget alle der er at køer, både matrix-baserede og forbundet-liste baseret på. Jeg er Doug Lloyd. Dette er CS 50.