En nybegynnerguide for å forstå køer og prioriterte køer

Som programmerer vil du jobbe med forskjellige datastrukturer avhengig av omfanget av prosjektene dine. Et slikt konsept er en kødatastruktur; køer er avgjørende for studenter og brukes i mange viktige algoritmer. Som køer deler prioritetskøer et lignende konsept, men har noen få grunnleggende forskjeller.

Les videre for å forstå køer og prioritetskøer.

Hva er en kø?

En kø er en enkel datastruktur som har en rekke applikasjoner i virkelige kodingsprosjekter. Datastrukturer er iboende abstrakte, men for enkelhets skyld forestiller vi oss at en kødatastruktur har en lineær form med to forskjellige ender.

Når det gjelder tidskompleksitet, tillater en kø innsetting (enqueue) og sletting (dequeue) i O (1) tid. På grunn av sin asymptotiske effektivitet er køer effektive for store datasett. Køer er først-inn-først-ut (FIFO) i naturen, noe som betyr at et dataelement som settes inn først vil bli åpnet først. I kontrast har stabler en LIFO-karakter (last-in-first-out) og har bare en åpen ende.

Tenk deg en billettkø på en kino; hver nye kunde som kommer, kommer i køen i den ene enden. En etter en kjøper hver kunde en billett og forlater køen fra frontenden. Kodatastrukturen fungerer nøyaktig som enhver ekte kø, og data settes inn (enqueue) i den ene enden og fjernes (dequeue) i den andre enden. Du kan nå forhåpentligvis forstå begrunnelsen for hvorfor køer følger en FIFO -metode.

En kø har mange virkelige kodingsprogrammer. Det er mer vanlig brukt i applikasjoner der data ikke trenger å bli behandlet umiddelbart, men heller i en FIFO -ordre. Diskplanlegging, asynkron dataoverføring, semaforer er noen typiske applikasjoner. Førstemann til mølla-planleggingsoppgaver som utskriftskøling eller inndatabuffere bruker også en kø.

Hva er en prioritetskø?

En prioritetskø ligner en kø, men den har flere egenskaper. Når et dataelement blir ført inn i prioritetskøen, får det et prioritetsnummer. I motsetning til dequeuing av en standard kø, blir dataelementer med høy prioritet dequeued før dataelementer med lav prioritet. Prioritet erstatter ankomstrekkefølgen i en prioritetskø, og derfor har prioritetskøer ikke en konsekvent FIFO -karakter.

I slekt: Algoritmer som alle programmerere burde vite

Programmerere kan implementere en prioritetskø på flere måter. En enkel implementering er å bruke en matrise med et struktur/klasse dataelement, og dataelementet vil inneholde prioriteten til hvert dataelement og selve dataene. En annen primitiv prioritetskøimplementering er å bruke en koblet liste. Prioritetskøer implementert gjennom koblede lister er funksjonelle, men ikke ideelle på grunn av ytelsen.

Du kan implementere en kø med bedre prioritet med en haug. Hvis du husker, gir binære hauger maksimum eller minimum element i 0 (1) tid, og innsetting tar bare 0 (logN) tid. Ved hjelp av hauger gir prioriterte køer en bedre ytelse asymptotisk sammenlignet med køer eller matriser.

En prioritetskø har også en rekke viktige applikasjoner. Prioritetskøer er avgjørende i grafalgoritmer som Prims Minimum Spanning Tree og Dijkstra's Shortest Path -algoritme. De er også ideelle i prosessplanleggingsalgoritmer for databehandlingsenheter (CPU).

Lær datastrukturer

Køer og prioritetskøer er viktige datastrukturer for alle nybegynnere. Det er avgjørende at elevene er komfortable med å implementere disse datastrukturer og bruke dem i forskjellige prosjekter.

Andre datastrukturer som hauger, stabler og trær er like viktige for studenter og profesjonelle. Det er også veldig vanlig at intervjuere avhører søkere om datastrukturer.

Etter å ha lest denne artikkelen, bør du nå ha en god ide om hvordan køer og prioritetskøer fungerer. Hvis alt fortsatt virker litt uklart, får du tak i disse etter hvert som du får mer erfaring med å bruke dem.

Hopper vs. Stabler: Hva skiller dem fra hverandre?

Du har hørt om dynger og stabler, men når bør du bruke den ene fremfor den andre?

Les neste

Om forfatteren