Anbefalt, 2021

Redaksjonens

Forskjellen mellom Linear Queue og Circular Queue

En enkel lineær kø kan implementeres på tre forskjellige måter, blant hvilke en av typene er en sirkulær kø. Forskjellen mellom lineær og sirkulær kø ligger i struktur- og ytelsesfaktorene. Den vesentlige forskjellen mellom den lineære køen og den sirkulære køen er at den lineære køen forbruker mer plass enn den sirkulære køen, mens den sirkulære køen ble utformet for å begrense minneutslippet av den lineære køen.

Køen kan beskrives som ikke-primær lineær datastruktur følger FIFO-rekkefølgen der dataelementer settes inn fra den ene enden (bakenden) og slettes fra den andre enden (frontend). De andre variasjonene i køen er den sirkulære køen, den dobbelte sluttkøen og prioritetskøen.

Sammenligningstabel

Grunnlag for sammenligningLineær køSirkulær kø
grunn~~POS=TRUNCOrganiserer dataelementene og instruksjonene i sekvensiell rekkefølge etter hverandre.Ordner dataene i det sirkulære mønsteret hvor det siste elementet er koblet til det første elementet.
Ordre av oppgavegjennomføring
Oppgaver utføres for at de ble plassert før (FIFO).Bestilling av å utføre en oppgave kan endres.
Innsetting og sletting
Det nye elementet legges fra bakenden og fjernes fra fronten.Innsetting og sletting kan gjøres på alle steder.
Opptreden
Ineffektiv
Fungerer bedre enn den lineære køen.

Definisjon av Linear Queue

En lineær kø er rasjonelt en første i først utbestilt liste. Det er såkalt lineært fordi det ligner på en rett linje der elementene er plassert etter hverandre. Den inneholder en homogen samling av elementene der nye elementer legges til i den ene enden og slettes fra en annen ende. Konseptet av køen kan forstås ved et eksempel på en kø av publikum som venter utenom billettrenten for å få teaterbilletten. I denne køen kommer personen til den bakre enden av køen for å ta billetten og billetten utstedes på forsiden av køen.

Det er flere operasjoner som utføres i køen

  • For det første blir køen initialisert til null (dvs. tom).
  • Bestem om køen er tom eller ikke.
  • Bestem om køen er full eller ikke.
  • Innføring av det nye elementet fra bakenden (Enqueue).
  • Sletting av elementet fra frontenden (dequeue).

Køen kan implementeres på to måter

  • Statisk (Bruk av arrays)
  • Dynamisk (Bruke pekere)

Begrensningen av den lineære køen er at den skaper et scenario der ikke noe nytt element kan legges i køen, selv om køen inneholder de tomme mellomrom. Denne situasjonen ovenfor er illustrert i figuren nedenfor. Her peker baksiden på den siste indeksen mens alle boksene er tomme fortsatt, ingen nytt element kan legges til.

Definisjon av Circular Queue

En sirkulær kø er en variant av den lineære køen som effektivt overstyrer begrensningen av den lineære køen. I sirkulær kø blir det nye elementet lagt til i den første posisjonen av køen hvis den siste er opptatt og plass er tilgjengelig. Når det gjelder lineær kø, kan innsetting bare utføres fra bakenden og sletting fra frontenden. I en full kø etter å ha utført serier av påfølgende sletninger i køen oppstår en viss situasjon der det ikke kan legges til noe nytt element selv om plassen som er tilgjengelig fordi understrømstilstanden (Bak = maks - 1) fortsatt eksisterer.

Sirkulær kø forbinder de to ender gjennom en peker, der det allerste elementet kommer etter det siste elementet. Det holder også oversikt over front og bak ved å implementere litt ekstra logikk slik at den kan spore elementene som skal settes inn og slettes. Med dette genererer ikke den sirkulære køen overløpstilstanden til køen er full i faktisk.

Noen forhold etterfulgt av den sirkulære køen:

  • Front må peke på det første elementet.
  • Køen vil være tom hvis Front = Bakre.
  • Når et nytt element er lagt til, økes køen med verdi en (Bak = Bak + 1).
  • Når et element slettes fra køen, økes fronten med en (Front = Front + 1).

Viktige forskjeller mellom lineær kø og sirkulær kø

  1. Den lineære køen er en bestilt liste der dataelementer er organisert i sekvensiell rekkefølge. I kontrast lagrer sirkulær kø dataene i sirkulær modus.
  2. Linjær kø følger FIFO-ordren for å utføre oppgaven (elementet lagt til i den første stillingen skal slettes i første posisjon). Omvendt, i den sirkulære køen, kan rekkefølgen av operasjoner som utføres på et element, endres.
  3. Innsetting og sletting av elementene er fikset i lineær kø, dvs. tillegg fra bakenden og sletting fra frontenden. På den annen side er den sirkulære køen i stand til å sette inn og slette elementet fra et hvilket som helst punkt til det ikke er opptatt.
  4. Linjær kø slipper minneplassen mens sirkulær kø gjør effektiv bruk av plass.

Gjennomføring av den lineære køen

Algoritmen gitt nedenfor illustrerer tillegg av elementer i en kø:
Køen trenger tre datavariabler, inkludert ett array for å lagre køen og andre for å lagre front- og bakre startposisjon som er -1.

 sett inn (element, kø, n, bak) {hvis (bak = = n) og skriv ut "køoverløp"; ellers {bak = bak + 1; kø [bak] = element; }} 

Algoritmen gitt nedenfor illustrerer sletting av elementer i en kø:

 delete_circular (vare, kø, bak, foran) {hvis (bak = = foran) og skriv ut "kø understrøm"; ellers {front = front + 1; item = kø [front]; }} 

Gjennomføring av den sirkulære køen

En algoritme for å tolke tillegg av elementet i den sirkulære køen:

 insert_circular (vare, kø, bak, foran) {bakre = (bak + 1) mod n; hvis (foran == bak) og skriv ut "køen er full"; ellers {kø [bak] = element; }} 

Algoritmen forklarer sletting av elementet i den sirkulære køen:

 delete_circular (vare, kø, bak, foran) {hvis (foran == bak) og skriv ut ("køen er tom"); ellers {front = front + 1; item = kø [front]; }} 

Konklusjon

Den lineære køen er ineffektiv i visse tilfeller der elementene er pålagt å skifte til ledige mellomrom for å utføre innføringsoperasjon. Det er grunnen til at det har en tendens til å kaste bort lagringsplassen mens sirkulær kø gjør riktig bruk av lagringsplass ettersom elementene er lagt til i en hvilken som helst posisjon hvis det finnes et tomrom.

Top