Kø (datastruktur)

For alternative betydninger, se Kø. (Se også artikler, som begynder med Kø)

En kø er en datastruktur, hvor de enkelte dataelementer fjernes i samme orden, som de er indsat. Dette svarer til en almindelig kø, hvor man bliver ekspederet i den rækkefølge, man er ankommet.

Der er defineret følgende operationer på en kø:

• Indsæt element. Et element sættes bag i køen.
• Fjern element. Det første element fjernes fra køen, og en reference eller en kopi af elementet returneres.
• Læs element. Det første element i køen læses, men fjernes ikke.
• Hvis køen har en maksimal størrelse, kan man teste, om denne grænse er nået.

Implementering

Køer kan implementeres i tabeller eller som dynamiske lister.

Implementering i tabel

De fleste programmeringssprog giver mulighed for, at man kan arbejde med tabeller, og det er muligt at implementere en kø i en tabel. Det forudsættes i det følgende, at tabellen starter med element nul. For at undgå at flytte elementer, der er sat i kø, kan man i stedet lade start- og slutpositionerne være dynamiske. Når én af positionerne når den sidste position i tabellen, fortsættes fra nul.

Køen oprettes som en tom tabel. Desuden skal der bruges to variable, start og slut til afgrænsning af køen. De er som udgangspunkt sat til nul.

Indsættelse af data sker på den position, som slut peger på. Hvis slut peger på elementet lige før start, er køen fuld, og elementet kan ikke tilføjes. Elementet indsættes, og slut forøges. Hvis slut i forvejen pegede på det sidste element i tabellen, sættes slut til nul.

Fjern et element: Læs elementet, som start peger på. Forøg start med en. Hvis start i forvejen pegede på det sidste element i tabellen, sættes start til nul.

Køen er tom, hvis start er lig slut.

Køen er fuld, hvis start + 1 = slut (modulo tabellens størrelse).

Implementering i en liste

Nogle programmeringssprog giver mulighed for brug af dynamiske lister. Med en liste kan de forskellige operationer laves som følger: Indsættelse sker ved, at der indsættes et element sidst i listen. Et element fjernes fra køen ved at fjerne det første element i listen. Køen er tom. hvis listen er tom.

Se også

• FIFO - LIFO (First In First Out - Last in First Out)