[Powered by Google Translate] [Kø] [Chris Gerber, Harvard University] Dette er CS50, CS50.TV] En nyttig datastruktur til at lagre en ordnet samling af elementer er en kø. Det anvendes, når elementerne skal fjernes i samme rækkefølge, som de blev tilsat. Dette koncept betegnes FIFO, som er en forkortelse for først ind, først ud. For at hjælpe visualisere dette, kan det være nyttigt at billede en checkout linje i en butik. Som folk ankommer, de venter på bagsiden af ​​linjen. Kassereren tager derefter skiftes betjener kunderne ved fronten, der derefter afslutte linien én ad gangen. I datalogi, henviser vi til den forrest i køen som leder og tilbage som halen. Et eksempel på, hvornår vi kan bruge dette i en ansøgning er en venteliste for klasse tilmeldinger. Som pladser bliver tilgængelige i klassen, personen i spidsen for ventelisten gives mulighed for at tilmelde dig i klassen. 

En kø kan konstrueres ved hjælp af en samling der gemmer data for, såsom en matrix eller en forbundet liste. Sammen med indsamlingen til at gemme elementerne i køen, vi også brug for en metode til at tilføje elementer i slutningen af ​​køen, som kaldes enqueuing, og en anden for at fjerne et element fra forrest i køen, som kaldes dequeuing. Er det ofte nyttigt at inkludere en anden metode til at returnere den aktuelle længde af køen såvel som en metode til at kontrollere, om køen er tom. Lad os se på, hvordan vi kan gennemføre en kø af heltal i C, anvendelse af et array til indsamling af elementer. Først skaber vi en struktur kaldet kø for at holde vores variabler. Vi vil bruge en fast størrelse 0 indeks vifte af heltal at lagre elementerne. Vi vil også indeholde en variabel kaldet hoved der gemmer indekset for det element, der er i øjeblikket i spidsen af ​​køen. En tredje variabel, benævnt længde, blive anvendt at holde styr på antallet af elementer i arrayet. Som et alternativ, kan du overveje at bruge en variabel kaldet hale at pege på det sidste felt element i grupperingen. Før vi skrive noget mere kode, lad os prøve vores design. Lad os starte med et tomt array af længde 0, med hovedet på 0. Lad os nu enqueue 4 værdier - 6, 2, 3 og 1. Længden vil nu være 4, og hovedet vil bo på 0. 

Hvad sker der, hvis vi dequeue en værdi? Vi vil reducere længden til 3, indstille dyr til 1, og returnere værdien 6. Denne kode kan se sådan ud. Her har vi den dequeue funktion, som tager en pointer til køen - q - og en pointer til elementet, som er en type int. Først skal vi kontrollere længden af ​​køen til at sikre, at det er mere end 0, at sikre, at der er et element, der skal dequeued. Så vi ser i elementerne array, ved positionen hoved, og sætte værdien af ​​elementet at være værdien på denne position. Så skifter vi hovedet til at være den næste indeks % Af kapaciteten. Vi derefter reducere længden af ​​køen med 1. Endelig vi vender tilbage korrekt at angive, at dequeue lykkedes. Hvis vi dequeue igen, vil længden blive 2, Hovedet vil også blive 2, og afkastet værdi vil være 2. 

Hvad sker der, hvis vi sætte mellemlager anden værdi, såsom en 7? Da vi var i slutningen af ​​køen, vi bliver nødt til at vikle rundt og gemme værdien i element 0 i arrayet. Matematisk kan dette repræsenteres ved tilsætning af længden til indekset af hovedet og udførelse af en modul ved hjælp af køen kapacitet. Her, er 2 +2, hvilket er 4% 4, som er 0. Omsætte denne idé til at kode vi har denne funktion. Her ser vi den enqueue funktion, som tager en pointer til køen - q - og tager elementet, der skal enqueued, hvilket er et helt tal. Vi næste tjek for at sikre, at kapaciteten af ​​køen stadig større end den aktuelle længde af køen. Næste, vi gemmer elementet i elementerne arrayet ved indeks, der bestemmes af hovedet + længde% kapacitet køen. Vi derefter øge kølængde med 1, og derefter returnere rigtigt at angive, at enqueue funktion var vellykket. 

Ud over de to funktioner vi har nævnt, der er to ekstra funktioner. Først er det isempty funktion, som tager en pointer til køen og kontrollerer, at længden er 0. Det andet er længden funktion, som også tager en pointer til køen og returnerer den aktuelle længde fra struct. Denne korte oversigt har vist en mulig implementering af en kø. En af begrænsningerne for denne implementering er, at køen har en fast maksimal størrelse. Hvis vi forsøger at tilføje flere elementer end køen kan rumme, vi måske nødt til at ignorere anmodningen og slip elementet, eller vi måske foretrækker at returnere nogle type fejl. Ved hjælp af en sammenkædet liste ikke et array ville gøre det nemmere at dynamisk størrelse køen. Men da vi ikke har direkte adgang til elementerne i en linket liste, hvis vi ikke holde styr på halen, vi ville have til at scanne hele linkede liste for at komme til slutningen hver gang. Vi kunne også overveje at bruge et array af en anden datatype, såsom struct, at skabe køer af mere komplekse dele. Tænker tilbage til vores eksempel på en klasse venteliste disse strukturer kunne repræsentere den enkelte studerende. 

Mit navn er Chris Gerber, og dette er CS50. [CS50.TV] Og afkast - >> en gang mere. Og returnere sandt at indikere, at - køen var vellykket. -% Kapacitet køen - Det bliver sjovt i redigeringstilstand. [Latter]