Stek

Stek 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. Omogućava upis i ispis po principu "zadnji koji ulazi - prvi izlazi" (engl. LIFO - last in, first out). Uprkos tome, nalazi široku primjenu.

Stek 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

Osnovne operacije

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.

Napredne operacije

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

Top (ili Peek) - funkcija koja čita podatak s vrha steka, 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 funkcija se često implementira.
Delete - jednostavna funkcija brisanja cijelog steka, koja zapravo vrši operaciju Pop nad stekom, sve dok na njemu ima elemenata (što se provjerava funkcijom IsEmpty).
Invert - kao što joj samo ime kaže, ova funkcija invertira stek. To je jednostavno izvedivo pomoću dodatnog steka, zbog spomenutog svojstva steka da vraća elemente u obrnutom redosljedu od onog kojim su bili upisani. Potrebno je samo prepisati elemente iz originalnog u dodatni stek - element s vrha originalnog steka će tada biti na dnu novog steka.
Search - funkcija koja pretražuje stek. Potreban joj je pomoćni stek, na kojega će stavljati pročitane elemente. Po završetku pretrage, obavezno se podaci s pomoćnog steka moraju vratiti u izvorni, kako bi se povratio prvobitni redoslijed.
Insert - funkcija koja se slično izvodi funkciji Search, s tom razlikom da umjesto potrage za podatkom na steku, traži mjesto iza kojeg će upisati novu vrijednost. Kada se s pomoćnog steka 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 ne prepisuje na pomoćni stek, 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 steku - na primjer, kasnije u tekstu očita će postati potreba za funkcijom za testiranje ispunjenosti steka kod implementacije pomoću polja, gdje je važno da se ne upiše više elemenata od dozvoljenih. No, stek se uglavnom koristi kada je osnovna funkcionalnost dovoljna za problem koji se njime želi riješiti.

Implementacije steka

Implementacija pomoću liste

Stek se često implementira kao jednostruko povezana lista reducirane funkcionalnosti, gdje je pokazivač početka liste zapravo pokazivač na element na vrhu steka.

Umetanje

Da bi se na vrh steka umetnuo neki novi podatak, potrebno je stvoriti novi element liste u koji će se on upisati, i koji će biti povezan sa (sadržavati pokazivač na) starim početkom liste. Pokazivač na početak liste se nakon toga prusmjerava tako da sada pokazuje na novoupisani element, koji time postaje i novi početak steka.

Čitanje

Čitanje sa steka je sasvim jednostavno. Potrebno je samo vratiti podatak zapisan u trenutnom početku steka. No, da bi se element s vrha steka i obrisao, potrebno je: preusmjeriti pokazivač na početak liste na sljedeći elemenat povezane liste i nakon toga obrisati stari početak liste, to jest stari vrh steka. Sljedeći elemenat liste tako postaje početak liste, a time i vrh steka.

Stanje steka

Stek je prazan ako je početak liste jedini preostali elemenat, dakle ako pokazivač početka liste (razlikovati od pokazivača na početak) ne pokazuje ni na jedan drugi elemenat. Da bi ovo bilo moguće, zadnji se elemenat liste ne koristi za zapis podataka.

Implementacija pomoću niza

Ako pohranjujemo podatke koji ne zauzimaju mnogo mjesta u memoriji ili ako nam nije bitno koliko memorije zauzimamo, i unaprijed znamo koliko će maksimalno elemenata sadržavati lista stek se može implementirati i kao niz. Kod implementacije liste pomoću niza, ključna je jedinstvena varijabla kursor, koja služi kao indikator popunjenosti steka. Točnije, to je indeks niza koji pokazuje na prvi slobodan element niza.

Umetanje

Novi podatak umeće se u prvi slobodan elemenat niza, dakle na ono mjesto na koje pokazuje varijabla kursor. Sam se kursor tada inkrementira, tako da sada pokazuje na prvo sljedeće mjesto u nizu, koje je tada zapravo prvo slobodno.

Čitanje

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

Stanje steka

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) elemenat niza, onda takvo mjesto u nizu ne sadrži nikakve vrijednosti. U slučaju da je kursor jednak 0, dakle, možemo reći da je stek prazan. Kod implementacije steka pomoću niza, javlja se i maksimalna veličina steka. Stek je ispunjen ako kursor poprima vrijednost jednaku veličini niza (jer je onda to zapravo imaginarni element izvan opsega stvarnog niza). Uglavnom se ne stvara posebna funkcija za ispitivanje ovog svojstva implementacije pomoću niza, već se pretpostavlja da program koji koristi implementaciju neće nikada pokušati zapisati više elemenata na stek nego što je moguće. Dakle, program ne smije pokušati pisati u element s indeksom jednakim vrijednosti kursora steka koji je pun.

Uporedba implementacija

Implementacija pomoću niza nije samo jednostavnija i brža zbog činjenice da kod upisa i ispisa ne trebamo preusmjeravati pokazivače koji bi povezivali elemente steka, 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 steku 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.

Sekvencijalna implementacija više stekova

Često se javlja potreba za korištenjem više stekova istodobno. U tim situacijama često se desi da dođe do prekoračenja jednog steka dok su drugi skoro prazni. Dakle, nepraktično je implementirati svaki stek u zasebnom memorijskom bloku očekivanog kapaciteta. Bolji način da iskoristimo memoriju jeste da smjestimo više stekova u jedan zajednički blok memorije (vektor). Prostor u ovome bloku preraspodjelimo ovisno o potrebamo svakog steka.

Npr. kod postojanja dva steka imamo jedan kontinualni zajednički memorijski prostor u vektoru. Dno prvog steka veže se za adresu ispred početka vektora, a dno drugog steka za prvu adresu poslije kraja vektora. Prvi stek raste prema gore, a drugi prema dole. Prekoračenje će se javiti kad je ukupna veličina oba steka jednaka veličini alociranog prostora, a vrhovi stekova se tada nalaze na susjednim lokacijama.

Implementacija više od dva steka u zajedničkom memorijskom bloku dosta je složenija. U tom slučaju mi ne možemo kao u slučaju dva steka vezati dna svih stekova za neke fiksne pozicije i onda dinamički preraspodjeljivati prostor i obezbjediti da se prekoračenje dešava kad ukupna veličina svih stekova bude jednaka veličini alociranog zajedničkog prostora. Da bi se ovaj kriterij prekoračenja zadržao potrebno je povremeno pomjerati stekova i time održavati svojstvo sekvencijalne alokacije. Na ovaj način mi odlažemo prekoračenje.

Primjene steka

Računanje

Stek je vrlo koristan u izradi kalkulatora, gdje se koristi kod pretvaranja infiks matematičkog zapisa u postfiks matematički zapis (obrnutu poljsku notaciju), koji se nakon pretvorbe vrlo lahko izračunava također koristeći stek. 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 primjeniti operatore iz pravilnog postfiksnog zapisa na dva po dva(pošto se radi o binarnim operacijama) operanda sa steka. Rezultat operacija se vraća na stek, i kada su iscrpljeni svi operandi i operatori iz izraza, na steku 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. stek 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 steka se uklanja (pop) zadnja pohranjena adresa i na nju se skače. Tako se program nastavlja izvršavati 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.

Operativni sistemi

Uz gore navedeni stek koji je dostupan na korisničkom nivou (engl. user mode - u kojem se izvršavaju korisnički programi), postoji i sistemski stek (dostupan samo u supervisor načinu rada- u kojem se izvršava kernel) koji omogućuje obradu prekida. Operativni sistem mora reagovati na prekide (engl. interrupts) koje izaziva hardver kada želi - na primjer - prenijeti podatke. Da bi operativni sistem skočivši na određenu rutinu mogao obraditi primljeni 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 stek uz programski brojač potrebno pohraniti i minimalni kontekst - stanja ostalih registara procesora. Na taj se način osigurava da operativni sistem, nakon što obradi rečeni zahtjev, omogući nastavak izvršavanja prekinutog procesa tako što će učitati stanja pohranjenih registara sa sistemskog steka.

Reference

Tomašević, Milo (2004). Algoritmi i strukture podataka. Beograd: Akademska misao. str. 406. ISBN 978-86-7466-328-8.

Vanjski linkovi

Interpretacija programa Sintaksni analizator Podatkovna struktura^{[mrtav link]}
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.