LIFO (računarstvo i elektronika)

LIFO (engl. LIFO - last in, first out) je kolekcija koja se temelji na politici "zadnji koji ulazi - prvi izlazi". Stek je LIFO lista. Stek je apstraktni tip podataka (ATP) koji služi za pohranu niza istovrsnih elemenata. Predstavlja vrstu strukture podataka. Specifičan je po ograničenom pristupu svojim elementima. Omogućava upis i ispis po principu "zadnji koji ulazi - prvi izlazi". Uprkos tome, nalazi široku primjenu. LIFO metoda je metoda koja steku dozvoljava upis i čitanje/brisanje samo sa svog "vrha", dok se ostataku eventualnih ranije upisanih elemenata može pristupiti isključivo nakon uklanjanja elemenata kasnije upisanih. Da bi se pristupilo k-tom elementu steka od n elemenata, potrebno je prvo sa steka ukloniti n-k elemenata upisanih nakon k-tog, i to po redu elemente broj: n, n-1, n-2, ... k+2, k-1. Drugim riječima, ranije upisanim elementima pristupa se tek nakon uklanjanja onih kasnije upisanih. Podaci se, dakle, sa steka čitaju u obrnutom redosljedu nego što su bili upisani. Stek se zbog ove osobine često upoređuje s hrpom tanjira. Prvi tanjir kojeg smo stavili na hrpu, nalazi se na dnu, a onaj koji posljednji stavimo nalazit će se na vrhu. Ako uklanjamo tanjire s vrha sve dok ne dođemo do dna hrpe, prvo ćemo uzeti onaj koji smo posljednji stavili, a na kraju onaj koji smo prvi stavili.

Operacije za rad sa stekom

Prikaz push i pop operacija.

Init - služi samo za deklaraciju i inicijalizaciju steka. Pod deklaracijom smatra se stvaranje steka, a pod inicijalizacijom ispravno postavljanje pokazivača ili kursora (ovisno o implementaciji) tako da se njima implicira stanje liste (da je stek trenutno prazan).
Push - operacija kojom se na vrh steka dodaje novi element i u njega zapisuje podatke.
Pop - operacija koja vraća vrijednost elementa sa vrha steka i briše ga.
IsEmpty - ovom se funkcijom provjerava stanje steka, odnosno da li je on prazan.

Funkcije koje se koriste uz LIFO metod

Stack() kreiramo novi stek, prazan
void push(Item item) dodamo novu stavku
Item pop() uklonite nedavno dodane stavke
boolean isEmpty() da li je stek prazan?
int size() broj predmeta u steku

FIFO i LIFO

Razlika između FIFO i LIFO metoda je u tome što FIFO metod, ukoliko ukupno imamo 3 elementa, elemente dodaje redosljedom: 1elemenat, 2elemenat, 3elemenat, a briše elemente redosljedom: 1elemenat, 2elemenat, 3elemenat.
LIFO metod, ukoliko imamo ukupno 3 elementa, te elemente dodaje redosljedom: 1elemenat, 2elemenat, 3elemenat, a briše ih redosljedom: 3elemenat, 2elemenat, 1elemenat.

Također pogledajte

FIFO (first in, first out)
Stek

Reference

N.Husović, E.Brka, S.Ribić - Operativni sistemi, Sarajevo, februar 2015. godine
Stacks and its Applications
Robert Sedgewick and Kevin Wayne - Algorithms, Princeton University