En nybörjarguide för att förstå köer och prioriterade köer

Som programmerare kommer du att arbeta med olika datastrukturer beroende på omfattningen av dina projekt. Ett sådant koncept är en ködatastruktur; köer är viktiga för studenter och används i många viktiga algoritmer. Precis som köer delar prioritetsköer ett liknande koncept men har några grundläggande skillnader.

Läs vidare för att förstå köer och prioritetsköer.

Vad är en kö?

En kö är en enkel datastruktur som har en mängd olika applikationer i verkliga kodningsprojekt. Datastrukturer är i sig abstrakta, men för enkelhetens skull föreställer vi oss att en ködatastruktur har en linjär form med två olika ändar.

När det gäller tidskomplexitet tillåter en kö insättning (enqueue) och radering (dequeue) i O (1) -tid. På grund av sin asymptotiska effektivitet är köer effektiva för stora datamängder. Köer är först-in-först-ut (FIFO) i naturen, vilket innebär att ett dataobjekt som infogas först kommer åt först. Däremot har staplar en LIFO-typ (last-in-first-out) och har bara en öppen ände.

Föreställ dig en biljettkö på en bio; varje ny kund som kommer ansluter sig till kön i ena änden. En efter en köper varje kund en biljett och lämnar kön från fronten. Kodatastrukturen fungerar precis som alla verkliga köer, och data sätts in (enqueue) i ena änden och tas bort (dequeue) i den andra änden. Du kan nu förhoppningsvis förstå resonemanget om varför köer följer en FIFO -metod.

En kö har massor av verkliga kodningsapplikationer. Det används mer ofta i applikationer där data inte behöver bearbetas omedelbart utan snarare i en FIFO -beställning. Diskplanering, asynkron dataöverföring, semaforer är några typiska applikationer. Först till kvarn-planering schemaläggningsuppgifter som utskriftsspolning eller inmatningsenhetsbuffertar använder också en kö.

Vad är en prioritetskö?

En prioritetskö liknar en kö, men den har ytterligare egenskaper. När ett dataelement placeras i prioritetskön ges det ett prioritetsnummer. I motsats till avlägsnande av en standardkö utmatas dataelement med hög prioritet före dataelement med låg prioritet. Prioritet ersätter ankomstordningen i en prioritetskö, varför prioritetsköer inte har en konsekvent FIFO -karaktär.

Relaterad: Algoritmer som alla programmerare borde veta

Programmerare kan implementera en prioritetskö på flera sätt. En enkel implementering är att använda en matris med ett struktur/klassdataobjekt, och dataposten kommer att innehålla prioriteten för varje dataelement och själva datan. En annan primitiv prioritetsköimplementering är att använda en länkad lista. Prioritetsköer implementerade via länkade listor är funktionella men inte idealiska på grund av deras prestanda.

Du kan implementera en kö med bättre prioritet med en hög. Om du kommer ihåg ger binära högar det maximala eller lägsta elementet på 0 (1) tid, och införandet tar bara 0 (logN) tid. Med hjälp av högar ger prioritetsköer en bättre prestanda asymptotiskt jämfört med köer eller matriser.

En prioritetskö har också en mängd viktiga applikationer. Prioritetsköer är avgörande i grafalgoritmer som Prims Minimum Spanning Tree och Dijkstra's Shortest Path -algoritm. De är också idealiska i processplaneringsalgoritmer för datorbearbetningsenhet (CPU).

Lär dig datastrukturer

Köer och prioritetsköer är viktiga datastrukturer för alla nybörjare. Det är viktigt att eleverna trivs med att implementera dessa datastrukturer och använda dem i olika projekt.

Andra datastrukturer som högar, stackar och träd är lika viktiga för studenter och proffs. Det är också mycket vanligt att intervjuare ifrågasätter sökande om datastrukturer.

Efter att ha läst den här artikeln bör du nu ha en bra uppfattning om hur köer och prioritetsköer fungerar. Om allt fortfarande verkar lite oklart kommer du att ta tag i dessa när du får mer erfarenhet av att använda dem.

Högar vs. Staplar: Vad skiljer dem åt?

Du har hört talas om högar och staplar, men när ska du använda det ena över det andra?

Läs Nästa

Om författaren