Queue är en abstrakt datatyp med först-in-först-ut-elementåtkomstdisciplin ( FIFO , engelska först in, först ut ). Att lägga till ett element (vanligtvis betecknat med ordet enqueue - lägg i en kö) är endast möjligt i slutet av kön, sampling - endast från början av kön (som vanligtvis kallas ordet dequeue - ta bort från kön), medan det valda elementet tas bort från kön.
Det finns flera sätt att implementera en kö i programmeringsspråk.
Det första sättet representerar kön som en array och två heltalsvariabler start och slut.
Pekar vanligtvis startpå köns huvud, end elementet som kommer att fyllas när ett nytt element kommer in i kön. När ett element läggs till i kön skrivs det q[end]nya köelementet till och endminskas med ett. Om värdet på end blir mindre än 1, så går vi en slags slinga runt arrayen, och värdet på variabeln blir lika med n. Att extrahera ett element från kön görs på liknande sätt: efter att ha extraherat ett element q[start]från kön startreduceras variabeln med 1. Med sådana algoritmer kommer en cell från kön nalltid att vara ledig (eftersom en kö med nelement inte kan urskiljas från en tom), vilket kompenseras av algoritmernas enkelhet.
Fördelar med denna metod: liten besparing av minne är möjlig i jämförelse med den andra metoden; lättare att utveckla.
Nackdelar: Det maximala antalet element i kön begränsas av storleken på arrayen. När det svämmar över kräver det omallokering av minne och kopiering av alla element till en ny array.
Den andra metoden bygger på att arbeta med dynamiskt minne. Kön representeras som en linjär lista , där tillägg/borttagning av element kommer strikt från dess respektive ändar.
Fördelar med denna metod: storleken på kön begränsas endast av mängden minne.
Nackdelar: svårare att utveckla; mer minne krävs; när man arbetar med en sådan kö är minnet mer fragmenterat; köandet är något långsammare.
Kömetoder kan implementeras baserat på två stackar S1 och S2som visas nedan:
procedurkö ( x ): S1.push( x ) dequeue() funktion: om S2 är tom: om S1 är tom: rapportera fel: kön är tom tills S1 är tom: S2.push(S1.pop()) returnera S2.pop()Denna implementeringsmetod är mest bekväm som grund för att bygga en beständig kö . .
Köer är implementerade i nästan alla utvecklade programmeringsspråk. CLI tillhandahåller klassen System.Collections.Queue för detta, med metoderna Enqueue och Dequeue. STL har också klasskön <>, definierad i huvudfilkön. Den använder samma terminologi (push och pop) som stackar .
Kön i programmering används, som i verkligheten, när du behöver utföra vissa åtgärder i den ordning de tas emot, och utföra dem sekventiellt. Ett exempel är arrangemanget av evenemang i Windows. När användaren utför någon åtgärd på applikationen anropas inte motsvarande procedur i applikationen (trots allt, för närvarande kan applikationen utföra andra åtgärder), men ett meddelande skickas till honom som innehåller information om den vidtagna åtgärden, detta meddelande är i kö, och endast när meddelanden som kom tidigare bearbetas kommer applikationen att utföra den nödvändiga åtgärden.
BIOS- tangentbordsbufferten är organiserad som en ringarray, vanligtvis 16 maskinord lång, och två pekare: till nästa element i det och till det första lediga elementet.
| Data struktur | |
|---|---|
| Listor | |
| Träd | |
| Räknar | |
| Övrig | |