Konsep Stack

Stack adalah struktur data linier dengan aturan akses LIFO (Last In First Out) — elemen terakhir yang dimasukkan adalah yang pertama keluar. Bayangkan tumpukan piring: kita menambah di atas, mengambil dari atas, dan tidak bisa menyentuh piring di tengah tanpa menggeser yang di atasnya. Aturan ini terdengar sederhana, tetapi justru kesederhanaannya membuat stack cocok untuk banyak skenario: undo pada editor, evaluasi ekspresi aritmetika, pengecekan tanda kurung seimbang, hingga call stack bahasa pemrograman. Pada Chapter ini kita akan memahami operasi dasar stack (push, pop, peek), use case umum, dan membangun mini-implementation dengan std::vector.

Mengapa LIFO Berguna #

LIFO cocok untuk masalah yang memerlukan reversal otomatis urutan operasi:

Undo/Redo — aksi terakhir yang dilakukan harus dibatalkan pertama.
Call stack — fungsi terakhir yang dipanggil harus kembali pertama.
Backtracking — cabang eksplorasi terakhir harus ditinggalkan pertama bila buntu.
Evaluasi ekspresi — operator terakhir ditemui (tertumpuk) dievaluasi lebih dulu saat operand tersedia.
Balanced parentheses — tanda kurung penutup terakhir harus memasangkan dengan tanda kurung pembuka terakhir.

Tanpa LIFO, kita harus menyimpan urutan dan membalik secara manual — stack melakukan ini secara natural.

Anatomi Stack dan Operasi Dasar #

Stack memiliki tiga operasi inti dengan kompleksitas O(1):

Operasi	Aksi	Kompleksitas
`push(v)`	Tambah `v` ke atas	O(1)
`pop()`	Hapus dan kembalikan elemen atas	O(1)
`peek()` / `top()`	Lihat elemen atas tanpa hapus	O(1)
`empty()`	Apakah stack kosong	O(1)
`size()`	Jumlah elemen	O(1)

flowchart TD subgraph Stack T3["30 (top)"] T2["20"] T1["10 (bottom)"] end Push["push(30)"] --> T3 T3 -->|"pop() → 30"| Out["return 30"]

Akses hanya dari satu sisi (top). Tidak ada akses indeks ke-i seperti array — itulah batasan yang membuat stack efisien untuk use case tertentu.

Use Case 1: Balanced Parentheses #

Aturan #

Diberikan string berisi kurung ()[]{}, tentukan apakah setiap kurung pembuka punya pasangan penutup dengan urutan yang benar.

Mekanisme: Stack sebagai Memori “Belum Ditutup” #

Bila menemui kurung pembuka ((, [, {): push ke stack.
Bila menemui kurung penutup (), ], }): cek stack top. Bila top tidak cocok atau stack kosong → tidak seimbang.
Setelah seluruh string diproses: stack harus kosong.

cpp
bool is_balanced(const std::string& s) {
    std::vector<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push_back(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;
            char top = st.back();
            st.pop_back();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) return false;
        }
    }
    return st.empty();
}

Line-by-line #

std::vector<char> st;: kita pakai std::vector sebagai stack — push_back = push, back = peek, pop_back = pop.
st.push_back(c);: bila kurung pembuka, simpan ke stack. Stack mencatat “kurung ini belum ditutup”.
if (st.empty()) return false;: kurung penutup tanpa pasangan pembuka — langsung tidak seimbang.
char top = st.back(); st.pop_back();: ambil kurung pembuka terakhir (LIFO).
if ((c == ')' && top != '(') || ...) return false;: penutup harus cocok dengan pembuka terakhir. ) hanya boleh menutup (, bukan [ atau {.
return st.empty();: semua pembuka harus sudah ditutup. Bila stack masih berisi, ada pembuka tanpa penutup.

Kompleksitas: O(n) time, O(n) space (worst case semua pembuka).

Use Case 2: Undo Sederhana #

Setiap aksi pengguna (ketik karakter, hapus kata, pindahkan kursor) di-push ke history stack. Bila pengguna menekan Ctrl+Z, kita pop aksi terakhir dan apply kebalikannya.

cpp
void demo_undo() {
    Stack history;
    history.push(1);   // aksi: ketik "H"
    history.push(2);   // aksi: ketik "i"
    history.push(3);   // aksi: ketik "!"
    std::cout << "aksi terakhir: " << history.peek() << '\n';
    std::cout << "undo -> " << history.pop() << " dibatalkan\n";
    std::cout << "aksi terakhir sekarang: " << history.peek() << '\n';
}

Output yang Dihasilkan (setelah demo lengkap):

text
aksi terakhir: 3
undo -> 3 dibatalkan
aksi terakhir sekarang: 2

Aksi terakhir (3 = “ketik !”) di-pop dan dibatalkan. Setelah undo, aksi terakhir yang tersisa adalah 2 (ketik “i”). Implementasi undo nyata biasanya menyimpan inverse operation (mis. delete vs insert) sebagai data pada stack.

Use Case 3: Call Stack Bahasa Pemrograman #

Setiap kali fungsi dipanggil, sistem operasi mengalokasikan stack frame di call stack — berisi parameter, variabel lokal, dan return address. Saat fungsi return, stack frame di-pop dan eksekusi kembali ke pemanggil.

Fungsi bar() yang dipanggil terakhir adalah yang pertama return — LIFO. Rekursi memanfaatkan call stack secara alami: setiap panggilan rekursif menambah stack frame, dan rekursi yang terlalu dalam menyebabkan stack overflow.

Kode Lengkap Konsep Stack #

cpp
#include <iostream>
#include <vector>
#include <string>

// Stack sederhana berbasis vector
class Stack {
public:
    void push(int v) { data_.push_back(v); }
    int pop() {
        int atas = data_.back();
        data_.pop_back();
        return atas;
    }
    int peek() const { return data_.back(); }
    bool empty() const { return data_.empty(); }
    std::size_t size() const { return data_.size(); }
private:
    std::vector<int> data_;
};

// Demo: balanced parentheses dengan stack
bool is_balanced(const std::string& s) {
    std::vector<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push_back(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;
            char top = st.back();
            st.pop_back();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) return false;
        }
    }
    return st.empty();
}

// Demo: undo sederhana
void demo_undo() {
    Stack history;
    history.push(1);   // aksi: ketik "H"
    history.push(2);   // aksi: ketik "i"
    history.push(3);   // aksi: ketik "!"
    std::cout << "aksi terakhir: " << history.peek() << '\n';
    std::cout << "undo -> " << history.pop() << " dibatalkan\n";
    std::cout << "aksi terakhir sekarang: " << history.peek() << '\n';
}

int main() {
    // 1. Basic LIFO
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    std::cout << "size = " << s.size() << '\n';
    std::cout << "pop  = " << s.pop() << '\n';
    std::cout << "pop  = " << s.pop() << '\n';
    std::cout << "peek = " << s.peek() << '\n';

    std::cout << "\n--- Balanced Parentheses ---\n";
    std::cout << std::boolalpha;
    std::cout << "([{}])      : " << is_balanced("([{}])") << '\n';
    std::cout << "([{})]      : " << is_balanced("([{})]") << '\n';
    std::cout << "(())[]{}    : " << is_balanced("(())[]{}") << '\n';
    std::cout << "((())       : " << is_balanced("((())") << '\n';

    std::cout << "\n--- Demo Undo ---\n";
    demo_undo();

    return 0;
}

Output yang Dihasilkan:

text
size = 3
pop  = 30
pop  = 20
peek = 10

--- Balanced Parentheses ---
([{}])      : true
([{})]      : false
(())[]{}    : true
((())       : false

--- Demo Undo ---
aksi terakhir: 3
undo -> 3 dibatalkan
aksi terakhir sekarang: 2

void push(int v) { data_.push_back(v); }: tambah elemen ke akhir std::vector — posisi akhir adalah “top” stack.
int pop(): ambil back() (top), lalu pop_back(). Implementasi naif — di produksi, harus cek empty() dulu untuk menghindari undefined behavior.
is_balanced: stack menyimpan kurung pembuka yang belum ditutup. Saat kurung penutup muncul, kita pop dan validasi pasangan.
Hasil ([{}] false: kurung tutup } meng-pop [, padahal harusnya } menutup { yang lebih dalam — ketidaksesuaian terdeteksi.
Hasil ((()) false: dua pembuka ( tanpa penutup — stack tidak kosong di akhir.

Aplikasi Lanjutan Stack #

Aplikasi	Cara Kerja
Infix → postfix conversion	Shunting yard algorithm (Dijkstra)
Evaluasi postfix	Push operand, pop saat operator
DFS iteratif	Stack berisi node yang akan dikunjungi
Browser history (back button)	Push URL saat navigasi; pop untuk back
Editor autocomplete trie	Stack state saat mengetik

Ringkasan #

Stack adalah struktur LIFO dengan operasi push, pop, peek, semua O(1).
Use case klasik: balanced parentheses, undo, call stack, evaluasi ekspresi, DFS.
std::vector dapat berperan sebagai stack — push_back/pop_back/back adalah operasi stack natif.
Rekursi memanfaatkan call stack OS secara implisit; rekursi terlalu dalam menyebabkan stack overflow.
Chapter berikutnya akan membahas implementasi stack dengan array, linked list, dan std::stack<T, Container>.