Sklad proti čakalni vrsti
Sklad je urejen seznam, v katerega je mogoče vstavljanje in brisanje elementov seznama izvesti samo na enem koncu, imenovanem vrh. Zaradi tega razloga se sklad šteje za podatkovno strukturo Zadnji v prvem ven (LIFO). Čakalna vrsta je tudi urejen seznam, v katerem se vstavljanje elementov seznama izvede na enem koncu, imenovanem zadaj, in brisanje elementov na drugem koncu, imenovanem spredaj. Ta mehanizem vstavljanja in brisanja omogoča, da je čakalna vrsta podatkovna struktura prvi v prvi ven (FIFO).
Kaj je Stack?
Kot smo že omenili, je sklad podatkovna struktura, v kateri se elementi dodajajo in odstranjujejo samo z enega konca, imenovanega vrh. Skladi dovoljujejo samo dve osnovni operaciji, imenovani push in pop. Operacija potiskanja doda nov element na vrh sklada. Operacija pop odstrani element z vrha sklada. Če je sklad že poln, ko se izvede operacija potiskanja, se to obravnava kot prelivanje sklada. Če se operacija izpiranja izvede na že praznem skladu, se to šteje za pretok sklada. Zaradi majhnega števila operacij, ki jih je mogoče izvesti na skladu, velja za omejeno podatkovno strukturo. Poleg tega je glede na način, kako sta definirani operaciji potiskanja in izpiranja, jasno, da elementi, ki so bili zadnji dodani v sklad, gredo iz sklada prvi. Zato se sklad obravnava kot podatkovna struktura LIFO.
Kaj je čakalna vrsta?
V čakalni vrsti se elementi dodajajo z zadnjega dela čakalne vrste in odstranjujejo z začetka čakalne vrste. Ker bodo elementi, ki so prvi dodani, najprej odstranjeni iz čakalne vrste, ohranja vrstni red FIFO. Zaradi takšnega vrstnega reda dodajanja in odvzemanja elementov čakalna vrsta predstavlja idejo blagajne. Splošne operacije, ki jih podpira čakalna vrsta, so operacije v čakalni vrsti in de-queue. Operacija v čakalni vrsti bo dodala element na zadnji del čakalne vrste, medtem ko operacija odstranitve iz čakalne vrste odstrani element s sprednje strani čakalne vrste. Na splošno čakalne vrste nimajo omejitve glede števila elementov, ki jih je mogoče dodati v čakalno vrsto, razen omejitev pomnilnika.
Kakšna je razlika med skladom in čakalno vrsto?
Čeprav so tako skladi kot čakalne vrste vrsta urejenih seznamov, imajo nekatere pomembne razlike. V skladih lahko dodajanje ali brisanje elementov izvedete samo z enega konca, imenovanega vrh, medtem ko se v čakalnih vrstah dodajanje elementov izvede z enega konca, imenovanega zadnji, brisanje elementov pa z drugega konca, imenovanega sprednji. V skladu bodo elementi, ki so zadnji dodani v sklad, najprej odstranjeni iz sklada. Zato se sklad obravnava kot podatkovna struktura LIFO. V čakalnih vrstah bodo elementi, ki so prvi dodani, najprej odstranjeni iz čakalne vrste. Zato se čakalna vrsta obravnava kot podatkovna struktura FIFO.
Sorodna povezava:
Razlika med skladom in kopico
