Skillnaderna mellan en cirkulär kö och en linjär kö

Även om köer i själva verket kan relatera till vilket flytande system som helst, är cirkulära och linjära köer oftast förknippade med mjukvara och datorsystem. I båda typerna finns strukturella och prestanda­skillnader. Exempelvis kan en nätverksarkitekt som designar en webbserverfarm behöva avgöra om åtkomsten hanteras via en cirkulär eller en linjär kö. Beslutet påverkar både hur trafiken dirigeras till servrarna och hur själva servrarna är strukturellt uppkopplade.

Verkliga exempel

För att snabbt förstå den primära skillnaden mellan en linjär kö och en cirkulär kö kan vi ta ett vardagligt exempel: en grupp människor väntar i kö för att få sitt bord på en restaurang. När ett bord blir ledigt sitter de först i kön in, och nya gäster tar plats i slutet av kön. En cirkulär kö är mer likt ett spel med musikstolar – nykomlingar kan ta plats var som helst där det finns en ledig stol.

Jämförelse av köstrukturer

En linjär kö är som en rak linje där varje element står exakt bakom det föregående. Det finns en tydlig början och ett tydligt slut. Uppgifter i den här strukturen utförs i den ordning de anländer, enligt FIFO‑principen (First In First Out). En cirkulär kö däremot har en ring‑formad struktur: det sista elementet är kopplat till det första, vilket bildar en sluten slinga. I denna struktur utförs uppgifter inte nödvändigtvis i den ordning de anländer.

Infoga och ta bort

Vid en linjär kö läggs nya uppgifter in i slutet, medan borttagning sker i början. Front- och bakdelarna är ansvariga för att hålla reda på köstatusen. En kö kan ha ett förutbestämt maximalt antal element. Innan en ny insättning kontrolleras en “kö full”‑test och innan en borttagning en “kö tom”‑test. “Kö full” verifierar att det finns plats för ny infogning, medan “kö tom” säkerställer att det finns element att ta bort. I en cirkulär kö kan infogningar och borttagningar göras på valfri position, inte nödvändigtvis i sekventiell ordning.

Underhållskostnad och tid

Vid en linjär kö måste ett tomt utrymme finnas i början när en ny uppgift läggs till. Alla element mellan front och slut flyttas därför upp en position för att frigöra plats. Varje ny infogning kräver alltså samma upprepade flyttningar. Infogning och borttagning blir därför två separata steg och kan vara tidskrävande och resursintensiva. I en cirkulär kö kan infogning och borttagning ske parallellt, vilket gör den mer effektiv.

Cirkulära köer används ofta i system där resurser återanvänds, t.ex. i bufferthantering och I/O‑köror, medan linjära köer passar bättre för enkla sekventiella processer.