Penerapan Stack dan Queue

Stack dan queue bukan sekadar struktur data abstrak — keduanya adalah blok dasar banyak algoritma fundamental. Empat penerapan paling penting yang akan kita bahas pada Chapter ini: parenthesis matching (validasi tanda kurung), konversi infix ke postfix dengan algoritma shunting yard Dijkstra, BFS traversal graph dengan queue, dan topological sort Kahn untuk graph asiklik. Setiap penerapan memperlihatkan mengapa LIFO atau FIFO adalah pilihan natural untuk masalah tertentu, dan bagaimana stack/queue menjadi jembatan antara struktur data dan algoritma graph. Pada akhir Chapter, kita akan memiliki vocabulary algoritma yang siap dipakai di banyak soal DSA.

Penerapan 1: Parenthesis Matching #

Aturan #

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

Mekanisme: Stack sebagai Memori Pembuka #

Stack menyimpan kurung pembuka yang belum ditutup. Saat kurung penutup muncul, top stack harus berisi pasangan pembukanya. Bila tidak cocok atau stack kosong → tidak valid. Akhir string: stack harus kosong.

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

Kompleksitas: O(n) time, O(n) space. LIFO cocok karena kurung penutup memasangkan dengan kurung pembuka terakhir yang belum ditutup.

Penerapan 2: Infix ke Postfix (Shunting Yard) #

Aturan #

Konversi ekspresi infix (mis. 3 + 4 * 2 / (1 - 5)) ke postfix (3 4 2 * 1 5 - / +). Postfix mudah dievaluasi tanpa precedence rule.

Mekanisme: Stack Operator + Precedence #

Algoritma shunting yard (Dijkstra):

Bila operand (angka/huruf): langsung output.
Bila (: push ke stack.
Bila ): pop dan output operator sampai ( ditemui, lalu buang (.
Bila operator: pop dan output semua operator di stack dengan precedence ≥ operator saat ini, lalu push operator saat ini. Inilah inti precedence rule.

Precedence: * / > + -.

cpp
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

std::string infix_to_postfix(const std::string& expr) {
    std::string output;
    std::stack<char> ops;
    for (char c : expr) {
        if (std::isspace(c)) continue;
        if (std::isdigit(c) || std::isalpha(c)) {
            output.push_back(c);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.empty() && ops.top() != '(') {
                output.push_back(ops.top());
                ops.pop();
            }
            if (!ops.empty()) ops.pop();  // buang '('
        } else {  // operator
            while (!ops.empty() && precedence(ops.top()) >= precedence(c)) {
                output.push_back(ops.top());
                ops.pop();
            }
            ops.push(c);
        }
    }
    while (!ops.empty()) {
        output.push_back(ops.top());
        ops.pop();
    }
    return output;
}

Line-by-line #

if (std::isdigit(c) || std::isalpha(c)) output.push_back(c);: operand langsung ke output — tidak perlu precedence.
else if (c == '(') ops.push(c);: kurung pembuka push, sebagai marker. Tidak akan di-output.
else if (c == ')'): pop sampai ( — semua operator di antara (...) keluar. Setelah loop, buang (.
while (!ops.empty() && precedence(ops.top()) >= precedence(c)): pop operator dengan precedence sama atau lebih tinggi. Kondisi >= (bukan >) mengimplementasikan left-associative: 3 - 4 - 5 dievaluasi sebagai (3 - 4) - 5, bukan 3 - (4 - 5).
while (!ops.empty()) output.push_back(ops.top()); ops.pop();: di akhir, pop semua operator tersisa.

Penerapan 3: Evaluasi Postfix #

Mekanisme: Stack Operand #

Postfix mudah dievaluasi dengan stack:

Bila operand: push ke stack.
Bila operator: pop dua operand (kanan dulu, lalu kiri), hitung, push hasil.
Akhir: satu elemen tersisa di stack = jawaban.

cpp
int eval_postfix(const std::string& postfix) {
    std::stack<int> st;
    for (char c : postfix) {
        if (std::isdigit(c)) {
            st.push(c - '0');
        } else {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            switch (c) {
                case '+': st.push(a + b); break;
                case '-': st.push(a - b); break;
                case '*': st.push(a * b); break;
                case '/': st.push(a / b); break;
            }
        }
    }
    return st.top();
}

Line-by-line #

int b = st.top(); st.pop(); int a = st.top(); st.pop();: urutan pop penting. b (operand kanan) di-pop dulu, lalu a (operand kiri). Bila urutan terbalik, a - b dan a / b akan salah.
switch (c): pilih operasi. Push hasil kembali ke stack.

Penerapan 4: BFS dengan Queue #

Aturan #

BFS menjelajah graph dari node sumber, kunjungi layer demi layer berdasarkan jarak.

Mekanisme: Queue Menjaga Urutan Jarak #

Push sumber ke queue, tandai visited.
Selama queue tidak kosong:
- Pop front (dequeue), proses node.
- Untuk setiap neighbor yang belum visited: tandai visited, push ke queue.

Queue FIFO memastikan node dengan jarak lebih dekat diproses dulu.

cpp
std::vector<int> bfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<int> traversal;
    std::vector<bool> visited(adj.size(), false);
    std::queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        traversal.push_back(cur);
        for (int neighbor : adj[cur]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    return traversal;
}

Penerapan 5: Topological Sort (Kahn’s Algorithm) #

Aturan #

Diberikan DAG (Directed Acyclic Graph), urutkan node sehingga untuk setiap edge u → v, u muncul sebelum v dalam urutan. Soal klasik: dependency resolution (build order, course schedule).

Mekanisme: Queue + Indegree #

Hitung indegree tiap node (jumlah edge masuk).
Push semua node dengan indegree 0 ke queue (node tanpa dependency).
Selama queue tidak kosong:
- Pop front, tambah ke urutan topological.
- Untuk setiap neighbor: decrement indegree. Bila jadi 0, push ke queue.
Bila urutan tidak mencakup semua node → graph punya cycle (tidak valid untuk topological sort).

cpp
std::vector<int> topological_sort(const std::vector<std::vector<int>>& adj,
                                  std::vector<int> indegree) {
    std::queue<int> q;
    for (std::size_t i = 0; i < indegree.size(); ++i) {
        if (indegree[i] == 0) q.push(static_cast<int>(i));
    }
    std::vector<int> order;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        order.push_back(cur);
        for (int neighbor : adj[cur]) {
            if (--indegree[neighbor] == 0) q.push(neighbor);
        }
    }
    return order;
}

Line-by-line #

for (...) if (indegree[i] == 0) q.push(i);: inisialisasi — node tanpa dependency (indegree 0) langsung siap diproses.
order.push_back(cur);: tambah node ke urutan. Setelah semua neighbor diproses, urutan ini valid topological.
if (--indegree[neighbor] == 0) q.push(neighbor);: decrement indegree. Bila jadi 0, semua dependency sudah diproses — push ke queue.
Bila order.size() != n (di luar fungsi): graph punya cycle. Topological sort tidak terdefinisi untuk graph dengan cycle.

Kode Lengkap Lima Penerapan #

cpp
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <cctype>

// 1. Parenthesis matching dengan stack
bool is_balanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;
            char top = st.top(); st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) return false;
        }
    }
    return st.empty();
}

// 2. Infix to postfix (Shunting Yard - disederhanakan)
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

std::string infix_to_postfix(const std::string& expr) {
    std::string output;
    std::stack<char> ops;
    for (char c : expr) {
        if (std::isspace(c)) continue;
        if (std::isdigit(c) || std::isalpha(c)) {
            output.push_back(c);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.empty() && ops.top() != '(') {
                output.push_back(ops.top());
                ops.pop();
            }
            if (!ops.empty()) ops.pop();  // buang '('
        } else {  // operator
            while (!ops.empty() && precedence(ops.top()) >= precedence(c)) {
                output.push_back(ops.top());
                ops.pop();
            }
            ops.push(c);
        }
    }
    while (!ops.empty()) {
        output.push_back(ops.top());
        ops.pop();
    }
    return output;
}

// 3. Evaluasi postfix
int eval_postfix(const std::string& postfix) {
    std::stack<int> st;
    for (char c : postfix) {
        if (std::isdigit(c)) {
            st.push(c - '0');
        } else {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            switch (c) {
                case '+': st.push(a + b); break;
                case '-': st.push(a - b); break;
                case '*': st.push(a * b); break;
                case '/': st.push(a / b); break;
            }
        }
    }
    return st.top();
}

// 4. BFS dengan queue (graph adjacency list)
std::vector<int> bfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<int> traversal;
    std::vector<bool> visited(adj.size(), false);
    std::queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        traversal.push_back(cur);
        for (int neighbor : adj[cur]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    return traversal;
}

// 5. Topological sort (Kahn's algorithm) dengan queue
std::vector<int> topological_sort(const std::vector<std::vector<int>>& adj,
                                  std::vector<int> indegree) {
    std::queue<int> q;
    for (std::size_t i = 0; i < indegree.size(); ++i) {
        if (indegree[i] == 0) q.push(static_cast<int>(i));
    }
    std::vector<int> order;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        order.push_back(cur);
        for (int neighbor : adj[cur]) {
            if (--indegree[neighbor] == 0) q.push(neighbor);
        }
    }
    return order;
}

int main() {
    std::cout << "=== 1. Parenthesis Matching ===\n";
    std::cout << std::boolalpha;
    std::cout << "([{}])   : " << is_balanced("([{}])") << '\n';
    std::cout << "([{})]   : " << is_balanced("([{})]") << '\n';
    std::cout << "((())    : " << is_balanced("((())") << '\n';

    std::cout << "\n=== 2. Infix to Postfix + Evaluasi ===\n";
    std::string infix = "3 + 4 * 2 / (1 - 5)";
    std::string postfix = infix_to_postfix(infix);
    std::cout << "infix   : " << infix << '\n';
    std::cout << "postfix : " << postfix << '\n';
    std::cout << "eval    : " << eval_postfix(postfix) << '\n';

    std::cout << "\n=== 3. BFS dengan Queue ===\n";
    std::vector<std::vector<int>> adj(5);
    adj[0] = {1, 2};
    adj[1] = {3};
    adj[2] = {3, 4};
    adj[3] = {4};
    adj[4] = {};
    auto bfs_order = bfs(adj, 0);
    std::cout << "BFS dari 0: ";
    for (int x : bfs_order) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "\n=== 4. Topological Sort (Kahn) ===\n";
    std::vector<std::vector<int>> dag(5);
    dag[0] = {1, 2};
    dag[1] = {3};
    dag[2] = {3};
    dag[3] = {4};
    std::vector<int> indegree(5, 0);
    for (auto& nbrs : dag)
        for (int v : nbrs) indegree[v]++;
    auto topo = topological_sort(dag, indegree);
    std::cout << "Topo order: ";
    for (int x : topo) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

text
=== 1. Parenthesis Matching ===
([{}])   : true
([{})]   : false
((())    : false

=== 2. Infix to Postfix + Evaluasi ===
infix   : 3 + 4 * 2 / (1 - 5)
postfix : 342*15-/+
eval    : 1

=== 3. BFS dengan Queue ===
BFS dari 0: 0 1 2 3 4 

=== 4. Topological Sort (Kahn) ===
Topo order: 0 1 2 3 4 

Postfix 342*15-/+:
- 3 4 2 → operand, output. Stack: []
- * → operator. Output: 342*. Stack operator sisa: +
- 1 5 → operand. Output: 342*15. Stack operator: +, /, (, -
- ) → pop sampai (. Output: 342*15-. Buang (. Stack operator: +, /
- akhir → pop semua. Output: 342*15-/+
Eval 342*15-/+ = 1:
- 3 4 2 * → 3 8 (4 * 2)
- 3 8 1 5 - → 3 8 -4 (1 - 5)
- 3 8 -4 / → 3 -2 (8 / -4, integer division)
- 3 -2 + → 1 (3 + (-2))
- Hasil = 1
BFS 0 1 2 3 4: dari node 0, layer 0 = {0}, layer 1 = {1, 2}, layer 2 = {3, 4}. Urutan FIFO sesuai jarak.
Topo 0 1 2 3 4: node 0 (indegree 0) diproses dulu, lalu 1 dan 2 (indegree jadi 0 setelah 0), lalu 3, lalu 4. Setiap edge u → v memiliki u sebelum v dalam urutan.

Tabel Ringkas Penerapan #

Penerapan	Struktur	Kompleksitas	Use Case
Parenthesis matching	Stack	O(n)	Validasi syntax editor, parser
Infix → postfix	Stack	O(n)	Compiler, kalkulator
Evaluasi postfix	Stack	O(n)	VM bytecode, kalkulator
BFS	Queue	O(V + E)	Shortest path unweighted, level-order
Topological sort (Kahn)	Queue	O(V + E)	Build order, course schedule

Aplikasi Tambahan #

Beberapa penerapan lain yang sering muncul:

DFS iteratif: stack berisi node yang akan dikunjungi (alternatif rekursi).
Dijkstra shortest path: priority queue (min-heap), varian queue dengan prioritas.
A search*: priority queue dengan heuristic.
LRU cache: deque + hash map untuk O(1) access dan eviction.
Sliding window maximum: deque monotonic (sudah dibahas Chapter monotonic-queue).
Expression tree construction: stack untuk membangun tree dari postfix.

Ringkasan #

Parenthesis matching: stack menyimpan pembuka; cocok dengan LIFO karena penutup memasangkan pembuka terakhir.
Infix → postfix (shunting yard): stack operator + precedence rule. >= precedence implementasi left-associative.
Evaluasi postfix: stack operand, pop dua untuk operator, push hasil.
BFS: queue menjamin urutan jarak — node lebih dekat diproses dulu.
Topological sort Kahn: queue + indegree. Node dengan indegree 0 diproses dulu; cycle terdeteksi bila urutan tidak lengkap.
Pilihan stack vs queue: DFS pakai stack (kedalaman), BFS pakai queue (jarak). Hampir semua traversal graph bisa dipilih berdasarkan kriteria ini.