Verem vs várólista
A Stack egy rendezett lista, amelyben a listaelemek beillesztése és törlése csak az egyik végén, az úgynevezett felső részen végezhető el. Emiatt a verem a Last in First out (LIFO) adatstruktúrának számít. A várólista egy rendezett lista is, amelyben a listaelemek beillesztése az egyik végén, az úgynevezett hátsó részen történik, az elemek törlése pedig a másik végén, az elülső részen. Ez a beillesztési és törlési mechanizmus teszi a várólistát az Első az elsőben (FIFO) adatstruktúrává.
Mi az a Stack?
Mint korábban említettük, a verem egy olyan adatstruktúra, amelyben az elemeket csak az egyik, felsőnek nevezett végből adják hozzá és távolítják el. A veremek csak két alapvető műveletet engednek meg, amit push and popnak hívnak. A tolási művelet új elemet ad a verem tetejéhez. A pop művelet eltávolít egy elemet a verem tetejéről. Ha a verem már megtelt, akkor egy tolási művelet végrehajtásakor azt verem túlcsordulásnak tekintjük. Ha egy pop műveletet egy már üres veremnél hajtanak végre, akkor az verem alulcsordulásnak számít. A veremen végrehajtható műveletek kis száma miatt korlátozott adatszerkezetnek számít. Ezenkívül a push és pop műveletek definiálásának módja alapján egyértelmű, hogy azok az elemek, amelyeket utoljára adtak a veremhez, először mennek ki a veremből. Ezért a verem LIFO adatstruktúrának számít.
Mi a várólista?
A sorban az elemeket hozzáadják a sor hátsó részéhez, és eltávolítják a sor elejéről. Mivel az elsőként hozzáadott elemeket először eltávolítjuk a sorból, fenntartja a FIFO sorrendjét. Az elemek hozzáadásának és eltávolításának ezen sorrendje miatt a sor képviseli a fizetési vonal ötletét. A várólista által támogatott általános műveletek a sorba állítási és a várólistázási műveletek. A sorba állítási művelet hozzáad egy elemet a sor hátuljához, míg a sorkezelés művelet eltávolít egy elemet a sor elejéről. Általánosságban elmondható, hogy a várakozási sorok nem korlátozzák az elemek számát, amelyek a memória korlátai mellett hozzáadhatók a sorhoz.
Mi a különbség a Stack és a Queue között?
Annak ellenére, hogy mind a verem, mind a sorok egyfajta rendezett listák, vannak néhány fontos különbségük. Halmokban az elemek hozzáadása vagy törlése csak az egyik, a felsőnek nevezett végről történhet, míg a sorokban az elemek hozzáadása az egyik, a hátul nevezett végről, az elemek törlése pedig a másik, az elejének nevezett végről történik. Egy veremben azokat az elemeket veszik fel először, amelyek a veremhez utoljára kerültek. Ezért a verem LIFO adatstruktúrának számít. A várólistákban az elsőként hozzáadott elemeket először eltávolítják a sorból. Ezért a várólistát FIFO adatstruktúrának tekintjük.
Kapcsolódó link:
Különbség Stack és Heap között
