Køen kan beskrives som ikke-primitive lineære datastruktur følger FIFO-ordren, hvori dataelementer indsættes fra den ene ende (bagenden) og slettes fra den anden ende (forenden). De øvrige variationer i køen er den cirkulære kø, dobbelt slut kø og prioritetskø.
Sammenligningstabel
| Grundlag for sammenligning | Lineær kø | Cirkulære kø |
|---|---|---|
| Grundlæggende | Organiserer dataelementerne og instruktionerne i en rækkefølge efter hinanden. | Arrangerer dataene i det cirkulære mønster, hvor det sidste element er forbundet med det første element. |
| Ordre af opgaveudførelse | Opgaver udføres, så de blev placeret før (FIFO). | Ordren for at udføre en opgave kan ændres. |
| Indsætning og sletning | Det nye element tilføjes fra bagenden og fjernes fra forsiden. | Indsætning og sletning kan foretages på enhver position. |
| Ydeevne | ineffektiv | Fungerer bedre end den lineære kø. |
Definition af Linear Queue
En lineær kø er rationelt en første i første uddelt liste. Det er såkaldt lineært, fordi det ligner en ret linje, hvor elementerne er placeret efter hinanden. Den indeholder en homogen samling af de elementer, hvor nye elementer tilføjes i den ene ende og slettes fra en anden ende. Konceptets koncept kan forstås ved eksemplet på en kø af publikum, der venter udenfor billetbænken for at få teaterbilletten. I denne kø er personen tilsluttet bagenden af køen for at tage billetten, og billetten udstedes i køens forreste ende.
Der er flere operationer udført i køen
- For det første initialiseres køen til nul (dvs. tom).
- Bestem, om køen er tom eller ej.
- Bestem, om køen er fuld eller ej.
- Indføring af det nye element fra bagenden (Enqueue).
- Sletning af elementet fra forenden (Dequeue).
Køen kan implementeres på to måder
- Statisk (Brug af arrays)
- Dynamisk (Brug af pegepinde)
Begrænsningen af den lineære kø er, at den skaber et scenario, hvor der ikke kan tilføjes et nyt element i køen, selvom køen indeholder de tomme mellemrum. Denne situation er illustreret i nedenstående figur. Her peger bagsiden på det sidste indeks, mens alle kasser er tomme stadig, der kan ikke tilføjes noget nyt element.
Definition af cirkulær kø
En cirkulær kø er en variant af den lineære kø, som effektivt overvinder begrænsningen af den lineære kø. I cirkulær kø tilføjes det nye element i køens første position, hvis sidstnævnte er optaget og plads er tilgængeligt. Når det kommer til lineær kø, kan indsættelsen kun udføres fra bagenden og sletning fra forenden. I en fuld kø efter at have udført serier af efterfølgende sletninger i køen opstår der en bestemt situation, hvor der ikke kan tilføjes noget nyt element, selvom der er plads til rådighed, fordi understrømstilstanden (bageste = max - 1) stadig eksisterer.
Cirkelkøen forbinder de to ender gennem en peger, hvor det allerførste element kommer efter det sidste element. Det holder også styr på front og bag ved at implementere nogle ekstra logik, så den kan spore de elementer, der skal indsættes og slettes. Med dette genererer den cirkulære kø ikke overløbstilstanden, før køen er fuld i virkeligheden.
Nogle betingelser efterfulgt af den cirkulære kø:
- Front skal pege på det første element.
- Køen vil være tom, hvis Front = Bagside.
- Når et nyt element er tilføjet, øges køen med værdi 1 (Bag = Bag + 1).
- Når et element slettes fra køen, forhøjes fronten med en (Front = Front + 1).
Nøgleforskelle mellem lineær kø og cirkulær kø
- Den lineære kø er en ordnet liste, hvori dataelementer er organiseret i sekventiel rækkefølge. I modsætning hertil lagrer den cirkulære kø dataene i cirkulær mode.
- Lineær kø følger FIFO-ordren for at udføre opgaven (elementet tilføjet i den første position vil blive slettet i den første position). Omvendt kan rækkefølgen af operationer udført på et element i den cirkulære kø ændres.
- Indsætningen og sletningen af elementerne er fastsat i lineær kø, dvs. tilsætning fra bagenden og sletning fra frontenden. På den anden side er den cirkulære kø i stand til at indsætte og slette elementet fra et hvilket som helst punkt, indtil det ikke er optaget.
- Lineær kø spilder hukommelsespladsen, mens den cirkulære kø gør effektiv udnyttelse af rummet.
Gennemførelse af den lineære kø
Den nedenfor givne algoritme viser tilsætningen af elementer i en kø:
Køen har brug for tre datavariabler, herunder et array til at gemme køen og andre for at gemme den forreste og bageste startposition, der er -1.
indsæt (emne, kø, n, bag) {hvis (bag = = n) og tryk derefter på "kø overløb"; ellers {bag = bag + 1; kø [bag] = element; }} Den nedenfor givne algoritme illustrerer sletningen af elementer i en kø:
delete_circular (vare, kø, bag, front) {hvis (bag = = front) og tryk derefter på "køunderstrømning"; ellers {front = front + 1; item = kø [front]; }} Gennemførelse af den cirkulære kø
En algoritme til at fortolke tilsætningen af elementet i den cirkulære kø:
insert_circular (vare, kø, bag, front) {bag = = bag + 1) mod n; hvis (forreste == bag) tryk derefter på "køen er fuld"; ellers {kø [bag] = element; }} Algoritmen forklarer sletningen af elementet i den cirkulære kø:
delete_circular (vare, kø, bag, front) {hvis (foran == bag) og tryk derefter på ("kø er tom"); ellers {front = front + 1; item = kø [front]; }} Konklusion
Den lineære kø er ineffektiv i visse tilfælde, hvor elementerne skal skifte til de ledige rum for at udføre indsættelsesoperationer. Det er derfor, at det har tendens til at spilde lagerpladsen, mens den cirkulære kø gør passende brug af lagerplads, da elementerne tilføjes på en hvilken som helst position, hvis der eksisterer et tomt rum.
