mynewspapers.net

Vilka är skillnaderna mellan en cirkulär kö och en linjär kö?

Vilka är skillnaderna mellan en cirkulär kö och en linjär kö?


Köer används för att modellera datastrukturer i datorprogrammering. Både linjära och cirkulära köer innebär en rad uppgifter objekt lagras med hjälp av en "först in först ut"-system. Detta innebär att det första objektet som lagts till i kön är först tas bort från den, med det sista objektet läggs också senast tas bort. I abstrakta termer, objekt läggs till baksidan av en kö och bort från framsidan. Dock har detta implementerats olikt i cirkulär och linjär köer. Skillnaderna mellan dessa två kön påverkar för minne, effektivitet och bearbetning.

Först in först ut

I både linjära och cirkulära köer gäller regeln "först in först ut". Alla nya objekt som läggs till antingen en linjär eller en cirkulär kö koppling kön baktill, som i verkliga livet köer. Det enda objekt som kan tas bort från en kö när som helst är den längst fram. I denna mening är både linjära och cirkulära köer tillgängliga endast i vardera änden. Inom datorprogrammering hanteras denna åtkomst genom att hålla pekare till fram och bak i kön. Pekarna registrera platsen i minnet där främre och bakre poster lagras. Där de andra objekten är i förhållande till dessa två beror på om kön är cirkulär och linjär.

Underliggande linjärt strukturera

Programmeringsspråk ger en rad lagringsalternativ där utvecklare kan hantera köer. En programmerare kan till exempel använda en array struktur för att lagra antingen en linjär eller en cirkulär matris. För en linjär array, kunde det första objektet i kön initialt lagras på första position i matrisen struktur, med ett noll index. Om kön hade tio objekt i det, skulle det sista elementet i kön inledningsvis göras på plats nio. När ett objekt har tagits bort från kön från position noll, skulle främre pekaren flyttar till plats ett. När ett objekt har lagts till i kön, skulle bakre pekaren också ökas stegvis med en.

Underliggande cirkulär struktur

Om ett program använder en array struktur för att lagra en cirkulär kö, kön verkar bete sig på samma sätt externt, men implementeringen skulle vara annorlunda. Exempelvis med en cirkulär kö, kunde om ett objekt har tagits bort från framsidan och en annan läggs till baksidan, snarare än främre och bakre pekare både uppräkning, objektet läggs till baksidan av kön faktiskt placeras i läge noll, vilket var där artikeln på framsidan hade ursprungligen varit lagrat. Detta sätt, de främre och bakre pekare skulle fortfarande ökas för att hålla reda på var den främre och kön var, men när varje når slutet av struktur, skulle det ställa tillbaka till början av matrisen och gå vidare därifrån.

Minne

Använder en array för att lagra en kö är ett bra exempel på när cirkulära arrayer kan erbjuda en förbättring när det gäller lagringsresurser en används. Om varje gång objekt läggs till en kö, baksidan av kön sträcker sig, detta innebär att den totala mängden minne som har allokerats till kön skulle kunna fortsätta att öka, även om objekten tas bort från framsidan. Detta kan innebära att den totala längden på kön är detsamma men minnet det kräver håller blir större. Cirkulär köer tillåter program att återanvända samma platser i minnet som artiklar bort och lagt till. Om kön förblir ungefär samma längd, så sätt det inte kräver mer minne som objekten läggs till och tas bort.

Management

Även om cirkulär köer förbättra minne jämfört med linjär köer, kräver de en annorlunda algoritm inom programmet som hanterar åtkomst till objekt. Till exempel med en linjär kö, är främre och bakre pekare helt enkelt ökas varje gång ett objekt läggs till eller tas bort. Dock med en cirkulär kö, måste en algoritm genomföras som gör varje pekaren flytta tillbaka till början av den tilldelade lagringsstrukturen när den når slutet.