En begyndervejledning til forståelse af køer og prioriterede køer

Som programmerer vil du arbejde med forskellige datastrukturer afhængigt af omfanget af dine projekter. Et sådant koncept er en kødatastruktur; køer er afgørende for studerende og bruges i mange vigtige algoritmer. Ligesom køer deler prioritetskøer et lignende koncept, men har et par grundlæggende forskelle.

Læs videre for at forstå køer og prioritetskøer.

Hvad er en kø?

En kø er en simpel datastruktur, der har en række forskellige applikationer i virkelige kodningsprojekter. Datastrukturer er i sagens natur abstrakte, men for enkelhedens skyld forestiller vi os, at en kødatastruktur har en lineær form med to forskellige ender.

Med hensyn til tidskompleksitet tillader en kø indsættelse (enqueue) og sletning (dequeue) i O (1) tid. På grund af sin asymptotiske effektivitet er køer effektive til store datasæt. Køer er først-i-først-ud (FIFO) i naturen, hvilket betyder, at et dataelement, der indsættes først, får adgang først. I modsætning hertil har stakke en last-in-first-out (LIFO) karakter og har kun en åben ende.

Forestil dig en billetkø i en biograf; hver ny kunde, der ankommer, kommer i køen i den ene ende. En efter en køber hver kunde en billet og forlader køen fra frontenden. Køens datastruktur fungerer præcist som enhver kø i den virkelige verden, og data indsættes (enqueue) i den ene ende og fjernes (dequeue) i den anden ende. Du kan nu forhåbentlig forstå begrundelsen for, hvorfor køer følger en FIFO -metode.

En kø har masser af virkelige kodningsapplikationer. Det bruges mere almindeligt i applikationer, hvor data ikke behøver at blive behandlet med det samme, men snarere i en FIFO -ordre. Diskplanlægning, asynkron dataoverførsel, semaforer er nogle typiske applikationer. Først til mølle-planlægningsopgaver, f.eks. Printspooling eller inputenhedsbuffere, bruger også en kø.

Hvad er en prioritetskø?

En prioritetskø ligner en kø, men den har yderligere egenskaber. Når et dataelement er placeret i prioritetskøen, får det et prioritetsnummer. I modsætning til dequeuing af en standard kø, dataelementer med en høj prioritet er dequeued før dataelementer med en lav prioritet. Prioritet afløser ankomstrækkefølgen i en prioritetskø, hvorfor prioritetskøer ikke har en konsekvent FIFO -karakter.

Relaterede: Algoritmer, som alle programmerere burde vide

Programmerere kan implementere en prioritetskø på flere måder. En ligetil implementering er at bruge en matrix med et struct/class dataelement, og dataelementet vil indeholde prioriteten for hvert dataelement og selve dataene. En anden primitiv prioritetskøimplementering er at bruge en sammenkædet liste. Prioritetskøer implementeret via sammenkædede lister er funktionelle, men ikke ideelle på grund af deres ydeevne.

Du kan implementere en kø med bedre prioritet med en bunke. Hvis du husker det, giver binære dynger det maksimale eller minimale element i 0 (1) tid, og indsættelse tager kun 0 (logN) tid. Ved hjælp af bunker giver prioritetskøer en bedre ydeevne asymptotisk sammenlignet med køer eller arrays.

En prioritetskø har også en række vigtige applikationer. Prioritetskøer er afgørende i grafalgoritmer som Prim’s Minimum Spanning Tree og Dijkstra's Shortest Path -algoritme. De er også ideelle til procesplanlægningsalgoritmer for computerbehandlingsenheder (CPU).

Lær datastrukturer

Køer og prioritetskøer er vigtige datastrukturer for alle begyndere. Det er afgørende, at eleverne er trygge ved at implementere disse datastrukturer og bruge dem i forskellige projekter.

Andre datastrukturer som bunker, stakke og træer er lige så vigtige for studerende og fagfolk. Det er også meget almindeligt, at interviewere spørger ansøgere om datastrukturer.

Efter at have læst denne artikel, skulle du nu have en god idé om, hvordan køer og prioritetskøer fungerer. Hvis alt stadig virker lidt uklart, får du styr på disse, efterhånden som du får mere erfaring med at bruge dem.

Bunker vs. Stakke: Hvad adskiller dem fra hinanden?

Du har hørt om dynger og stakke, men hvornår skal du bruge den ene frem for den anden?

Læs Næste

Om forfatteren