Kö (datastruktur)
Wikipedia
En kö är 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).
[redigera] Implementation
Om man implementerar en kö exempelvis som en länkad lista får både operationerna (queue och dequeue) konstant tidskomplexitet (O(1)).
I praktiken är det inte ovanligt att ha en array av fast storlek, med en referens som anger aktuell position för avläsning och insättning i kön. Tidskomplexiteten blir densamma, men åtkomst till strukturen går fortare och den är även mer minnessnål. Detta förutsätter att man kan sätta en lämplig gräns för köns storlek. Ett exempel på en snålt tilltagen sådan kö var den som lagrade tangenttryckningar i den ursprungliga IBM PC. För snabbt skrivande när program var upptagna kunde då få datorn att pipa.
