Čakalno vrsto lahko opišemo kot ne-primitivno strukturo linearnih podatkov, ki sledi vrstnemu redu FIFO, v katerem se podatkovni elementi vstavijo z enega konca (zadnji konec) in izbrišejo iz drugega konca (sprednji konec). Druge različice čakalne vrste so krožna čakalna vrsta, dvojno končana čakalna vrsta in prioritetna čakalna vrsta.
Primerjalna tabela
| Podlaga za primerjavo | Linearna čakalna vrsta | Krožna čakalna vrsta |
|---|---|---|
| Osnovno | Organizira podatkovne elemente in navodila v zaporednem vrstnem redu. | Podatke ureja v krožnem vzorcu, kjer je zadnji element povezan s prvim elementom. |
| Vrstni red izvedbe naloge | Naloge se izvajajo v vrstnem redu, v katerem so bile postavljene (FIFO). | Vrstni red izvajanja naloge se lahko spremeni. |
| Vstavljanje in brisanje | Novi element se doda iz zadnjega dela in se odstrani s sprednje strani. | Vstavljanje in brisanje se lahko opravi na katerem koli mestu. |
| Izvedba | Neučinkovit | Deluje bolje kot linearna čakalna vrsta. |
Opredelitev linearne čakalne vrste
Linearna čakalna vrsta je racionalno prva na prvem seznamu. To je tako imenovano linearno, ker spominja na ravno črto, kjer so elementi postavljeni eden za drugim. Vsebuje homogeno zbirko elementov, v katere se dodajo novi elementi na enem koncu in izbrišejo iz drugega konca. Koncept čakalne vrste je mogoče razumeti na primeru čakalne vrste gledalcev, ki čakajo zunaj števca vstopnic, da bi dobili gledališko vstopnico. V tej čakalni vrsti se oseba pridruži zadnjemu delu čakalne vrste, da vzame vozovnico, in vstopnica se izda na sprednjem koncu čakalne vrste.
V čakalni vrsti je izvedenih več operacij
- Najprej je čakalna vrsta inicializirana na nič (tj. Prazna).
- Ugotovite, ali je čakalna vrsta prazna ali ne.
- Ugotovite, ali je čakalna vrsta polna ali ne.
- Vstavljanje novega elementa iz zadnjega konca (Enqueue).
- Izbris elementa iz sprednjega dela (Dequeue).
Čakalno vrsto lahko izvedemo na dva načina
- Statično (z uporabo nizov)
- Dinamično (z uporabo kazalcev)
Omejitev linearne čakalne vrste je, da ustvari scenarij, v katerem ni mogoče dodati novega elementa v čakalno vrsto, tudi če čakalna vrsta vsebuje prazne prostore. Ta zgornja situacija je prikazana na spodnji sliki. Tu zadaj kaže na zadnji indeks, medtem ko so vsa polja prazna, ni mogoče dodati nobenega novega elementa.
Opredelitev krožne vrste
Krožna čakalna vrsta je varianta linearne čakalne vrste, ki učinkovito presega omejitev linearne čakalne vrste. V krožni čakalni vrsti se novi element doda na prvo mesto čakalne vrste, če je zadnja zasedena in je na voljo prostor. Ko gre za linearno čakalno vrsto, se vstavljanje lahko izvede samo iz zadnjega konca in brisanja iz sprednjega dela. V celotni čakalni vrsti se po vrsti zaporednih izbrisov v čakalni vrsti pojavi določena situacija, ko ni mogoče dodati nobenega novega elementa, tudi če je prostor, ki je na voljo, ker stanje podtoka (Rear = max - 1) še vedno obstaja.
Krožna čakalna vrsta povezuje oba konca skozi kazalec, kjer prvi element pride za zadnjim elementom. Prav tako sledi spredaj in zadaj z izvajanjem nekaj dodatne logike, tako da lahko sledi elementom, ki jih je treba vstaviti in izbrisati. S tem krožna čakalna vrsta ne ustvari pogoja prelivanja, dokler se čakalna vrsta ne polni v dejanskem stanju.
Nekateri pogoji, ki jim sledi krožno čakalno vrsto:
- Spredaj mora kazati na prvi element.
- Čakalna vrsta bo prazna, če je Front = Rear.
- Ko je dodan nov element, se čakalna vrsta poveča z vrednostjo ena (Rear = Rear + 1).
- Ko se element izbriše iz čakalne vrste, se spredaj poveča za eno (Front = Front + 1).
Ključne razlike med linearno čakalno vrsto in krožno čakalno vrsto
- Linearna čakalna vrsta je urejen seznam, v katerem so podatkovni elementi organizirani v zaporednem vrstnem redu. Nasprotno pa krožna čakalna vrsta shranjuje podatke na krožni način.
- Linearna čakalna vrsta sledi zaporedju FIFO za izvedbo naloge (element, dodan v prvo mesto, bo izbrisan v prvem položaju). Nasprotno pa se lahko v krožni vrsti spremeni vrstni red operacij, ki se izvajajo na elementu.
- Vstavljanje in brisanje elementov je fiksirano v linearni čakalni vrsti, tj. Dodatek iz zadnjega dela in brisanje iz sprednjega dela. Po drugi strani pa je krožna čakalna vrsta sposobna vstaviti in izbrisati element iz katere koli točke, dokler ni prazen.
- Linearna čakalna vrsta zapravlja pomnilniški prostor, medtem ko krožna čakalna vrsta omogoča učinkovito uporabo prostora.
Izvedba linearne čakalne vrste
Spodnji algoritem prikazuje dodajanje elementov v čakalno vrsto:
Čakalna vrsta potrebuje tri podatkovne spremenljivke, vključno z enim nizom za shranjevanje čakalne vrste in drugim za shranjevanje sprednjega in zadnjega začetnega položaja, ki je -1.
insert (element, čakalna vrsta, n, zadaj) {if (zadaj == n) in nato natisnite "overflow overflow"; drugo {zadaj = zadaj + 1; čakalna vrsta [zadaj] = postavka; }} Spodnji algoritem prikazuje izbris elementov v čakalni vrsti:
delete_circular (postavka, čakalna vrsta, zadaj, spredaj) {if (zadaj == spredaj) in natisnite "underflow" čakalne vrste; else {front = front + 1; item = čakalna vrsta [spredaj]; }} Izvajanje krožne čakalne vrste
Algoritem za interpretacijo dodatka elementa v krožni čakalni vrsti:
insert_circular (postavka, čakalna vrsta, zadaj, spredaj) {zadaj = (zadaj + 1) mod n; če (spredaj == zadaj), potem natisnite "čakalna vrsta je polna"; else {vrsta [zadnja] = postavka; }} Algoritem pojasnjuje izbris elementa v krožni čakalni vrsti:
delete_circular (postavka, čakalna vrsta, zadaj, spredaj) {if (spredaj == zadaj) in nato natisni ("čakalna vrsta je prazna"); else {front = front + 1; item = čakalna vrsta [spredaj]; }} Zaključek
Linearna čakalna vrsta je v nekaterih primerih neučinkovita, kadar so elementi potrebni za premik v prazne prostore za izvedbo vstavitve. To je razlog, zakaj zapravlja prostor za shranjevanje, medtem ko krožna čakalna vrsta ustrezno uporablja prostor za shranjevanje, saj se elementi dodajo na katerem koli mestu, če obstaja prazen prostor.
