Choose your language!

---

|

Stek (Stack) – osnovna struktura podataka

Stek (Stack) je jedna od osnovnih struktura podataka u programiranju koja funkcioniše po principu LIFO (Last In – First Out). Razumevanje steka je ključno za rad sa rekurzijom, grafovima, stablima i mnogim algoritmima koji se koriste u praksi.

U ovoj lekciji naučićemo osnovnu ideju steka, njegove operacije, načine implementacije i tipične zadatke u kojima se stek koristi.

Slika 1: Ilustracija steka (Stack) koja prikazuje LIFO princip, sa osnovnim operacijama push i pop i jasno označenim vrhom steka.

Na slici je prikazana struktura podataka stek (Stack) i njen osnovni princip rada — LIFO (Last In – First Out). Elementi su složeni jedan na drugi, slično kao tanjiri u gomili, gde se uvek pristupa samo elementu koji se nalazi na vrhu.

Desna strana (ili gornji deo) dijagrama označava vrh steka (top). Operacija push dodaje novi element upravo na taj vrh, dok operacija pop uklanja element sa vrha steka. Nije moguće direktno pristupiti elementima koji se nalaze ispod vrha bez prethodnog uklanjanja elemenata iznad njih.

Ovakvo ponašanje čini stek idealnim za probleme kod kojih je potrebno da se poslednja dodata informacija prva obradi, kao što su: rekurzivni pozivi funkcija (call stack), DFS obilazak grafova, undo/redo operacije i proveravanje ispravnosti zagrada.

Dijagram vizuelno pomaže da se razume zašto stek nema proizvoljan pristup elementima, već striktno kontroliše redosled obrade putem LIFO pravila.

1️⃣ Osnovna ideja

Definicija: LIFO — Last In, First Out. Poslednji element koji je ubačen u stek je prvi koji se izvadi.

Svakodnevni primeri:

• Tanjiri u gomili: kada staviš novi tanjir na vrh, njega ćeš prvi skinuti.
• Undo u editorima: poslednja radnja se prva poništava.
• Pregledači — istorija (back): poslednja posećena stranica stoji na vrhu.

Animacija rada steka (Stack)

Stek funkcioniše po principu LIFO (Last In – First Out). Elementi se dodaju i uklanjaju isključivo sa vrha steka.

PUSH POP

DNO STEKA

□ Objašnjenje:
Poslednji element koji ubacimo (PUSH) prvi se uklanja (POP). Zbog toga se stek koristi kod:

• rekurzije
• provere zagrada
• undo/redo operacija
• evaluacije izraza

2️⃣ Osnovne operacije

Stek obično podržava nekoliko jednostavnih operacija:

• push(x) — ubaci element x na vrh steka.
• pop() — ukloni i vrati element sa vrha.
• top() / peek() — pogledaj (ne ukloni) element na vrhu.
• is_empty() — proveri da li je stek prazan.

Napomena o složenosti: sve ove osnovne operacije rade u O(1) vremenu (amortizovano za push kod vektora/growable array).

Greške i ivice:

• Pop na praznom steku — treba detektovati i obraditi (baciti izuzetak, vratiti sentinel vrednost, ili proveriti is_empty pre pop).
• Top na praznom steku — slično, oprezno.

Primeri u C++ (std::stack)

stack s;

// push – dodajemo element na vrh steka
s.push(10);

// top – čitamo element sa vrha (bez uklanjanja)
int x = s.top();

// pop – uklanjamo element sa vrha
s.pop();

U C++ jeziku koristimo std::stack, koji već interno implementira LIFO ponašanje. Sve osnovne operacije rade u O(1) vremenu.

Primeri u Python-u (list kao stek)

stack = []

# push – dodajemo element na kraj liste
stack.append(10)

# top – čitamo poslednji element
top_element = stack[-1]

# pop – uklanjamo poslednji element
stack.pop()

U Python-u se obična lista često koristi kao stek, gde je kraj liste vrh steka. Operacije append i pop su efikasne i rade u O(1) vremenu.

Napomena: Pre poziva pop() ili top(), uvek treba proveriti da li je stek prazan, kako bi se izbegle greške (pristup nepostojećem elementu).

3️⃣ Implementacija (ideja, bez previše koda)

Postoje dve česte implementacije:

3.1 Pomoću niza / vektora

Jednostavno koristimo dinamički niz (npr. std::vector u C++) i tretiramo kraj niza kao vrh steka.

// push: vec.push_back(x)
// pop:  vec.pop_back()
// top:  vec.back()
// is_empty: vec.empty()
  

Prednosti: veoma brzo (O(1) za operacije), jednostavno.

3.2 Pomoću povezane liste

Svaki čvor pokazuje na prethodni (ili sledeći) — vrh steka je glava liste.

// push(x): napravi novi node, node.next = head, head = node
// pop(): if head == null -> error; otherwise head = head.next
  

Prednosti: nema potrebe za reallokacijom memorije; pop/push uvek O(1). Nedostaci: više memorije po elementu zbog pokazivača.

4️⃣ Stek i rekurzija

Call stack (stog poziva) je praktična implementacija steka koju koristi runtime okruženje:

• Svaki poziv funkcije stavlja se na vrh call stack-a (frame sa lokalnim promenljivama i povratnom adresom).
• Kada funkcija završi, njen frame se skida sa vrha (pop).

Zašto DFS „koristi“ stek? Kod rekurzivne DFS implementacije, runtime call stack implicitno čuva trenutni put i tačke povratka. Iterativna DFS implementacija koristi eksplicitni stek da bi simulirala isto ponašanje.

Kratak primer praćenja poziva

Funkcija:

function f(n):
  if n == 0: return
  print(n)
  f(n-1)
  print("return", n)
  

Za poziv f(3), call stack (po koracima) izgleda:

1. pozovemo f(3) — stavimo frame(3) na stek
2. unutar f(3) pozovemo f(2) — stavimo frame(2)
3. zatim f(1), pa f(0)
4. kada f(0) završi — pop, vraćamo se u f(1), itd.

Ovo jasno pokazuje LIFO ponašanje: poslednji pozvani frame je prvi koji se završi.

Rekurzija i stek poziva (Call Stack)

Svaki rekurzivni poziv funkcije se smešta na stek poziva. Kada funkcija završi izvršavanje, njen kontekst se uklanja sa steka.

Primer: računanje faktorijela fact(n)

Pokreni rekurziju (fact(4))

□ Važno:
Rekurzija koristi stek kako bi zapamtila:

• vrednosti parametara
• lokalne promenljive
• mesto povratka u kod

Ako se stek prepuni (previše rekurzivnih poziva), dolazi do stack overflow greške.

□ Ključna razlika:

• Stek (LIFO) — poslednji ubačeni element se prvi uklanja
• Red (FIFO) — prvi ubačeni element se prvi uklanja

Zato se:

• stek koristi za rekurziju, undo/redo, parsiranje izraza
• red koristi za BFS, simulacije čekanja, raspoređivanje procesa

Automatski rad steka kroz primer koda

U ovom primeru prati se izvršavanje jednostavnog koda i automatski se prikazuje stanje steka nakon svake operacije.

1  push(1)
2  push(2)
3  pop()
4  push(3)

Pokreni animaciju

□ Šta ovde vidiš?
Svaka linija koda se izvršava redom. Stek se menja tačno u trenutku kada se pozove push ili pop.

Ovakav način razmišljanja je ključan za razumevanje:

• rekurzije
• DFS algoritma
• undo/redo mehanizama

Interaktivni zadatak: Pogodi ispis

Posmatraj sledeći kod koji koristi stek. Pre nego što klikneš na dugme, pokušaj da predvidiš ispis.

push(10);
push(20);
push(30);
cout << pop() << " ";
push(40);
cout << pop();

Šta će biti ispisano?

Proveri

Kako razmišljati?
Stek radi po principu poslednji ušao – prvi izašao (LIFO). Svaki pop() uklanja i vraća element sa vrha steka.

5️⃣ Tipični zadaci

Stek je ključan u mnogim klasičnim problemima:

• Balansirane zagrade: proveravamo redosled otvaranja i zatvaranja zagrada.
• Pretvaranje infix → postfix (Shunting Yard algoritam): za parsiranje izraza.
• Evaluacija postfix (Reverse Polish) izraza: koristimo stek za rezultat operacija.
• Undo/redo mehanizmi i istorija operacija.
• Backtracking: privremeno čuvamo stanje i vraćamo se (pop) kada ispitamo granu.

Mini vežba: Provera balansiranih zagrada

Zadatak je da proverimo da li su zagrade u datom stringu pravilno balansirane. Koristimo stek da pratimo redosled otvaranja i zatvaranja zagrada.

Pravila:

• Svaka otvorena zagrada mora imati odgovarajuću zatvorenu.
• Zagrade moraju biti zatvorene u pravilnom redosledu.

Primeri ulaza:

• ()[]{} → ispravno
• ([{}]) → ispravno
• ([)] → neispravno
• ((() → neispravno

Pitanje: Kako bismo koristili stek da proverimo da li su zagrade balansirane?

Veza sa drugim lekcijama

Stek će se koristiti i ponovo pojavljivati u sledećim temama:

• DFS obilasku grafova (implicitni call stack ili eksplicitni stek)
• Obilasku stabala (rekurzivni algoritmi)
• Rekurziji i backtracking-u (pr. generisanje permutacija, sudoku solver)

Zaključak: Stek je jednostavna, ali veoma moćna struktura podataka čija se LIFO logika pojavljuje u mnogim algoritamskim obrascima. Razumevanje steka pomaže pri grebanju površine problemâ kao i pri radu sa rekurzijom i grafovima.

Zadaci za vežbu — Stek (Stack)

1. Provera ispravnosti zagrada

Tekst zadatka

Dat je string koji se sastoji od znakova (), {} i []. Potrebno je proveriti da li su zagrade pravilno uparene i u pravilnom redosledu. Ako jesu — ispisati YES, inače NO.

Primer

Ulaz:
{[()]}

Izlaz:
YES

Ulaz:
{[(])}

Izlaz:
NO

Prikaži uputstvo

Uputstvo

• Koristi stek za čuvanje otvorenih zagrada.
• Kada naiđeš na zatvorenu zagradu, proveri vrh steka.
• Ako se tipovi ne poklapaju — izraz nije ispravan.
• Na kraju, stek mora biti prazan.

Prikaži rešenje

Rešenje

#include <iostream>
#include <stack>
using namespace std;

bool odgovara(char o, char z) {
    if(o == '(' && z == ')') return true;
    if(o == '[' && z == ']') return true;
    if(o == '{' && z == '}') return true;
    return false;
}

int main() {
    string s;
    cin >> s;
    stack<char> st;

    for(char c : s) {
        if(c=='(' || c=='[' || c=='{')
            st.push(c);
        else {
            if(st.empty() || !odgovara(st.top(), c)) {
                cout << "NO";
                return 0;
            }
            st.pop();
        }
    }

    cout << (st.empty() ? "YES" : "NO");
    return 0;
}

2. Obrtanje stringa pomoću steka

Tekst zadatka

Dat je string S. Potrebno je ispisati njegovu obrnutu verziju koristeći stek kao pomoćnu strukturu podataka.

Primer

Ulaz:
programiranje

Izlaz:
ejnarimgorp

Prikaži uputstvo

Uputstvo

• Ubaci svaki karakter stringa na stek.
• Zatim skidaj elemente sa steka i ispisuj ih.
• Stek automatski obrće redosled (LIFO).

Prikaži rešenje

Rešenje

#include <iostream>
#include <stack>
using namespace std;

int main() {
    string s;
    cin >> s;
    stack<char> st;

    for(char c : s)
        st.push(c);

    while(!st.empty()) {
        cout << st.top();
        st.pop();
    }
    return 0;
}

3. Sledeći veći element (Next Greater Element)

Tekst zadatka

Dat je niz od n celih brojeva. Za svaki element pronaći prvi veći element desno od njega. Ako ne postoji, ispisati -1.

Primer

Ulaz:
4
4 5 2 10

Izlaz:
5 10 10 -1

Prikaži uputstvo

Uputstvo

• Koristi stek indeksa (ne vrednosti).
• Prolazi niz zleva na desno.
• Dok je trenutni element veći od elementa na vrhu steka, pronađen je sledeći veći element.
• Svaki element ulazi i izlazi iz steka najviše jednom.
• Algoritam radi u O(n) vremenu.

Prikaži rešenje

Rešenje (C++)

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;

    int a[n], res[n];   // a[] - ulazni niz, res[] - rezultat
    stack<int> st;     // stek čuva INDEKSE elemenata

    // Učitavanje niza i inicijalizacija rezultata
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        res[i] = -1;    // podrazumevano: nema većeg elementa
    }

    // Prolazak kroz niz
    for(int i = 0; i < n; i++) {

        // Dok je trenutni element veći od onog
        // na indeksu sa vrha steka
        while(!st.empty() && a[i] > a[st.top()]) {
            res[st.top()] = a[i]; // pronađen sledeći veći element
            st.pop();             // taj indeks je sada rešen
        }

        // Trenutni indeks ide na stek
        st.push(i);
    }

    // Ispis rezultata
    for(int i = 0; i < n; i++)
        cout << res[i] << " ";

    return 0;
}

Objašnjenje algoritma na primeru

Za ulazni niz [4, 5, 2, 10] algoritam radi sledeće:

• Počinje se sa praznim stekom.
• Element 4 se stavlja na stek (nema desno veći element još).
• Element 5 je veći od 4 → sledeći veći element za 4 je 5.
• Element 2 se stavlja na stek jer nije veći od 5.
• Element 10 je veći i od 2 i od 5 → rešava oba elementa redom.
• Poslednji element nema veći desno → ostaje -1.

Konačni rezultat je: 5 10 10 -1

Prednost ovog pristupa je što se svaki element u stek ubacuje i izbacuje najviše jednom, zbog čega algoritam radi u linearnom vremenu.

4. Evaluacija postfix (RPN) izraza

Tekst zadatka

Dat je aritmetički izraz zapisan u postfix (Reverse Polish Notation) notaciji. Potrebno je izračunati njegovu vrednost. Operatori su +, -, * i /.

Primer

Ulaz:
2 3 1 * + 9 -

Izlaz:
-4

Prikaži uputstvo

Uputstvo

• Koristi stek brojeva.
• Brojeve ubacuj direktno na stek.
• Kada naiđeš na operator:
  • skini dva broja sa steka
  • primeni operator
  • rezultat vrati na stek
• Na kraju obrade, na vrhu steka ostaje rezultat.
• Algoritam radi u O(n) vremenu.

Prikaži rešenje

Rešenje (C++)

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> st;   // stek u kome čuvamo brojeve
    string token;   // jedan token izraza (broj ili operator)

    // Čitamo ulaz token po token (razdvojene razmacima)
    while (cin >> token) {

        // Ako je token broj (počinje cifrom)
        if (isdigit(token[0])) {
            // Pretvaramo string u int i guramo na stek
            st.push(stoi(token));
        } 
        // Ako je token operator
        else {
            // Skidamo dva operanda sa steka
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();

            // Primenjujemo operator i rezultat vraćamo na stek
            if (token == "+") st.push(a + b);
            if (token == "-") st.push(a - b);
            if (token == "*") st.push(a * b);
            if (token == "/") st.push(a / b);
        }
    }

    // Na kraju, rezultat je na vrhu steka
    cout << st.top();
    return 0;
}

Objašnjenje algoritma na primeru

Razmotrimo postfix izraz: 2 3 1 * + 9 -

• 2 → broj → stavljamo na stek → [2]
• 3 → broj → stavljamo na stek → [2, 3]
• 1 → broj → stavljamo na stek → [2, 3, 1]
• * → skidamo 1 i 3 → računamo 3 * 1 = 3 → vraćamo na stek → [2, 3]
• + → skidamo 3 i 2 → računamo 2 + 3 = 5 → vraćamo na stek → [5]
• 9 → broj → stavljamo na stek → [5, 9]
• - → skidamo 9 i 5 → računamo 5 - 9 = -4 → vraćamo na stek → [-4]

Na kraju obrade, na steku ostaje samo jedan element: -4, što je rezultat izraza.

Prednost postfix notacije je što nema zagrada i ne zahteva poštovanje prioriteta operatora — redosled računanja je jednoznačan i lako se implementira pomoću steka.

Zadaci za vežbu — Stek u realnim situacijama

U sledećim zadacima stek se koristi za rešavanje problema koji se javljaju u svakodnevnom životu i realnim softverskim sistemima.

5. Undo operacije u tekst editoru

Tekst zadatka

Korisnik unosi operacije u tekst editoru (stringovi). Svaka nova operacija se dodaje na stek. Kada se pojavi komanda UNDO, poslednja operacija se uklanja. Na kraju ispisati koje operacije su ostale.

Primer

Ulaz:
write
delete
copy
UNDO
paste

Izlaz:
write delete paste

Prikaži uputstvo

Uputstvo

• Svaku operaciju (osim UNDO) ubaci na stek.
• Kod UNDO komande ukloni vrh steka.
• Stek prirodno modeluje ponašanje Undo funkcionalnosti.

Prikaži rešenje

Rešenje sa komentarima

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack st;
    string cmd;

    // Čitamo komande dok traje unos
    while(cin >> cmd) {

        // Ako je UNDO — brišemo poslednju operaciju
        if(cmd == "UNDO") {
            if(!st.empty())
                st.pop();   // LIFO: brišemo poslednju dodatu akciju
        } 
        else {
            // Inače, dodajemo novu akciju
            st.push(cmd);
        }
    }

    // Pošto je stek obrnutog redosleda,
    // koristimo pomoćni stek za pravilan ispis
    stack pomocni;

    while(!st.empty()) {
        pomocni.push(st.top());
        st.pop();
    }

    // Ispis preostalih operacija
    while(!pomocni.empty()) {
        cout << pomocni.top() << " ";
        pomocni.pop();
    }

    return 0;
}

□ Napomena:
Undo sistem u realnim aplikacijama često koristi DVA steka: jedan za Undo, drugi za Redo.

6. Kretanje unazad kroz istoriju stranica

Tekst zadatka

Korisnik posećuje web stranice (string). Komanda BACK vraća korisnika na prethodnu stranicu. Ispisati trenutno otvorenu stranicu nakon svake komande.

Primer

Ulaz:
google
youtube
facebook
BACK
BACK
twitter

Izlaz:
google
youtube
facebook
youtube
google
twitter

Prikaži uputstvo

Uputstvo

• Svaka nova stranica ide na stek.
• BACK uklanja trenutnu stranicu.
• Vrh steka predstavlja trenutno otvorenu stranicu.

Prikaži rešenje

Rešenje sa komentarima

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack history;
    string cmd;

    while(cin >> cmd) {

        // Ako korisnik ide unazad
        if(cmd == "BACK") {
            if(!history.empty())
                history.pop();   // uklanjamo trenutnu stranicu
        } 
        else {
            // Nova stranica se dodaje na vrh steka
            history.push(cmd);
        }

        // Ako postoji bar jedna stranica — ona je trenutna
        if(!history.empty())
            cout << history.top() << endl;
    }

    return 0;
}

□ Zašto je stek idealan ovde?
Zato što korisnik uvek želi da se vrati na poslednju posećenu stranicu.

Povezane lekcije:

• DFS i BFS – obilazak grafova (osnove grafova i stabala)
• Rekurzivni algoritmi – uvod i primeri
• Mapa učenja – Grafovi i stabla (pregled oblasti)

---

​Prethodno
​|< Povezane liste

Sledeće
​​Red(Queue) >|

---