Stack (tumpukan) adalah struktur data dengan aturan paling ketat: elemen hanya boleh ditambahkan dan diambil dari satu ujung yang sama. Karena elemen yang terakhir masuk adalah yang pertama keluar, aturan ini disebut LIFO (Last In, First Out) — persis seperti tumpukan piring di dapur. Aturan sederhana ini membuat stack terlihat terbatas, tetapi justru kesederhanaan itulah yang menjadikannya alat utama untuk soal-soal yang sifatnya “mundur dari yang terakhir”: memeriksa kurung, membatalkan aksi undo, dan menelusuri graf dengan DFS. Chapter ini membangun stack di atas std::vector, lalu memakainya untuk memecahkan satu masalah klasik.

Konsep LIFO dan Empat Operasi Inti #

Antarmuka stack terdiri dari empat operasi: push menaruh elemen di puncak, pop mengambil elemen puncak, peek (kadang disebut top) melihat elemen puncak tanpa mengambilnya, dan isEmpty memeriksa kekosongan. Semua operasi ini bekerja di O(1) — tidak ada pencarian, tidak ada pergeseran. Ketika kita menyimpan “pekerjaan yang tertunda”, stack menjamin pekerjaan yang paling baru dimulai diselesaikan lebih dulu.

Perhatikan pembagian tugasnya: peek membaca tanpa mengubah isi, sedangkan pop mengubah isi. Implementasi yang aman memeriksa isEmpty sebelum kedua operasi tersebut, karena pop atau peek pada stack kosong adalah undefined behavior.

Implementasi Stack Berbasis std::vector #

Karena push_back dan pop_back dari vector bekerja persis di ujung, vector adalah fondasi yang alami: ujung belakang vector kita perlakukan sebagai puncak tumpukan. Program berikut membangun class Stack dengan pembungkusan aman, lalu memakai vektor char untuk aplikasi pemeriksa kurung:

cpp 
// Stack berbasis vector + aplikasi klasik: pemeriksa kurung seimbang.
#include <iostream>
#include <string>
#include <vector>

class Stack {
public:
    void push(int nilai) { data_.push_back(nilai); }   // taruh di atas

    void pop() {
        if (!isEmpty()) data_.pop_back();  // jaga-jaga: pop pada stack kosong adalah UB
    }

    int peek() const { return data_.back(); }  // panggil hanya bila tidak kosong

    bool isEmpty() const { return data_.empty(); }
    int size() const { return static_cast<int>(data_.size()); }

private:
    std::vector<int> data_;
};

// Memeriksa apakah semua kurung () [] {} seimbang dan tersarang dengan benar.
bool kurangSeimbang(const std::string& teks) {
    std::vector<char> tumpukan;
    for (char c : teks) {
        if (c == '(' || c == '[' || c == '{') {
            tumpukan.push_back(c);               // pembuka: push
        } else if (c == ')' || c == ']' || c == '}') {
            if (tumpukan.empty()) return false;  // penutup tanpa pembuka
            char buka = tumpukan.back();
            tumpukan.pop_back();
            if ((c == ')' && buka != '(') ||
                (c == ']' && buka != '[') ||
                (c == '}' && buka != '{')) {
                return false;                    // jenis kurung tidak cocok
            }
        }
    }
    return tumpukan.empty();  // sisa pembuka berarti belum seimbang
}

int main() {
    Stack s;
    std::cout << "Kosong? " << (s.isEmpty() ? "ya" : "tidak") << '\n';
    s.push(10);
    s.push(20);
    s.push(30);
    std::cout << "peek() = " << s.peek() << '\n';
    std::cout << "size() = " << s.size() << '\n';
    while (!s.isEmpty()) {
        std::cout << "pop()  = " << s.peek() << '\n';
        s.pop();
    }
    std::cout << "Kosong? " << (s.isEmpty() ? "ya" : "tidak") << '\n';

    std::string uji[] = {"({[]})", "([)]", "{[()]}()", "())("};
    for (const std::string& teks : uji) {
        std::cout << teks << " -> "
                  << (kurangSeimbang(teks) ? "seimbang" : "tidak seimbang") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Kosong? ya
peek() = 30
size() = 3
pop()  = 30
pop()  = 20
pop()  = 10
Kosong? ya
({[]}) -> seimbang
([)] -> tidak seimbang
{[()]}() -> seimbang
())( -> tidak seimbang

Bedah baris penting:

  1. Baris 8 (push): seluruh pekerjaan push hanyalah push_back — menaruh elemen di ujung vector, O(1) amortized seperti yang kita hitung di chapter Dynamic Array.
  2. Baris 10-12 (pop): pop_back hanya dipanggil bila stack tidak kosong; penjagaan ini mencegah undefined behavior.
  3. Baris 14-17 (peek dan isEmpty): back() membaca ujung tanpa menghapus; empty() menjadi syarat aman untuk keduanya.
  4. Baris 27 (push_back pembuka): setiap kurung bukan penutup masuk ke tumpukan; kita belum tahu dengan apa ia akan berpasangan.
  5. Baris 30-32: saat menemukan penutup, elemen teratas diambil sebagai kandidat pasangan. Bila tumpukan kosong di titik ini, berarti ada penutup tanpa pembuka — langsung dinyatakan tidak seimbang.
  6. Baris 33-37: pasangan harus sejenis: ) menuntut (, ] menuntut [, } menuntut {. Ketidakcocokan apa pun menggagalkan pemeriksaan.
  7. Baris 40: setelah seluruh karakter diproses, tumpukan harus kosong; sisa pembuka berarti masih ada yang belum ditutup.

Aplikasi: Memeriksa Kurung Seimbang #

Keluaran program menunjukkan empat kasus uji. String "({[]})" seimbang karena setiap penutup berpasangan dengan pembuka teratas; string "([)]" gagal karena ) menemukan [ di puncak tumpukan — urutan penutupan salah meski jumlah kurung pas. String "{[()]}()" seimbang dua lapis, sedangkan "())(" gagal karena tanda ) kedua menemukan tumpukan kosong.

Bagaimana pemeriksaan bekerja langkah demi langkah untuk "([)]": ( di-push, [ di-push, lalu ) datang — puncak tumpukan adalah [, jenisnya tidak cocok, fungsi mengembalikan false tanpa perlu memeriksa karakter lain. Proses ini menunjukkan kekuatan stack: keputusan selalu diambil dari data terbaru, dan data terbaru memang selalu ada di puncak.

Stack di Sekitar Kita #

Begitu pola LIFO dikenali, kita melihatnya di mana-mana. Fitur undo pada editor menyimpan aksi dalam stack; tombol back pada browser menyimpan halaman dalam stack; dan compiler sendiri menjalankan function call melalui call stack, di mana setiap fungsi aktif mendapat frame di puncak. Pada Section ini nantinya, DFS (depth-first search) pada chapter Graph akan memakai rekursi yang di dalamnya bekerja dengan stack yang sama.

Satu sisi aturan LIFO yang belum kita bahas adalah pasangannya, FIFO (First In, First Out) — antrian yang melayani yang paling awal datang lebih dulu. Itulah topik chapter berikutnya, bersama dengan deque yang menggabungkan keduanya.

Rujukan resmi: std::stack dan std::vector .