DOUG LLOYD: Så hvis du har sett videoen på stakken, Dette er trolig kommer til å føle seg som en liten bit av déjà vu. Det kommer til et veldig lignende konsept, bare med en liten vri på den. Vi kommer til å snakke nå om køer. Slik at en kø, ligner på en stabel, er en annen form for datastruktur som vi kan bruke til å vedlikeholde data på en organisert måte. I likhet med en stabel, det kan gjennomføres som en matrise eller en lenket liste. I motsetning til en stabel, reglene som vi bruker for å bestemme når ting blir lagt til og fjernet fra en kø er litt annerledes. I motsetning til en stabel, hvilken er en LIFO struktur, sist inn, først ut er en kø en FIFO struktur, FIFO, først inn, først ut. Nå køer, har du sannsynligvis har en analogi til køer. Hvis du noen gang har vært i kø på en fornøyelsespark eller i en bank, det er liksom en fairness implementere struktur. Den første personen i kø på Banken er den første personen hvem som får snakke med fortelleren. 

Det ville være en slags rase til bunnen dersom den eneste måten du fikk til å snakke med teller på banken var å være den siste personen i kø. Alle ville alltid vil å være den siste personen i kø, og personen som var der først som har ventet på en stund, kunne være der i flere timer, og timer, og timer før de har en sjanse til å faktisk ta ut penger i banken. Og så køene er liksom den rettferdighet implementere struktur. Men det betyr ikke nødvendigvis som stabler er en dårlig ting, bare at køene er en annen måte å gjøre det. Så igjen en kø er først inn, først ut, versus en stabel som sist inn, først ut. I likhet med en stabel, vi har to operasjoner at vi kan utføre på køer. Navnene er enqueue, som er å legge et nytt element til slutten av køen, og dequeue, som er for å fjerne den eldste element fra forsiden av køen. Så vi kommer til å legge til elementer på slutten av køen, og vi kommer til å fjerne elementer fra forsiden av køen. Igjen, med bunken, ble vi legger til elementer til toppen av bunken og fjerne elementer fra toppen av bunken. Så med enqueue, det er å legge til Til slutt fjernes fra forsiden. Så den eldste ting der er alltid den neste tingen å komme ut hvis vi prøver og dequeue noe. 

Så igjen, med køer, kan vi arraybaserte implementeringer og knyttet-liste basert implementeringer. Vi starter igjen med arraybaserte implementeringer. Strukturen definisjon ser ganske lik. Vi har et annet utvalg det av datatype verdi, slik at den kan holde vilkårlige datatyper. Vi igjen kommer til å bruke heltall i dette eksempelet. 

Og akkurat som med vår matrise-baserte stabelen implementering, fordi vi bruker en array, vi nødvendigvis har den begrensningen at C slag av håndhever på oss, som er vi har ikke noe dynamikk i vår evne til å vokse og krympe matrisen. Vi må bestemme på begynnelsen hva er det maksimale antall ting at vi kan sette inn i dette kø, og i dette tilfellet kapasiteten vil være noen pund definert konstant i koden vår. Og i forbindelse med denne video, er kapasiteten kommer til å være 10. 

Vi trenger å holde styr på foran i køen slik at vi vet hvilke element vi ønsker å dequeue, og vi må også holde styr på noe else-- antallet elementer som vi har i vår kø. Legg merke vi ikke å holde styr på slutten av køen, bare størrelsen av køen. Og grunnen til det vil forhåpentligvis bli litt klarere i et øyeblikk. Når vi har fullført denne typen definisjon, vi har en ny datatype heter kø, som vi kan nå erklære variabler av den datatypen. Og litt forvirrende, jeg har bestemt meg å kalle denne køen q, bokstaven q istedenfor datatypen q. 

Så her er vår køen. Det er en struktur. Den inneholder tre medlemmer eller tre- felt, en rekke størrelse KAPASITET. I dette tilfellet er KAPASITET 10. Og denne matrisen er kommer til å holde heltall. I grønn er forsiden av vår køen, ved siden av elementet som skal fjernes, og i rødt vil være størrelsen på køen, hvor mange elementer er for tiden eksisterende i køen. Så hvis vi sier q.front equals 0, og q.size størrelse tilsvarer 0-- vi setter 0s inn i disse feltene. Og på dette punktet, er vi ganske mye klar til å begynne å jobbe med våre køen. 

Så den første operasjonen vi kan utføre er å Enqueue noe, å legge til et nytt element til slutten av køen. Vel hva trenger vi å gjøre i det generelle tilfellet? Vel denne funksjonen Enqueue behov å akseptere en peker til vår køen. Igjen, hvis vi hadde erklært vår køen globalt, vi ville ikke trenger å gjøre dette nødvendigvis, men generelt, vi må godta pekere til datastrukturer som dette, fordi ellers vi er forbi value-- vi er passerer i kopier av køen, og så vi ikke faktisk endrer køen som vi har tenkt å endre. 

Den andre tingen den trenger å gjøre er å akseptere et dataelement av riktig type. Igjen, i dette tilfellet, er det kommer til å være heltall, men du kunne vilkårlig erklære datatype som verdi og bruke dette mer generelt. Det er elementet vi ønsker å Enqueue, vi ønsker å legge til enden av køen. Så vi faktisk ønsker å plasserer disse dataene i køen. I dette tilfellet, å plassere den i riktig plassering av vårt utvalg, og da vi ønsker å endre størrelsen av køen, hvor mange elementer vi for tiden. 

Så la oss komme i gang. Her er igjen, at generell skjema funksjon erklæring for hva enqueue kan se ut. Og her vi går. La oss Enqueue antall 28 inn i køen. Så hva skal vi gjøre? Vel, er det foran våre kø på 0, og størrelsen på vår kø er på 0, og så vi ønsker sannsynligvis å sette antall 28 i array element nummer 0, ikke sant? Så vi har nå lagt den inn der. Så nå hva trenger vi å endre? Vi ønsker ikke å endre foran i køen, fordi vi ønsker å vite hva element vi må kanskje dequeue senere. Så grunnen til at vi har foran der er liksom en indikator på hva som er den eldste tingen i matrisen. Vel den eldste tingen i array-- i Faktisk, den eneste i rekken riktig now-- er 28, noe som er på rekke plassering 0. Så vi ønsker ikke å endre det grønne nummeret, fordi det er den eldste element. Snarere, vi ønsker å endre størrelsen. Så i dette tilfellet, vil vi øke størrelsen til en. 

Nå en generell slags idé om hvor neste elementet kommer til å gå i en kø er å legge til disse to tallene sammen, front og størrelse, og som vil fortelle deg hvor neste element i køen kommer til å gå. Så nå la oss Enqueue et annet nummer. La oss Enqueue 33. Så 33 kommer til å gå inn matrise plassering 0 pluss 1. Så i dette tilfellet, det kommer å gå inn i rekke områder 1, og nå på størrelse med vår køen er 2. 

Igjen, vi er ikke i endring forsiden av våre kø, fordi 28 er fremdeles eldste element, og vi Vil to-- når vi til slutt får til dequeuing, fjerne elementer fra denne køen, ønsker vi å vite der den eldste element er. Og så må vi alltid å opprettholde noen indikator på hvor det er. Så det er hva det 0 er der for. Det er det som foran er der for. 

La oss i enqueue ett element, 19. Jeg er sikker på at du kan gjette hvor 19 kommer til å gå. Det kommer til å gå inn matrise plassering nummer to. Det er 0 pluss to. Og nå på størrelse med vår køen er 3. Vi har 3 elementer i den. Så hvis vi skulle, og vi kommer ikke til til akkurat nå, Enqueue et annet element, det ville gå inn i matrisen plassering nummer 3, og størrelsen på vår kø ville være fire. Så vi har enqueued flere elementer nå. Nå la oss begynne å fjerne dem. La oss dequeue dem fra køen. 

Så lik pop, som er slags på analog av denne for stabler dequeue må akseptere en pekeren til queue-- igjen, med mindre det er globalt deklarert. Nå ønsker vi å endre plasseringen på forsiden av køen. Det er der det liksom kommer inn i bildet, den fronten variabel, fordi når vi fjerner et element, vi ønsker å flytte den til neste eldste element. 

Da ønsker vi å redusere størrelsen på køen, og da vi ønsker å returnere verdien som ble fjernet fra køen. Igjen, vi ønsker ikke å bare forkaste det. Vi antagelig pakker ut det fra queue-- vi er dequeuing det fordi vi bryr oss om det. Så vi ønsker denne funksjonen til å returnere et dataelement av type verdi. Igjen, i dette tilfellet, er verdien heltall. 

Så nå la oss dequeue noe. La oss fjerne et element fra køen. Hvis vi sier int x lik & q, ampersand q-- igjen det er en peker til denne q data structure-- hva element kommer til å bli dequeued? I dette tilfelle, fordi det er en første inn, først ut datastruktur, FIFO, Det første vi legger i dette Køen var 28, og slik at i dette tilfellet, vi kommer til å ta 28 av køen, ikke 19, som er hva vi ville ha gjort hvis dette var en stabel. Vi kommer til å ta 28 ut av køen. 

I likhet med hva vi gjorde med en stabel, vi er faktisk ikke kommer til å slette 28 fra køen selv, vi skal bare snill av late som om det ikke er der. Så det kommer til å bli der i minnet, men vi er bare kommer til slags ignorere det ved å flytte de to andre felt av vår q data struktur. Vi kommer til å endre forsiden. Q.front skal nå være en, fordi det er nå den eldste elementet vi har i vår køen, fordi vi allerede har fjernet 28, som var den tidligere eldste element. 

Og nå, vi ønsker å endre størrelsen på køen til to elementer i stedet for tre. Nå husker tidligere jeg sa når vi ønsker å legge til elementer i køen, vi setter det i en matrise sted som er summen av fronten og størrelse. Så i dette tilfellet, er vi fremdeles sette det, det neste elementet i køen, i matrisen plassering 3, og vi får se det i et sekund. 

Så vi har nå dequeued vår første element fra køen. La oss gjøre det igjen. La oss ta et annet element fra køen. I det tilfelle gjeldende eldste element er rekke områder 1. Det er hva q.front forteller oss. Det grønne boksen forteller oss at det er den eldste element. Og så vil x blir 33. Vi vil bare slags glemme som 33 eksisterer i matrisen, og vi vil si at nå, det ny eldste element i køen er på rekke plassering 2, og størrelsen av køen, antall elementer vi har i køen, er en. Nå la oss Enqueue noe, og jeg slags ga dette bort en andre siden, men hvis vi ønsker å sette 40 inn i køen, der er 40 kommer til å gå? Vel, vi har vært å sette det i q.front pluss kø størrelse, og så det er fornuftig å faktisk å sette 40 her. Nå merker at i enkelte punkt, skal vi for å komme til enden av vår rekke innsiden av q, men det falmet ut 28 og 33-- de er faktisk, teknisk åpne plasser, ikke sant? Og så kan vi eventually-- som regel med å legge disse to together-- vi kan til slutt må mod av størrelsen på kapasitet slik at vi kan vikle seg rundt. 

Så hvis vi får til element nummer 10, hvis vi er erstatte den i element nummer 10, ville vi faktisk sette den i matrisen plassering 0. Og hvis vi skulle matrise beliggenhet-- unnskylde meg, hvis vi har lagt dem opp sammen, og vi fikk nummer 11 ville være der vi måtte sette den, noe som ikke eksisterer i denne array-- det ville være å gå ut av banen. Vi kunne mod med 10 og sette det i matrisen plassering 1. Så det er hvordan køer fungere. De er alltid kommer til å gå fra venstre til høyre og muligens vikle rundt. Og du vet at de er full hvis størrelse, at røde boksen, blir lik kapasitet. Og så etter at vi har lagt 40 til køen, vel hva trenger vi å gjøre? Vel, den eldste element i køen er fortsatt 19, slik at vi ikke ønsker å endre foran i køen, men nå har vi to elementer i køen, og så vi ønsker å øke vår størrelse fra 1 til 2. 

Det er ganske mye det med arbeider med tabellbaserte køer, og lignende for å stable, Det er også en vei å gjennomføre en kø som en lenket liste. Nå hvis dette datastruktur typen ser kjent ut for deg, er det. Det er ikke en enkeltvis lenket liste, det er en dobbelt lenket liste. Og nå, som en side, er det faktisk mulig å gjennomføre en kø som en enkeltvis lenket liste, men Jeg tenker i form av visualisering, det kan faktisk bidra til å vise dette som en dobbelt lenket liste. Men det er absolutt mulig å gjøre dette som en enkeltvis lenket liste. 

Så la oss ta en titt på hva dette kan se ut. Hvis vi ønsker å enquue-- så nå, igjen er vi bytte til en koblet-liste basert modell her. Hvis vi ønsker å Enqueue, vi ønsker å legge til et nytt element, godt Hva må vi gjøre? Vel, først av alt, fordi vi legger til slutten og fjerne fra begynnelse, vi sannsynligvis ønsker å opprettholde pekere til både hodet og halen av lenket liste? Halen er en annen betegnelse for enden av lenket liste, det siste elementet i lenket liste. Og disse vil trolig, igjen, være gunstig for oss hvis de er globale variabler. Men nå hvis vi ønsker å legge til en ny element hva har vi å gjøre? Hva vi bare [? malak?] eller dynamisk fordele vår nye knutepunktet for oss selv. Og så, akkurat som når vi legger alle element til en dobbelt lenket liste vi, må bare sortere of-- de tre siste trinnene her er bare om å flytte pekere i den riktige måten slik at elementet blir lagt til kjedet uten å bryte kjeden eller lage noen slags feil eller å ha noen form for ulykke skje der vi tilfeldigvis foreldreløs noen elementer av vår køen. Her er hva dette kan se ut. Vi ønsker å legge til elementet 10 til enden av denne køen. Så den eldste element her er representert ved hodet. Det er det første vi legger inn i dette hypotetiske kø her. Og hale, 13, er den mest nylig lagt element. Og så hvis vi ønsker å Enqueue 10 inn denne køen, ønsker vi å sette det etter 13. Og så vi kommer til å dynamisk tildele plass for en ny node og se etter null for å være sikker vi ikke har en hukommelsessvikt. Så skal vi til plassere 10 inn som node, og nå må vi være forsiktige om hvordan vi organiserer pekere slik at vi ikke bryte kjeden. 

Vi kan sette 10 tidligere felt å peke tilbake til den gamle halen, og siden '10 vil bli ny hale på et tidspunkt da alle disse kjedene er koblet til, ingenting kommer til å komme etter 10 akkurat nå. Og så 10 neste pekeren vil peke til null, og deretter etter at vi gjør dette, etter at vi har koblet 10 bakover til kjeden, vi kan ta den gamle hodet, eller unnskyldning meg, den gamle halen av køen. Den gamle slutten av køen, 13, og gjøre det vise til 10. Og nå, på dette punktet, har vi enqueued tallet 10 i denne kø. Alt vi trenger å gjøre nå er bare å flytte halen til å peke til 10 i stedet for til 13. 

Dequeuing er faktisk meget lik dukker fra en stabel som er implementert som en lenket liste hvis du har sett den stabler video. Alt vi trenger å gjøre er å starte på begynner, finne det andre elementet, frigjøre det første element, og deretter bevege hodet for å peke på det andre elementet. Sannsynligvis bedre å visualisere det bare for å være ekstra tydelig om det. Så her er vår køen igjen. 12 er den eldste element i vår kø, hodet. 10 er det nyeste elementet i vår kø, vår hale. 

Og så når vi ønsker til dequeue et element, vi ønsker å fjerne den eldste element. Så hva gjør vi? Vel vi satt en traversering peker som starter på hodet, og vi flytte det slik at det peker mot det andre elementet av denne queue-- noe ved å si trav tilsvarer trav-pilen ved, for eksempel, ville flytte trav det å peke på 15, som etter vi dequeue 12, eller etter at vi fjerner 12, vil bli den daværende eldste element. 

Nå har vi fått tak på den første element via pekeren hodet og det andre element via pekeren trav. Vi kan nå gratis hodet, og så kan vi sier ingenting kommer før 15 lenger. Så vi kan endre 15 tidligere pekeren til å peke til null, og vi bare bevege hodet over. Og der vi går. Nå har vi lykkes dequeued 12, og nå er vi har en annen kø av 4 elementer. Det er ganske mye alt det er til køer, både matrise-basert og knyttet-liste basert. Jeg er Doug Lloyd. Dette er CS 50.