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.

LIFO metod

Operacije za rad sa stekom

uredi
 
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

uredi
  • 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

uredi


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

uredi

Reference

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