A LIFO ( eng. last in, first out , "last in, first out") az időre és a prioritásokra vonatkozó adatok rendszerezésének és kezelésének módja. A strukturált, lineáris, LIFO által szervezett listában az elemek csak az egyik végéhez adhatók hozzá vagy távolíthatók el, ezt a "lista tetejének" nevezik. [1] A LIFO felépítése egy tányérköteg példájával szemléltethető: ahhoz, hogy felülről vegye a másodikat, el kell távolítania a felsőt, az utolsó eltávolításához pedig el kell távolítani az összes fent fekvőt. .
A kifejezés a listafeldolgozás és az adatok ideiglenes tárolásának elvont alapelveit jelenti, különösen akkor, ha egy bizonyos sorrendben korlátozott adathalmazhoz kell hozzáférni. A LIFO-elv akkor érvényes, ha a szerkezethez utoljára hozzáadott adatot kell először eltávolítani vagy feldolgozni. Hasznos hasonlat egy irodai dolgozóhoz: az ember egyszerre csak egy oldalon dolgozhat, így a következő dokumentum az előzőek kötegének tetejére kerül a mappába. Hasonlóképpen a számítógépnek is vannak korlátai, például az adatbusz szélessége és az a tény, hogy a rendszer egyszerre csak egy memóriahelyet tud kezelni. [2] A számításokban használt absztrakt LIFO-mechanizmust valós adatstruktúrákban valósítják meg halom formájában , melynek neve nyilvánvalóan „egy köteg papírra”, „ egy köteg tányérra” stb. utal. bála, köteg ). A FILO kifejezést néha szinonimaként használják ( angolul first in, last out - „first in, last out”), ami azt hangsúlyozza, hogy a lista korábbi kiegészítéseinek meg kell várniuk, amíg fel nem kerülnek a szerkezet legtetejére, majd ezután elérhető lesz. A sorbanállási elméletben néha használják az LCFS (utolsó érkezés, elsőként kiszolgálás) kifejezést. Az általános lista, a tömb, a sor és a verem közötti különbséget az adatelérési mechanizmusban használt szabályok határozzák meg. [2] Mindenesetre a hozzáférés a LIFO struktúrában a sorhoz képest fordított sorrendben történik . „Vannak bizonyos, gyakori helyzetek az informatikában, amikor a beszúrást és törlést listákra akarjuk korlátozni, hogy ezek a változások csak a lista elején vagy végén történhessenek, de a közepén ne. Két adatstruktúra hasznos ilyen esetekben: veremek (üzletek) és sorok . [3]
A LIFO szinonimájaként a "magazin-princípium" kifejezést is használják, ami a fegyvertárral és a töltényekkel hasonlít. [négy]
A veremstruktúrák a számítástechnikai rendszerekben az alapvető és ezért rendkívül fontosak közé tartoznak. Elmondható, hogy az adatok konfigurálható rendszerezésének képessége nélkül, beleértve a futtatható kódra való hivatkozást is , a számítógépek nem lennének olyan rugalmas eszközök, mint manapság, hanem egyszerűen drága számológépek lennének speciális célokra, mint például a második ENIAC . világháború . korlátozott képességekkel és szűk hatókörrel. [5]
A rendezett adatstruktúrákban a verem dinamikus memóriaelemként szolgál, amelyben egy absztrakt fogalom - egy hardverfüggő hívásverem - az adatok vagy azok egy részének másolatának tárolására szolgál, legyen az adatelemek memóriacíme. (lásd: Paraméter (programozás)#Paraméter átadása hivatkozással ) vagy az adatok másolata (paraméter átadása érték szerint). A legáltalánosabb listafeldolgozási feladat a rendezés ( lexikográfiai sorrendben , növekvő értékben stb.), amelyben a gép műveletei csupán két elem összehasonlítására korlátozódnak, míg a lista legtöbbször több millió tagot tartalmaz. Különféle stratégiák (számítógépes algoritmusok ) léteznek, amelyek optimálisak a különféle típusú adatok rendezéséhez, de megvalósításukkor mindegyik olyan programok vagy szubrutinok használatához folyamodik, amelyek általában rekurzívan hívják magukat vagy a kódjuk egy részét , és minden egyes hívással. részlegesen rendezett elemlistát adnak a hívási veremhez. Ez az oka annak, hogy a veremeket és a rekurziókat általában párhuzamosan vezetik be az adatszerkezeti kurzusokban, mivel ezek szorosan összefüggenek. [6]
A hívásveremhez való rugalmas hozzáférésnek köszönhetően az adatok átcsoportosításának lehetőségével (az absztrakt LIFO-módszer szerint szervezett adatblokkot úgy tűnik, kifejezetten csak azért találták ki, hogy az adatok könnyen átrendezhetők legyenek) szubrutinok és szabványos funkciók fogadása. a szükséges adatokat, végrehajtja azokat a feladatokat, amelyekre optimalizálva vannak, és visszaadja az információkat a program hívó szegmensének. [7] A hívási verem bizonyos esetekben tartalmazza a hívó program következő utasításának címét, amely általában valamilyen műveletet hajt végre a szubrutinoktól és szabványos függvényektől kapott "válaszokon". Rekurzív hívásoknál ezek a műveletek jellemzően a lista következő elemének összehasonlítását jelentik a visszaadott „válasz”-val (például két legnagyobb értékű érték közötti választással), amíg a lista ki nem merül.
Ezért az absztrakt LIFO elv implementációinak valós világában a hívási veremek száma rendkívül gyakran változik, mindegyik mérete a manipulálandó adatelemek számától függ. Ezért célszerű a LIFO-t egy halom füzethez és füzethez hasonlítani, nem pedig egy köteg vékony papírlaphoz.