[Powered by Google Translate] [Kö] [Chris Gerber, Harvard University] Detta är CS50, CS50.TV] En användbar datastruktur för lagring av en ordnad samling av element är en kö. Det används när elementen måste tas bort i samma ordning som de tillsattes. Detta koncept kallas FIFO, vilket är en förkortning för först in, först ut. För att hjälpa visualisera detta, kan det vara lämpligt att bilden en kassan linje i en butik. När människor kommer, väntar de på baksidan av linjen. Kassören tar sedan vänder betjänar kunder på framsidan, som sedan avsluta linjen en åt gången. I datavetenskap hänvisar vi till framsidan av kön som chef och tillbaka som svansen. Ett exempel på när vi kan använda detta i ett program är en väntelista för klass registreringar. Som platser blir tillgängliga i klassen, personen i spetsen för väntelistan finns möjlighet att anmäla dig till klassen. 

En kö kan konstrueras med användning av någon samling som lagrar data i ordning, såsom en matris eller en länkad lista. Tillsammans med samlingen för att lagra poster i kön, Vi behöver också en metod för att lägga till objekt i slutet av kön, som kallas enqueuing, och en annan för att ta bort ett objekt från chefen för kön, som kallas dequeuing. Det är ofta användbart att inkludera en annan metod för att returnera den aktuella längden på kön såväl som en metod för att kontrollera om kön är tom. Låt oss titta på hur vi kan genomföra en kö av heltal i C, använda en array för insamling av elementen. Först skapar vi en struktur som kallas kö för att hålla våra variabler. Vi kommer att använda en fast storlek array 0 index heltal att lagra elementen. Vi kommer också att innehålla en variabel som heter huvud som lagrar index för elementet som för närvarande i spetsen för kön. En tredje variabel, kallad längd, kommer att användas att hålla reda på antalet element i arrayen. Som ett alternativ kan du överväga att använda en variabel som heter svans att peka på det sista fältet elementet i arrayen. Innan vi skriver något mer kod, Låt oss prova vår design. Låt oss börja med en tom array med längden 0, med huvudet satt till 0. Nu ska vi köa 4 värden - 6, 2, 3, och 1. Längden kommer nu att 4, och huvudet kommer att bo på 0. 

Vad händer om vi avköa ett värde? Vi kommer att minska längden till 3, ställa huvudet till 1, och returnera värdet 6. Den koden kan se ut så här. Här har vi dequeue funktion, som tar en pekare till kön - q - och en pekare till elementet, som är en typ int. Först kollar vi längden på kön för att se att det är mer än 0, att säkerställa att det finns ett element som skall ur kön. Då vi tittar i elementen arrayen, i det läge huvudet, och ange värdet på elementet vara det värde vid denna position. Sedan byter vi huvudet att bli nästa index % Kapaciteten. Vi minskar då längden av kön med 1. Slutligen återvänder vi riktigt för att indikera att dequeue lyckades. Om vi ​​avköa igen, längden blir 2, huvudet blir också 2, och returvärdet blir 2. 

Vad händer om vi köa annat värde som en 7? Eftersom vi var i slutet av kön, kommer vi att behöva svepa runt och lagra värdet i elementet 0 av matrisen. Matematiskt kan detta representeras genom tillsats längden till index av huvudet och utföra en modul med kö kapacitet. Här som är 2 +2, vilket är 4% 4, vilket är 0. Översätta denna idé att koda vi har denna funktion. Här ser vi den enqueue funktion, som tar en pekare till kön - q - och tar elementet som skall kö, som är ett heltal. Vi kontrollerar bredvid se till att kapaciteten i kön är ännu större än den aktuella längden på kön. Sedan lagrar vi elementet i elementen arrayen vid indexet som bestäms av huvudet + längd% kapacitet kön. Vi ökar sedan kölängden med 1, och sedan återvända riktigt för att indikera att enqueue funktionen lyckades. 

Förutom de två funktioner som vi har nämnt, Det finns två ytterligare funktioner. Först är IsEmpty funktionen, som tar en pekare till kön och verifierar att längden är 0. Den andra är längden funktionen, som tar också en pekare till kön och returnerar den aktuella längden från struct. Denna korta översikt har visat en möjlig tillämpning av en kö. En av begränsningarna för denna implementering är att kön har en fast maximal storlek. Om vi ​​försöker att lägga till fler element än kön kan hålla, vi kan behöva ignorera begäran och släpp elementet, eller vi kanske föredrar att returnera någon typ av fel. Med användning av en länkad lista snarare än en matris skulle göra det lättare att dynamiskt storlek kön. Men eftersom vi inte har direkt tillgång till de delar av en länkad lista, om vi inte hålla reda på svansen, vi skulle behöva skanna hela länkad lista för att få till slutet varje gång. Vi kan också överväga att använda en rad av en annan datatyp, såsom structs att skapa köer av mer komplexa element. Tänker tillbaka till vårt exempel på en klass väntelista, dessa strukturer kunde representera de enskilda studenterna. 

Mitt namn är Chris Gerber, och detta är CS50. [CS50.TV] Och avkastning - >> en gång till. Och return true för att indikera att - kön var framgångsrik. -% Kapacitet kön - Det ska bli kul i redigera. [Skratt]