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.

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.

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.

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.

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)

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)

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?

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.

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

#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

#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

#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;
}

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

#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;
}

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

#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;
}

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

#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;
}

Povezane lekcije:

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