Príručka pre začiatočníkov k porozumeniu frontám a prioritným frontám

Ako programátor budete pracovať s rôznymi dátovými štruktúrami v závislosti od rozsahu vašich projektov. Jeden taký koncept je dátová štruktúra frontu; fronty sú pre študentov nevyhnutné a používajú sa v mnohých dôležitých algoritmoch. Rovnako ako fronty, aj prioritné fronty majú podobný koncept, ale majú niekoľko zásadných rozdielov.

Pokračujte v čítaní, aby ste pochopili rady a prioritné fronty.

Čo je to front?

Fronta je jednoduchá dátová štruktúra, ktorá má množstvo aplikácií v projektoch kódovania v reálnom živote. Dátové štruktúry sú vo svojej podstate abstraktné, ale kvôli jednoduchosti si predstavujeme, že dátová štruktúra frontu má lineárny tvar s dvoma rôznymi koncami.

Pokiaľ ide o časovú náročnosť, front umožňuje vloženie (zaradenie do poradia) a vymazanie (vyradenie) v čase O (1). Vďaka svojej asymptotickej účinnosti sú fronty efektívne pre veľké množiny údajov. Fronty sú svojou povahou prvé v prvom rade (FIFO), čo znamená, že k dátovej položke, ktorá je vložená ako prvá, sa bude pristupovať najskôr. Naproti tomu zásobníky majú charakter LIFO (last-in-first-out-out) a majú iba jeden otvorený koniec.

Predstavte si rad lístkov v kine; každý nový zákazník, ktorý príde, sa zaradí do fronty na jednom konci. Každý jeden po druhom si kúpi lístok a opustí front z frontendu. Štruktúra údajov frontu funguje presne ako všetky fronty v reálnom svete a údaje sa vkladajú (zaraďujú do poradia) na jeden koniec a odstraňujú (radia) na druhom konci. Teraz už dúfame, že porozumiete dôvodom, prečo sa rady riadia metodikou FIFO.

Fronta má množstvo skutočných kódovacích aplikácií. Bežnejšie sa používa v aplikáciách, kde údaje nie je potrebné spracovať okamžite, ale skôr v poradí FIFO. Plánovanie disku, asynchrónny prenos údajov, semafory sú niektoré typické aplikácie. Fronty používajú aj úlohy plánovania, kto skôr príde, ten skôr slúži, ako napríklad zaraďovanie tlače alebo vyrovnávacia pamäť vstupného zariadenia.

Čo je to prioritný front?

Prioritný front je podobný frontu, ale má ďalšie vlastnosti. Keď je dátový prvok zaradený do frontu priorít, priradí sa mu číslo priority. Na rozdiel od odstavenia štandardného frontu sa dátové prvky s vysokou prioritou vyradia z radu pred dátovými prvkami s nízkou prioritou. Priorita nahrádza poradie príchodu do prioritného frontu, a preto prioritné fronty nemajú konzistentný charakter podľa FIFO.

Súvisiace: Algoritmy, ktoré by mal vedieť každý programátor

Programátori môžu implementovať prioritný front niekoľkými spôsobmi. Jednoduchou implementáciou je použitie poľa s údajovou položkou štruktúry/triedy a údajová položka bude obsahovať prioritu každého dátového prvku a samotných údajov. Ďalšou primitívnou implementáciou frontu s prioritou je použitie prepojeného zoznamu. Prioritné fronty implementované prostredníctvom prepojených zoznamov sú funkčné, ale vzhľadom na ich výkon nie sú ideálne.

Frontu s lepšou prioritou môžete implementovať hromadou. Ak si pamätáte, binárne haldy udávajú maximálny alebo minimálny prvok za čas 0 (1) a vloženie trvá iba 0 (logN). S pomocou hromád poskytujú prioritné fronty asymptoticky lepší výkon v porovnaní s frontmi alebo poľami.

Prioritný front má tiež množstvo dôležitých aplikácií. Prioritné fronty sú kľúčové v grafických algoritmoch, ako je Primov minimálny rozsah stromu a algoritmus najkratšej cesty Dijkstry. Sú tiež ideálne v algoritmoch plánovania procesov počítačovej procesorovej jednotky (CPU).

Naučte sa dátové štruktúry

Fronty a prioritné fronty sú dôležité dátové štruktúry pre všetkých začiatočníkov. Je dôležité, aby boli študenti spokojní s implementáciou týchto dátových štruktúr a ich používaním v rôznych projektoch.

Ostatné dátové štruktúry, ako sú haldy, komíny a stromy, sú pre študentov a profesionálov rovnako dôležité. Je tiež veľmi bežné, že sa anketári pýtajú žiadateľov na dátové štruktúry.

Po prečítaní tohto článku by ste teraz mali mať dobrú predstavu o tom, ako fronty a prioritné fronty fungujú. Ak sa vám všetko zdá byť trochu nejasné, s týmito sa poperiete, ako získate ďalšie skúsenosti s ich používaním.

Haldy vs. Stohy: Čo ich odlišuje?

Počuli ste o Haldách a Stackoch, ale kedy by ste mali používať jeden nad druhým?

Čítajte ďalej

O autorovi