Hvad er forskellen mellem en cirkulær kø og en lineær kø?
Køer bruges til at modellere datastrukturer i computer programmering. Både lineære og cirkulære køer omfatte en række dataelementer lagres ved hjælp af en "først ind først ud" system. Det betyder, at det første punkt føjet til køen er den første til at blive fjernet fra det, med det sidste punkt også tilføjet sidste til at blive fjernet. Abstrakt, idet poster tilføjes på bagsiden af en kø og fjernes fra forsiden. Imidlertid er dette implementeret forskelligt i cirkulære og lineære køer. Forskellene mellem disse to køtyper har konsekvenser for hukommelse, effektivitet og forarbejdning.
Først i først ud
I både lineære og cirkulære køer, "først i først ud" reglen gælder. Alle nye poster tilføjes til enten en lineær eller en cirkulær kø deltage i kø på bagsiden, som i det virkelige liv køer. Det eneste element, der kan fjernes fra en kø til enhver tid er den på forsiden. I denne forstand både lineære og cirkulære køer er kun tilgængelige i hver ende. Inden programmering af computere, er denne adgang forvaltes ved at holde pegepinde til forsiden og bagsiden af køen. Disse pejlemærker registrere placeringen i hukommelsen, hvor de forreste og bageste elementer er gemt. Hvis de andre elementer er i forhold til disse to afhænger af, om køen er cirkulær eller lineær.
Underliggende lineær struktur
Programmeringssprog give en række lagringsmuligheder, hvor udviklere kan håndtere køer. For eksempel kan en programmør anvende et array struktur til at lagre enten en lineær eller en cirkulær array. For et lineært array, kan det første element i køen oprindeligt opbevares ved den første position i arrayet struktur, som har en nul-indekset. Hvis køen havde ti elementer i det, ville det sidste punkt i køen i første omgang være på position ni. Når et element blev fjernet fra køen, fra position nul, ville den forreste markøren flytte for at positionere en. Når et element blev tilsat til køen, vil den bageste pointer også øges med én.
Underliggende cirkulær struktur
Hvis et program anvender en matrix struktur til at gemme en cirkulær kø vil køen synes at opføre sig på samme måde eksternt, men gennemførelsen detaljer ville være anderledes. For eksempel, med en cirkulær kø, hvis et element blev fjernet fra foran og en anden tilføjet til den bageste, snarere end de forreste og bageste pointers både forøgning, elementet tilsættes til bagenden af køen faktisk kunne placeres i position nul, som var, hvor det element ved fronten havde oprindeligt været opbevaret. På denne måde vil de forreste og bageste pointers stadig øges for at holde styr på, hvor den forreste og køen var, men når hver når enden af strukturen, vil det blive sat tilbage til starten af rækken, og bevæge sig fremad fra der.
Hukommelse
Ved hjælp af en matrix til at gemme en kø er et godt eksempel på, hvor cirkulære arrays kan tilbyde en forbedring i forhold til de lagringsressourcer et program bruger. Hvis der tilsættes hver gang elementer til en kø, strækker bagsiden af køen, betyder dette, at den samlede mængde hukommelse tildelt køen kunne fortsætte med at stige, selv hvis emner bliver fjernet fra forsiden. Dette kan betyde, at den samlede længde af køen forbliver den samme, men den hukommelse, det kræver holder bliver større. Cirkulære køer tillader programmer at genbruge de samme steder i hukommelsen som elementer fjernes og tilføjes. Hvis køen forbliver nogenlunde samme længde, på denne måde er det ikke kræver mere hukommelse som elementer tilføjes og fjernes.
Ledelse
Selvom cirkulære køer forbedre hukommelsen sammenlignet med lineære køer, de kræver en anden algoritme i det program, der styrer adgangen til de punkter. For eksempel med en lineær kø, de forreste og bageste pointere blot øges, hver gang et element er tilføjet eller fjernet. Men med en cirkulær kø, en algoritme skal gennemføres, der gør hver pointer flytte tilbage til starten af den tildelte lagringsstruktur når den når slutningen.