Erinevus lineaarse järjekorra ja ümmarguse järjekorra vahel

2019

Lihtsat lineaarset järjekorda saab rakendada mitmel kolmel viisil, millest üks tüüp on ümmargune järjekord. Lineaarse ja ümmarguse järjekordade vahe seisneb struktuurilistes ja jõudlusfaktorites. Oluline erinevus lineaarse järje ja ringjoone vahel on see, et lineaarne järjekord tarbib rohkem ruumi kui ümmargune järjekord, samas kui ümmargune järjekord töötati välja, et piirata lineaarse järjekordi mälu raiskamist.

Järjekorra võib kirjeldada kui mitte-primitiivset lineaarset andmestruktuuri, mis järgib FIFO järjekorda, milles andmeelemendid sisestatakse ühest otsast (tagumine ots) ja kustutatakse teisest otsast (esiosa). Teised järjekordsed variandid on ümmargune järjekord, kahekordselt lõppenud järjekord ja prioriteedijärjekord.

Võrdluskaart

Võrdluse alus	Lineaarne järjekord	Ümmargune järjekord
Põhiline	Korraldab andmeelemendid ja -juhised üksteise järel järjestuses.	Korraldab andmed ümmarguse mustriga, kus viimane element on ühendatud esimese elemendiga.
Ülesande täitmise kord	Ülesanded täidetakse selleks, et need oleksid eelnevalt paigutatud (FIFO).	Ülesande täitmise kord võib muutuda.
Sisestamine ja kustutamine	Uus element lisatakse tagumisest otsast ja eemaldatakse esiosast.	Lisamise ja kustutamise saab teha igal positsioonil.
Toimivus	Ebatõhus	Töötab paremini kui lineaarne järjekord.

Lineaarse järjekorra määratlus

Lineaarne järjekord on ratsionaalselt esimene esimeses tellitud nimekirjas. Seda nimetatakse lineaarseks, kuna see sarnaneb sirgjoonega, kus elemendid paiknevad üksteise järel. See sisaldab homogeenset kogumit elementidest, milles ühele otsale lisatakse uusi elemente ja kustutatakse teisest otsast. Järjekorra mõistet saab mõista näiteks sellest, et vaatajaskond ootab väljaspool piletiloendajat, et teatripiletit saada. Selles järjekorras liitub isik pileti tagaotsas järjekorda ja pilet väljastatakse järjekorda.

Järjekorras on mitu toimingut

Esiteks lähtestatakse järjekord nullini (st tühi).
Määrake, kas järjekord on tühi või mitte.
Määrake, kas järjekord on täis või mitte.
Uue elemendi sisestamine tagumisest otsast (Enqueue).
Elemendi kustutamine esiosast (Dequeue).

Järjekorda saab rakendada kahel viisil

Staatiliselt (massiivide kasutamine)
Dünaamiliselt (osade kasutamine)

Lineaarse järjekorda piiramine on see, et see loob stsenaariumi, kus järjekorda ei saa lisada uut elementi isegi siis, kui järjekord sisaldab tühja ruumi. See ülaltoodud olukord on illustreeritud allpool toodud joonisel. Siin on tagaosa viimase indeksi suunas, samas kui kõik kastid on tühjad, uusi elemente ei saa lisada.

Ümmarguse järjekorra määratlus

Ümmargune järjekord on lineaarse järjekordi variant, mis ületab tõhusalt lineaarse järjekorda piiramise. Ümmarguses järjekorras lisatakse uus element järjekorra esimesele positsioonile, kui viimane on hõivatud ja ruumi on saadaval. Kui tegemist on lineaarse järjekorraga, võib sisestamise teha ainult tagumisest otsast ja kustutamist esiosast. Täielikus järjekorras pärast järjestikuste järjestikuste kustutamiste sooritamist tekib teatud olukord, kus ühtegi uut elementi ei saa lisada isegi siis, kui olemasolev ruum on allavoolu (taga = max - 1) veel olemas.

Ümmargune järjekord ühendab mõlemad otsad kursoriga, kus esimene element on pärast viimast elementi. Samuti jälgib see esi- ja tagaosa, rakendades mõningaid täiendavaid loogikaid, et oleks võimalik jälgida elemente, mis tuleb sisestada ja kustutada. Sellega ei tekita ümmargune järjekord ülevoolu seisundit enne, kui järjekord on tegelikus.

Mõned tingimused, millele järgneb ümmargune järjekord:

Ees peab olema esimene element.
Järjekord on tühi, kui esipaneel = taga.
Uue elemendi lisamisel suurendatakse järjekorda ühe väärtusega (tagumine = tagumine + 1).
Kui element kustutatakse järjekorrast, suurendatakse eesmist ühe võrra (eesmine = ees + 1).

Peamised erinevused lineaarse järjekorra ja ümmarguse järjekordade vahel

Lineaarne järjekord on tellitud loend, milles andmeelemendid on järjestatud järjestuses. Seevastu ümmargune järjekord salvestab andmed ringikujuliselt.
Lineaarne järjekord järgib FIFO järjekorda ülesande täitmiseks (esimeses asendis lisatud element kustutatakse esimeses asendis). Vastupidi, ringikujulises järjekorras võib elemendi toimingute järjekord muutuda.
Elementide sisestamine ja kustutamine on fikseeritud lineaarses järjekorras, st lisamine tagumisest otsast ja kustutamine esiosast. Teisest küljest on ringjoont võimalik elementi sisestada ja kustutada mis tahes punktist, kuni see on vaba.
Lineaarne järjekord raiskab mäluruumi, samas kui ümmargune järjekord muudab ruumi tõhusaks kasutamiseks.

Lineaarse järje rakendamine

Allpool toodud algoritm illustreerib elementide lisamist järjekorda:
Järjekorras on kolm andmemuutujat, mis sisaldavad ühte massiivi järjekorra salvestamiseks ja teine, et salvestada esi- ja tagumist algasendit -1.

 sisestada (element, järjekord, n, taga) {if (taga == n) siis printida "järjekordne ülevool"; muu {taga = taga + 1; järjekord [tagumine] = kirje; }}

Allpool toodud algoritm illustreerib elementide kustutamist järjekorras:

 delete_circular (kirje, järjekord, taga, ees) {if (taga == ees) ja seejärel printige "järjekordne allavool"; muu {front = front + 1; kirje = järjekord [ees]; }}

Ümmarguse järjekorda rakendamine

Algoritm elementi lisamise ümmarguses järjekorras tõlgendamiseks:

 insert_circular (kirje, järjekord, taga, ees) {taga = (taga + 1) mod n; kui (ees == taga) siis printida "järjekord on täis"; other {queue [rear] = üksus; }}

Algoritm selgitab elementi kustutamist ümmarguses järjekorras:

 delete_circular (üksus, järjekord, taga, ees) {if (ees == taga) ja seejärel printimine ("järjekord on tühi"); muu {front = front + 1; kirje = järjekord [ees]; }}

Järeldus

Lineaarne järjekord on mõningatel juhtudel ebaefektiivne, kui elemendid on vajalikud sisestusoperatsiooni läbiviimiseks vabade ruumide juurde liikumiseks. See on põhjus, miks ta kipub raiskama ruumi, samas kui ümmargune järjekord kasutab salvestusruumi asjakohaseks kasutamiseks, kuna elemendid lisatakse mis tahes asendisse, kui on tühi ruum.