Stog

Jednostavan prikaz stoga

Stog ili složaj je u računarstvu apstraktni tip podataka (ATP) koji služi za pohranu niza istovrsnih elemenata. Vrsta je podatkovne strukture. Specifičan je po ograničenom pristupu svojim elementima, točnije omogućava upis i ispis po principu "zadnji koji ulazi - prvi izlazi" (engl. LIFO - last in, first out). Unatoč tome, nalazi široku primjenu.

Stog dozvoljava upis i čitanje/brisanje samo sa svog "vrha", dok se ostataku eventualnih ranije upisanih elemenata može pristupit isključivo nakon uklanjanja elemenata kasnije upisanih. Da bi se pristupilo k-tom elementu stoga od n elemenata, potrebno je prvo sa stoga maknuti 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. Podatci se dakle sa stoga čitaju u obrnutom redosljedu nego što su bili upisani.

Stog se zbog ovog svojstva često uspoređuje s hrpom tanjura. Prvi tanjur kojeg smo stavili na hrpu, nalazi se na dnu, a onaj koji posljednji stavimo nalaziti će se na vrhu. Ako uklanjamo tanjure 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 stogom

Osnovne operacije

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

Napredne operacije

Osnovne su operacije dovoljne za sve potrebne operacije s listama. Napredne operacije su najčešće samo funkcije sastavljene od više osnovnih operacija za rad sa stogom.

• Top (ili Peek) - funkcija koja čita podatak s vrha stoga, a da ga ne obriše. Moguće ju je implementirati kao ravnopravnu operaciju osnovnima ili kao njihovu nadogradnju kada su osnovne funkcije jedine omogućene. U ovom drugom slučaju, izvodi se kao kombinacija operacija Pop i Push. Zbog praktičnosti, ova se funkcija nerjetko implementira.
• Delete - jednostavna funkcija brisanja cijelog stoga, koja zapravo vrši operaciju Pop nad stogom, sve dok na njemu ima elemenata (što se provjerava funkcijom IsEmpty).
• Invert - kao što joj samo ime kaže, ova funkcija invertira stog. To je jednostavno izvedivo pomoću dodatnog stoga, zbog spomenutog svojstva stoga da vraća elemente u obrnutom redosljedu od onog kojim su bili upisani. Potrebno je samo prepisati elemente iz originalnog u dodatni stog - element s vrha originalnog stoga će tada biti na dnu novog stoga.
• Search - funkcija koja pretražuje stog. Potreban joj je pomoćni stog, na kojega će stavljati pročitane elemente. Po svršetku pretrage, obavezno se podatci s pomoćnog stoga moraju vratiti u izvorni, kako bi se povratio izvoran redoslijed.
• Insert - funkcija koja se slično izvodi funkciji Search, s tom razlikom da umjesto potrage za podatkom na stogu, traži mjesto iza kojeg će upisati novu vrijednost. Kada se s pomoćnog stoga dopunjeni elementi vrate na originalni, umetanje je izvršeno.
• DeleteElement - funkcija slična funkciji Insert, koja umjesto umetanja na određeno mjesto, element određenog mjesta propušta prepisati na pomoćni stog, tako da se on izostavlja i kod vraćanja na originalni.

Moguće je zamisliti i mnoge druge funkcije poput ovih, koje bi dodale dodatnu funkcionalnost stogu - na primjer, kasnije u tekstu očita će postati potreba za funkciju za testiranje ispunjenosti stoga kod implementacije pomoću polja, gdje je važno da se ne upiše više elemenata od dozvoljenih. No, stog se uglavnom koristi kada je osnovna funkcionalnost dovoljna za problem koji se njime želi riješiti.

Implementacije stoga

Implementacija pomoću liste

Stog se često implementira kao jednostruko vezana lista reducirane funkcionalnosti, gdje je pokazivač glave liste zapravo pokazivač na element na vrhu stoga.

Pisanje

Da bi se na vrh stoga upisao novi podatak, potrebno je stvoriti novi element liste u koji će se on upisati, i koji će biti povezan sa (sadržavati pokazivač na) starom glavom liste. Pokazivač na glavu liste se nakon toga prusmjerava tako da pokazuje na novoupisani element, koji time postaje i novi vrh stoga.

Čitanje

Čitanje sa stoga je sasvim jednostavno. Potrebno je samo vratiti podatak zapisan u trenutnoj glavi stoga. No, da bi se element s vrha stoga i obrisao, potrebno je: preusmjeriti pokazivač na glavu liste na sljedeći element vezane liste i nakon toga obrisati staru glavu liste, to jest stari vrh stoga. Sljedeći element liste tako postaje glava liste, a time i vrh stoga.

Stanje stoga

Stog je prazan ako je glava liste jedini preostali element, dakle ako pokazivač glave liste to jest poveznica glave (razlikovati od pokazivača na glavu) ne pokazuje ni na jedan drugi element. Da bi ovo bilo moguće, zadnji se element liste ne koristi za zapis podataka.

Implementacija pomoću polja

Ako pohranjujemo podatke koji ne zauzimaju mnogo mjesta u memoriji ili ako smo voljni žrtvovati memorijski prostor, i unaprijed znamo koliko će maksimalno elemenata sadržavati lista stog se može implementirati i kao niz. Kod implementacije liste pomoću polja, ključna je jedinstvena varijabla kursor, koja služi kao indikator popunjenosti stoga. Točnije, to je indeks polja koji pokazuje na prvi slobodan element polja.

Pisanje

Novi podatak zapisuje se upravo u prvi slobodan element polja, dakle na ono mjesto na koje pokazuje varijabla kursor. Sam se kursor tada inkrementira, tako da sada pokazuje na prvo sljedeće mjesto u polju, koje je tada zapravo prvo slobodno.

Čitanje

Čitanje se obavlja vraćanjem vrijednosti sa zadnjeg iskorištenog mjesta u polju. Pošto kursor, kao što je rečeno, pokazuje na prvo prazno mjesto, zadnje iskorišteno je ono tik prije polja na koje pokazuje kursor. Dakle kako bi se pročitala vrijednost s vrha stoga, vraća se vrijednost polja s mjesta (kursor-1). Kursor se nakon toga dekrementira kako bi označio da je polje s kojeg je vraćena vrijednost sada "prazno".

Stanje stoga

Pošto je kursor indeks prvog praznog mjesta, lako je zaključiti da ako je kursor = 0 tj. ako je prvo prazno mjesto i prvi (zapravo nulti) element polja, onda takvo polje ne sadrži nikakve vrijednosti. U slučaju da je kursor jednak 0, dakle, možemo reći da je stog prazan. Kod implementacije stoga pomoću polja, javlja se i maksimalna veličina stoga. Stog je ispunjen ako kursor poprima vrijednost jednaku veličini polja (jer je onda to zapravo imaginarni element izvan opsega stvarnog polja). Uglavnom se ne stvara posebna funkcija za ispitivanje ovog svojstva implementacije pomoću polja, već se pretpostavlja da program koji koristi implementaciju neće nikada pokušati zapisati više elemenata na stog nego što je moguće. Dakle program ne smije pokušati pisati u element s indeksom jednakim vrijednosti kursora stoga koji je pun.

Usporedba implementacija

Implementacija pomoću polja nije samo jednostavnija i brža zbog činjenice da kod upisa i ispisa ne trebamo preusmjeravati poveznice (pokazivače) koji bi povezivali elemente stoga, nego upravo zbog toga što tih pokazivača nema može biti i ekonomičnija. To je tako ipak samo u slučaju da se radi o stogu kojemu je određen maksimalni broj elemenata, čiji elementi zauzimaju malo prostora u memoriji(tako da je veličina pokazivača značajna) i koji je najveći dio vremena relativno pun. No takav slučaj je vrlo rjedak, tako da je u većini slučajeva isplativija implementacija liste, a ponekad i jedina moguća osim ako implementaciju pomoću polja nismo voljni nadograditi za rad s dinamički alociranim poljima u slučaju prekoračenja maksimalne vrijednosti. No tada već govorimo o stanovitom hibridu implementacija jer onda koristimo zapravo vezanu listu polja koja je kompleksnija od jednostavnih implementacija, a time i njena isplativost u pogledu brzine postaje upitna.

Primjene stoga

Računanje

Stog je vrlo koristan u izradi kalkulatora, gdje služi kod pretvaranja infiks matematičkog zapisa u postfiks matematički zapis (obrnutu poljsku notaciju), koji se nakon pretvorbe vrlo lako evaluira (izračunava) također koristeći stog. U pretvorbi se koristi za privremenu pohranu operatora visokog prioriteta koji se tek nakon dodavanja operatora nižeg prioriteta dodaju u postfiks zapis. Kod evaluacije se može koristiti za pohranu operanada, odnosno u slučaju varijabli, njihovih vrijednosti. Da bi se izraz evaluirao, potrebno je sljedno primjeniti operatore iz pravilnog postfiksnog zapisa na dva po dva(pošto se radi o binarnim operacijama) operanda sa stoga. Rezultat operacija se vraća na stog, i kada su iscrpljeni svi operandi i operatori iz izraza, na stogu ostaje rezultat evaluacije izraza, tj. rješenje.

Programi

Programi u svom izvršnom obliku mogu sadržavati skokove na potprograme (engl. subroutine) odnosno dijelove koda nakon čijeg izvršavanja se vraća u glavni program. Ti se skokovi čine tako da se na tzv. stog za pozive (engl. call stack) neposredno prije izvršavanja skoka stavlja (push) adresa sljedeće instrukcije tj. sadržaj brojača instrukcija (engl. instruction pointer/program counter) uvećan za 1. Nakon izvršenja pozvanog potprograma, sa stoga se uklanja (pop) zadnja pohranjena adresa i na nju se skače. Tako se program nastavlja izvršavati tik nakon mjesta na kojem se nalazio poziv potprograma. Procesori CISC arhitekture za svaku od navedenih operacija (push i pop) obično rabe samo jednu instrukciju.

Operacijski sustavi

Uz gore navedeni stog koji je dostupan na korisničkom nivou (engl. user mode - u kojem se izvršavaju korisnički programi), postoji i sistemski stog (dostupan samo u supervisor načinu rada (hrvatski: nadgledničkom, nadzorničkom) - u kojem se izvršava kernel) koji omogućava obradu prekida. Operacijski sustav, naime, mora reagirati na prekide (engl. interrupts) koje izaziva sklopovlje kada želi - na primjer - prenijeti podatke (vidi sklopovski prekid). Da bi operacijski sustav skočivši na određenu rutinu mogao obraditi zaprimljeni zahtjev za prekidom (engl. interrupt request - IRQ), potrebno je prethodno privremeno prekinuti izvršavanje trenutnog procesa. Kako bi se to učinilo sigurno, (nakon izvršavanja trenutne instrukcije) na sistemski je stog uz programsko brojilo potrebno pohraniti i minimalni kontekst - stanja ostalih registara procesora. Na taj se način osigurava da operacijski sustav, nakon što obradi rečeni zahtjev, omogući nastavak izvršavanja prekinutog procesa tako što će učitati stanja pohranjenih registara sa sistemskog stoga.

Vanjske poveznice

• Interpretacija programa Sintaksni analizator Podatkovna struktura
• Lekcija 16 Apstraktni tipovi - ADT
• Stack program in c++
• Stack Machines - the new wave
• Bounding stack depth
• Libsafe - Protecting Critical Elements of Stacks
• Stack Size Analysis for Interrupt-driven Programs (322 KB)
• Stack Implementation ( Graphical & Text Mode) C Language implementation of Stack
• Pointers to stack visualizations
• CollectionSpy — A profiler for Java's Collection Framework; contains java.util.Stack specific features.