Kö (datastruktur)

I datavetenskapen är en kö en linjär datastruktur för lagring av data. En kö karakteriseras av att de data som stoppades in först är de data som man får ut först. En kö kallas också FIFO (First In First Out: "först in, först ut"). Data i kön manipuleras med två operationer: enqueue och dequeue ("placera data sist i kön" respektive "ta bort data främst i kön").

Implementation

I en kö implementerad som en länkad lista får båda operationerna queue och dequeue konstant tidskomplexitet (O(1)). Fördelen med en länkad lista är att den i teorin kan växa obegränsat (i praktiken begränsas dock köns storlek av det tillgängliga datorminnet). Några nackdelar är att minnesförbrukningen i en länkad lista är högre än i ett fält (se nedan), och att länkarna i listan kan spridas i adressrymden och därmend orsaka ett ökat antal cachemissar.

En alternativ teknik är att använda sig av ett fält av fast storlek, med två referenser som anger aktuella positioner för avläsning och insättning i kön. Tidskomplexiteten blir densamma, O(1), men åtkomst till strukturen går fortare, har bättre cacheegenskaper och strukturen är mer minnessnål. Detta förutsätter att det går att sätta en lämplig övre gräns för köns storlek. Ett exempel på en sådan kö med alltför snålt tilltagen gräns var kön som lagrade tangenttryckningar i den ursprungliga IBM PC. För snabbt skrivande när program var upptagna fyllde då kön med väntande tangenttryckningar. När kön blev full avgav datorn ett pip för att markera att kön var full.

En variation på överstående implementation är att öka fältets storlek när kön fylls, gärna med en multiplikativ faktor. Den amorterade tidskomplexiteten fortsätter att vara O(1), men som i fallet med den länkade listan finns ingen (teoretisk) övre gräns för köns storlek. Dock förutsätter denna teknik att det är möjligt att komma åt tillräckligt med minne för att öka fältstorleken. I resursfattiga äldre datorsystem (som IBM PC i exemplet ovan) eller inbäddade system kan omöjliggöra denna variation.