Pradedančiųjų vadovas, kaip suprasti eiles ir prioritetines eiles

Kaip programuotojas, jūs dirbsite su skirtingomis duomenų struktūromis, priklausomai nuo jūsų projektų apimties. Viena iš tokių sąvokų yra eilės duomenų struktūra; eilės yra būtinos studentams ir yra naudojamos daugelyje svarbių algoritmų. Kaip ir eilės, prioritetinės eilės turi panašią koncepciją, tačiau turi keletą esminių skirtumų.

Skaitykite toliau, kad suprastumėte eiles ir prioritetines eiles.

Kas yra eilė?

Eilė yra paprasta duomenų struktūra, turinti daugybę pritaikymų realiame gyvenime. Duomenų struktūros iš esmės yra abstrakčios, tačiau dėl paprastumo mes įsivaizduojame, kad eilės duomenų struktūra turi linijinę formą su dviem skirtingais galais.

Kalbant apie laiko sudėtingumą, eilė leidžia įterpti (sudėlioti) ir ištrinti (atidėti) O (1) laiku. Dėl asimptotinio efektyvumo eilės yra veiksmingos dideliems duomenų rinkiniams. Eilės yra pirmojo iš pirmo (FIFO) pobūdžio, tai reiškia, kad pirmiausia bus pasiektas duomenų elementas, kuris įterptas pirmiausia. Priešingai, kaminai turi paskutinio įvedimo (LIFO) pobūdį ir turi tik vieną atvirą galą.

Įsivaizduokite bilietų eilę kine; kiekvienas naujas klientas ateina į eilę viename gale. Kiekvienas klientas vienas po kito perka bilietą ir išeina iš eilės. Eilės duomenų struktūra veikia lygiai taip pat, kaip ir bet kuri realaus pasaulio eilė, o duomenys įterpiami (sustatomi) viename gale ir pašalinami (dequeue) kitame gale. Dabar galite tikėtis suprasti, kodėl eilės laikosi FIFO metodikos.

Eilėje yra daug realaus gyvenimo kodavimo programų. Jis dažniau naudojamas programose, kuriose duomenų nereikia apdoroti iš karto, o FIFO tvarka. Disko planavimas, asinchroninis duomenų perdavimas, semaforai yra keletas tipiškų programų. Planavimo užduotys, kurios pirmas ateina, tarnauja, pvz., Spausdinimo keitimas arba įvesties įrenginio buferiai, taip pat naudoja eilę.

Kas yra prioritetinė eilė?

Prioritetinė eilė yra panaši į eilę, tačiau ji turi papildomų savybių. Kai duomenų elementas įtraukiamas į prioritetų eilę, jam suteikiamas prioriteto numeris. Priešingai nei standartinės eilės panaikinimas, duomenų elementai, turintys aukštą prioritetą, yra panaikinami prieš duomenų elementus su mažu prioritetu. Prioritetas pakeičia atvykimo į prioritetų eilę tvarką, todėl prioritetinės eilės neturi nuoseklaus FIFO pobūdžio.

Susijęs: Algoritmai, kuriuos turėtų žinoti kiekvienas programuotojas

Programuotojai gali įgyvendinti prioritetų eilę keliais būdais. Paprastas įgyvendinimas yra naudoti masyvą su struktūros/klasės duomenų elementu, o duomenų elemente bus kiekvieno duomenų elemento ir pačių duomenų prioritetas. Kitas primityvus prioritetų eilės įgyvendinimas yra susieto sąrašo naudojimas. Prioritetinės eilės, įdiegtos per susietus sąrašus, yra funkcionalios, tačiau dėl savo našumo nėra idealios.

Su kaupu galite įgyvendinti geresnę prioritetų eilę. Jei prisimenate, dvejetainiai krūvos suteikia maksimalų arba mažiausią elementą per 0 (1) laiko, o įterpimas trunka tik 0 (logN) laiko. Naudojant krūvas, prioritetinės eilės suteikia geresnį našumą asimptomiškai, palyginti su eilėmis ar masyvais.

Prioritetinėje eilėje taip pat yra įvairių svarbių programų. Prioritetinės eilės yra labai svarbios grafiko algoritmams, tokiems kaip Prim minimalus apimties medis ir Dijkstra trumpiausio kelio algoritmas. Jie taip pat idealiai tinka kompiuterio procesoriaus (CPU) procesų planavimo algoritmuose.

Sužinokite duomenų struktūras

Eilės ir prioritetinės eilės yra svarbios duomenų struktūros visiems pradedantiesiems. Labai svarbu, kad studentai galėtų patogiai diegti šias duomenų struktūras ir naudoti jas įvairiuose projektuose.

Kitos duomenų struktūros, tokios kaip krūvos, krūvos ir medžiai, yra vienodai svarbios studentams ir profesionalams. Taip pat labai dažnai pašnekovai apklausia pareiškėjus dėl duomenų struktūrų.

Perskaitę šį straipsnį, dabar turėtumėte gerai suprasti, kaip veikia eilės ir prioritetinės eilės. Jei viskas vis tiek atrodo šiek tiek neaišku, įgysite daugiau patirties, kai naudosite juos.

Krūvos vs. Kaminai: kas juos skiria?

Jūs girdėjote apie „Heaps and Stacks“, bet kada turėtumėte naudoti vieną kitą?

Skaityti toliau

Apie autorių