Kö

Definition

En kö är en sekvens där det senast inlagda elemetet alltd hamnar sist och endast det första elementet kan tas bort. Därför kallas en kö för FIFO (First In First O ut).

De två operationer en kö måste ha är att lägga in element (kallas enqueue) och ta bort element (kallas dequeue):

Implementation

Felhantering

Alla exempel hittils har hoppat över felhanteringen. Låt oss nu för en gångs skull ta med den.

Vad ska hända till exempel om någon försöker anropa dequeue() när kön är tom? Ett vanligt sätt att hantera fel i C är att funktionen returnerar någon felkod (tex -1) om ett fel uppstår. Om allt går bra returneras något fördefinierat värde (tex 0) som indikerar det. Så är felhanteringen löst i arrayimplemetationen nedan. Ett problem är att vi "gör av med" returvärdet för att ge denna statuskod. Hur ska dequeue() då kunna returnera det element som hämtas från kön? Lösningen är att returnera det i en av funktionens parametrar. Denna måste då vara en pekare eftersom det inte finns "utparametrar" (pass-by-reference) i C. Definitionen av köns funktioner ändras med dena felhantering till:
Här kommer en header-fil med denna definition, queue.h .

Array

Här har vi arrayimplementationen, ArrayQueue.c , och ett program för att testa den, TestQueue.c . Arrayen behandlas som en cirkulär buffert, dvs på positionen efter det sista elementet finns det första elementet. På det viset slipper vi flytta på elementen i kön. En klurighet blir då att veta när arrayen är full och att kunna skilja detta tillstånd från det att arrayen är tom. Detta löses i exemplet genom att ha en variabel som håller reda på arrayens storlek.

Denna implementation har en privat operation (nextPos() ). Det innebär att den operationen inte finns med i headerfilen och därmed inte är känd för den som använder vårat bibliotek. Därmed behöver vi inte vara rädda för att ändra dess definition, det finns ju inget utanför vårt bibliotek som är beroende av den. Jämför hur datat (array eller länkad lista) på samma sätt varit privat i våra tidigare impelenationer av datastrukturer. Att den över huvud taget finns beror på att den är användbar för de publika operationerna (dvs de som finns i headerfilen). I det här fallet har vi med den för att det är en meningsfull ny abstraktion, både mha parametrar (vi slipper ha koden på två ställen) och mha specifikation (förtydliga vad currentPos++ % MAX_QUEUE_SIZE gör och underlättar om vi vill ändra i den kodraden).

Det finns inget beroende av köns storlek i vare sig enqueue() eller dequeue(). Båda är O(1).

Angående minesutrymme gäller samma resonemang som för stacken .

Länkad lista

Här kommer implementationen med länkad lista, ListQueue.c . Observera att det inte behövs någon "first", dvs någon pekare på köns första element. Det beror på att listan är cirkulär, det första elementet är helt enkelt det efter last (dvs last->next). För att provköra denna implementation behövs ett nytt testprogram, TestListQueue.c . Varför det? Vi har ju inte ändrat specifikationen!?! Nej, det har vi inte, men problemet är att enqueue() i denna implementation aldrig returnerar -1 (att kön är full). Detta innebär väl snarast att implemetationen inte riktigt uppfyller hela specifikationen. Sådant måste dokumenteras väl!

Inte heller med denna implementation finns det något beroende av köns storlek, både enqueue() och dequeue() är O(1).

För minesutrymme samma resonemang som för stacken .

Jämförelse

Inget nytt, samma resonemang som för stacken även här. En kö och en stack är väldigt likartade datastrukturer, skillnaden är bara i vilken ände element tas bort.