Kön kan beskrivas som icke-primitiv linjär datastruktur följer FIFO-ordningen i vilken dataelement är infogade från ena änden (bakre änden) och raderas från den andra änden (främre änden). De andra variationerna i kön är den cirkulära köen, dubbelt avslutad kö och prioritetskön.
Jämförelsediagram
| Grunder för jämförelse | Linjär kö | Cirkulär kö |
|---|---|---|
| Grundläggande | Organiserar dataelementen och instruktionerna i en sekventiell ordning en efter en. | Ordnar data i det cirkulära mönstret där det sista elementet är anslutet till det första elementet. |
| Order of task execution | Uppgifterna är utförda så att de placerades före (FIFO). | Order för att utföra en uppgift kan ändras. |
| Infogning och radering | Det nya elementet läggs från baksidan och tas bort från framsidan. | Infogning och radering kan göras vid vilken position som helst. |
| Prestanda | Ineffektiv | Fungerar bättre än den linjära köen. |
Definition av linjär kö
En linjär kö är rationellt en första i först utbeställd lista. Den är så kallad linjär eftersom den liknar en rak linje där elementen placeras en efter en. Den innehåller en homogen samling av de element där nya element läggs till i ena änden och raderas från en annan ände. Konceptets koncept kan förstås av exemplet av en publikköna som väntar utanför biljetträknaren för att få teaterbiljetten. I den här köen ansluter personen till bakre delen av köen för att ta biljetten och biljetten utfärdas i köens främre ände.
Det finns flera operationer som utförs i köen
- För det första initieras köen till noll (dvs tom).
- Bestäm om köen är tom eller inte.
- Bestäm om köen är full eller inte.
- Infoga det nya elementet från bakre änden (Enqueue).
- Deletion av elementet från frontänden (Dequeue).
Kön kan implementeras på två sätt
- Statiskt (Använda arrays)
- Dynamiskt (Använda pekare)
Begränsningen av den linjära köen är att den skapar ett scenario där inget nytt element kan läggas till i kön, även om kön innehåller tomma utrymmen. Denna ovanstående situation illustreras i nedanstående figur. Här pekar baksidan på det sista indexet medan alla lådor är tomma fortfarande, inget nytt element kan läggas till.
Definition av cirkulär kö
En cirkulär kö är en variant av den linjära köen som effektivt övervinner begränsningen av den linjära köen. I cirkulär kö läggs det nya elementet till könens första läge, om det sista är upptaget och det finns ledigt utrymme. När det gäller linjär kö kan inmatningen endast utföras från bakre änden och borttagning från frontänden. I en fullständig kön efter att ha utfört serier av successiva raderingar i kön uppstår en viss situation där inget nytt element kan läggas till även om det lediga rummet är tillgängligt eftersom underflödet (bakre = max - 1) fortfarande finns.
Cirkelkön ansluter de två ändarna genom en pekare där det första elementet kommer efter det sista elementet. Det håller också koll på fram och bak genom att implementera lite extra logik så att den kan spåra elementen som ska infogas och raderas. Med detta genererar den cirkulära köen inte överflödsläget tills kön är full i faktisk.
Några villkor följt av cirkelkön:
- Front måste peka på det första elementet.
- Kön kommer att vara tom om Front = Bakre.
- När ett nytt element läggs till ökas köen med värde ett (Bakre = Bakre + 1).
- När ett element raderas från kön, ökar fronten med en (Front = Front + 1).
Viktiga skillnader mellan linjär kö och cirkulär kö
- Linjärkön är en beställd lista där dataelement är organiserade i sekventiell ordning. Däremot lagrar cirkelkön data i cirkulär mode.
- Linjär kö följer FIFO-orderen för att utföra uppgiften (det element som läggs till i det första läget kommer att raderas i det första läget). Omvänt, i den cirkulära köen kan orderordningen för operationer som utförs på ett element ändras.
- Införandet och deletionen av elementen är fixerad i linjär kö, dvs tillägg från bakre änden och borttagning från frontänden. Å andra sidan är den cirkulära köen kapabel att infoga och radera elementet från vilken tidpunkt som helst tills det inte är upptaget.
- Linjär kö slösar bort minnesutrymmet medan cirkulär kö gör effektiv användning av rymden.
Implementering av den linjära köen
Den nedan angivna algoritmen illustrerar tillsatsen av element i en kö:
Kön behöver tre datavariabler, inklusive en grupp för att lagra kön och andra för att lagra front- och bakre inledande position som är -1.
infoga (föremål, kö, n, bakre) {om (bakåt == n) skriv sedan ut "köövergång"; annars {bakre = bakre + 1; kö [baksida] = objekt; }} Den nedan angivna algoritmen illustrerar radering av element i en kö:
delete_circular (föremål, kö, bak, framsida) {om (bakåt == framsida) och skriv sedan ut "köunderflöde"; annars {front = front + 1; item = kö [front]; }} Genomförande av den cirkulära köen
En algoritm för att tolka tillsatsen av elementet i cirkelkön:
insert_circular (föremål, kö, bak, framsida) {bakre = (bakre + 1) mod n; om (framåt == bakåt) skriv ut "kö är full"; annars {kö [bakåt] = objekt; }} Algoritmen förklarar elementets borttagning i den cirkulära köen:
delete_circular (föremål, kö, bak, framsida) {om (framåt == bakåt) och skriv ut ("kö är tom"); annars {front = front + 1; item = kö [front]; }} Slutsats
Linjärkön är ineffektiv i vissa fall där elementen måste flyttas till de lediga utrymmena för att utföra insättningsoperationer. Det är därför att det tenderar att slösa bort lagringsutrymmet medan cirkelkön gör lämplig användning av lagringsutrymmet när elementen läggs till vid vilken position som helst, om det finns ett tomt utrymme.
