Prioritetskøer i JavaScript

En prioritert kø er en utvidelse av en enkel kølitedatastruktur med elementer som inneholder en prioriteringsverdi, en kø er en samling av elementer der det første elementet som kommer inn i køen er det første elementet som kommer ut av en kø. Denne utførelsesteknikken er kjent som FIFO (først inn og først ut). Tenk på en rekke mennesker som står utenfor en minibank, personen som skal stå først i linjen vil være den som bruker minibanken først. Personen som blir med sent i køen for minibanken, vil være den siste som bruker minibanken.

Så nå vet vi hva som er en grunnleggende kø, men hva med prioriteringskøen? I prioriteringskøen har hvert element som kommer inn i køen to verdier, en prioriteringsverdi og dataene. Elementene som har samme prioriteringsverdi vil bli utført basert på FIFO (først inn og først ut) Men elementer med høyere prioritet enn andre vil bli utført først uansett når de ble lagt inn i køen.

Dette er et avansert datastrukturemne, så vi antar at du er kjent med hvordan JavaScript fungerer og de grunnleggende funksjonalitetene til JavaScript. For å implementere en prioriteringskø i JavaScript må vi først vite hvordan vi skal implementere en enkel kø i JavaScript.

Implementering av en kø i JavaScript

Datastrukturkonseptene som køer, stabler, hauger eller prioriterte køer implementeres ved hjelp av matriser i JavaScript.

La oss definere en funksjon som vil definere strukturen vår:

funksjonskø ()
// senere kode vil bli plassert her inne

Vi vet at køer implementeres med matriser, så vi skal lage en matrise som heter Collections

Inne i funksjonen:

Array = [];

For å implementere køens datastruktur trenger vi for å implementere følgende funksjonaliteter:

• Enqueue: For å legge til et nytt element på slutten av listen
• Dequeue: For å fjerne det første elementet fra listen
• Isempty: For å sjekke om køen er tom eller ikke
• Størrelse: For å returnere lengden på køen
• Foran: For å returnere verdien av det første elementet på listen
• Skriv ut: For å skrive ut køen

Disse funksjonalitetene blir alle enkelt lagt til ved å bruke følgende kodelinjer:

funksjonQueue ()
Array = [];
dette.print = funksjon ()
konsoll.logg (matrise);
;
dette.enqueue = funksjon (newMem)
Array.Push (Newmem);
;
dette.dequeue = funksjon ()
ReturnArray.skifte();
;
dette.front = funksjon ()
Returmarray [0];
;
dette.størrelse = funksjon ()
ReturnArray.lengde;
;
dette.isEmpty = funksjon ()
Retur (Array.lengde === 0);
;

Nå, at vi har datastrukturen klar, må vi lage et objekt som er kartlagt til denne strukturen, vi gjør det ved å bruke linjen:

var newqueue = new kø ();

Nå trenger vi noen elementer som skal plasseres i køen, vi gjør det ved å bruke følgende linjer:

newqueue.enqueue ('a');
newqueue.enqueue ('b');
newqueue.enqueue ('c');

For å se på hvordan køen vår ser ut akkurat nå, kan vi kalle utskriftsfunksjonen slik:

newqueue.skrive ut();

Vi får følgende utgang på konsollen vår:

For å teste, hvis første-inn og første-ut-implementeringen fungerer som den skal, vil vi avgjøre et element fra listen, og skrive ut den fremste verdien og deretter skrive ut hele gjenværende køen med følgende linjer:

newqueue.dequeue ();
konsoll.Logg (Newqueue.front());
newqueue.skrive ut();

Den komplette kodebiten til køstrukturen er:

funksjonQueue ()
Array = [];
dette.print = funksjon ()
konsoll.logg (matrise);
;
dette.enqueue = funksjon (newMem)
Array.Push (Newmem);
;
dette.dequeue = funksjon ()
ReturnArray.skifte();
;
dette.front = funksjon ()
Returmarray [0];
;
dette.størrelse = funksjon ()
ReturnArray.lengde;
;
dette.isEmpty = funksjon ()
ReturnArray.lengde === 0;
;

varnewQueue = new Queue ();
newqueue.enqueue ("a");
newqueue.enqueue ("b");
newqueue.enqueue ("c");
newqueue.skrive ut();
newqueue.dequeue ();
konsoll.Logg (Newqueue.front());
newqueue.skrive ut();

Når vi utfører denne koden, kan vi observere følgende resultat på konsollen:

Så da vi kalte Dequeue -funksjonen, fjernet det det første elementet fra listen. Etter det sjekket vi etter det fremste elementet i køen som var “B”. Så skrev vi ut køen igjen, og det ga oss den gjenværende køen i riktig rekkefølge. Dette betyr at køimplementeringen vår fungerer perfekt:

Implementering av en prioriteringskø i JavaScript

Vi vet at forskjellen mellom en normal kø og en prioriteringskø er at elementene i prioriteringskøen inneholder en prioriteringsverdi sammen med dataene deres. Dette betyr at all funksjonaliteten til prioriteringskøen er den samme som en normal kø bortsett fra Enqueue -funksjon.

I prioriterte køer plasserer enqueue -funksjonen, det høyere prioriterte elementet før det lavere prioriterte elementet. Og hvis to eller flere elementer har samme prioritet, plasseres nylig tilførte elementer i den senere enden av køen for å opprettholde en første og første-out verdsettelsesmetode.

Så når vi husker at vi kan skrive den nye enqueue -funksjonen for prioriteringskøen med følgende kodelinjer:

dette.enqueue = funksjon (newMem)
var array = [];
// senere kode vil bli plassert her inne
;

Det første vi gjør i enqueue -funksjonen er at hvis samlingen er tom, så skyver vi bare elementet på køen:

hvis dette.er tom())
Array.Push (Newmem);

Hvis køen ikke er tom:

• Så skal vi sjekke prioriteten til det nye elementet med prioriteringen av hvert element i køen
• Hvis prioriteten til det nye elementet er lavere enn samlingens element.Vi skal legge til det nye elementet på før samlingenes element
• Dette er fordi 1 betyr førsteprioritet mens 2 betyr andre prioritet
• Hvis prioriteringen av det nye elementet som er større i verdi (lavere i faktisk prioritet), vil vi flytte til slutten av køen og legge til elementet der

annet
var lagt til = falsk;
for (vari = 0; iif (newmem [1] < array[i][1])
Array.Splice (i, 0, Newmem);
lagt til = sant;
gå i stykker;


hvis (!la til)
Array.Push (Newmem);

Hele enqueue funksjon vil se slik ut:

dette.enqueue = funksjon (newMem)
hvis dette.er tom())
Array.Push (Newmem);
annet
var lagt til = falsk;
for (vari = 0; iif (newmem [1] < array[i][1])
Array.Splice (i, 0, Newmem);
lagt til = sant;
gå i stykker;


hvis (!la til)
Array.Push (Newmem);


;

Resten av prioriteringskøfunksjonene er stort sett de samme som normal kø, med en liten endring i dequeue -funksjonen for bare å vise navnet og ikke verdien av elementet. Hele prioritert kølodsutdrag er som:

FunctionPriorityQueue ()
vararray = [];
dette.printCollection = funksjon ()
konsoll.logg (matrise);
;
dette.enqueue = funksjon (newMem)
hvis dette.er tom())
Array.Push (Newmem);
annet
var lagt til = falsk;
for (vari = 0; iif (newmem [1] Array.Splice (i, 0, Newmem);
lagt til = sant;
gå i stykker;


hvis (!la til)
Array.Push (Newmem);


;
dette.dequeue = funksjon ()
var verdi = matrise.skifte();
returverdi [0];
;
dette.front = funksjon ()
ReturnArray [0];
;
dette.størrelse = funksjon ()
ReturnArray.lengde;
;
dette.isEmpty = funksjon ()
ReturnArray.lengde === 0;
;

På tide å sette elementer i køen ved hjelp av følgende kodelinjer:

var pq = new PriorityQueue ();
pq.Enqueue (["Google", 2]);
pq.enqueue (["bing", 3]);
pq.Enqueue (["Microsoft", 1]);
pq.enqueue (["eple", 2]);
pq.printCollection ();

Som du kan se, er første prioritet “Microsoft” element med verdi 1. Det må være i starten av køen selv om den ble lagt til på 3. plass.

Nå, hvis vi kaller Dequeue -funksjonen og deretter utskriftsfunksjonen igjen, bør det første elementet fjernes fra listen:

pq.dequeue ();
pq.printCollection ();

Der du går, fungerer vår prioriteringskø perfekt.

Konklusjon

Køer er datastrukturkonsepter som fungerer med verdsettelsesmetoden til første og første-ut. Tilsvarende fungerer prioriterte køer med verdsettelse av første og første-ut, men med en ekstra verdi av "prioritet", vil elementet med høyest prioritet bli utført først uansett når de ble lagt til i køen. I dette innlegget lærte vi hvordan vi implementerer en enkel kø i JavaScript og hvordan du bruker den datastrukturen til å implementere arbeidet med en prioriteringskø.