Ngăn xếp (Stack): Cơ chế LIFO, kiểm tra dấu ngoặc và tính biểu thức hậu tố trong C++ & Python

Ngăn xếp (stack) là cấu trúc tuyến tính nền tảng để giải quyết các bài toán có tính chất "lồng nhau" hoặc "quay lui về trạng thái gần nhất": từ thao tác hoàn tác (Ctrl + Z), ngăn xếp lời gọi hàm (đệ quy), đến kiểm tra cú pháp dấu ngoặc và tính giá trị biểu thức toán học. Như đã giới thiệu trong lộ trình cấu trúc dữ liệu và giải thuật, mọi thao tác thêm, xóa và đọc phần tử ở đỉnh ngăn xếp có chi phí hằng số hoặc hằng số khấu hao tùy bộ chứa. Với vector và list, lần thêm gây cấp phát lại có thể tốn O(n).

Bài viết này trình bày bản chất cơ chế LIFO, cách dùng Stack trong C++17 và Python 3, lỗi sập chương trình khi ngăn xếp rỗng, cùng hai ứng dụng kinh điển: kiểm tra dãy ngoặc hợp lệ và tính giá trị biểu thức hậu tố (Reverse Polish Notation — RPN).

Cơ chế LIFO (Vào sau ra trước) và 4 thao tác O(1)

Hãy hình dung một chồng đĩa đặt trong ống trụ kín đáy: chiếc đĩa nào được đặt vào muộn nhất (nằm ở trên cùng) sẽ được nhấc ra sớm nhất. Nguyên lý đó gọi là LIFO (Last-In, First-Out — Vào sau ra trước). Khác với mảng cho phép truy cập chỉ số bất kỳ, ngăn xếp giới hạn mọi thao tác vào một đầu duy nhất gọi là đỉnh ngăn xếp (top), nhờ đó cả 4 thao tác chuẩn đều đạt độ phức tạp thuật toán Big-O là O(1):

Cách sử dụng Stack trong C++ và Python

C++17: Chọn std::stack hay std::vector?

Thư viện chuẩn C++ cung cấp std::stack trong <stack>. Tuy nhiên, khi lập trình thi đấu hoặc phỏng vấn, bạn cũng có thể dùng trực tiếp std::vector làm ngăn xếp (push_back, pop_back, back) vì ba lợi điểm: vùng nhớ liên tiếp thân thiện với bộ nhớ đệm CPU, dễ dàng duyệt từ đáy lên đỉnh khi cần ghép kết quả hoặc gỡ lỗi, và hỗ trợ reserve(n) để cấp phát trước bộ nhớ.

Python 3: Dùng list có sẵn

Trong Python, list là mảng động nên hai thao tác ở cuối danh sách (st.append(x) và st.pop()) có chi phí O(1) khấu hao. Tuyệt đối không dùng đầu danh sách làm đỉnh (st.insert(0, x) hay st.pop(0)) vì Python phải dịch chuyển toàn bộ n phần tử phía sau, làm mỗi thao tác tốn O(n) (xem thêm ở bài hàng đợi Queue).

Cảnh báo lỗi gọi top() hoặc pop() khi ngăn xếp rỗng

Trong C++, st.top() và st.pop() không tự kiểm tra ngăn xếp rỗng. Gọi chúng khi st.empty() == true gây hành vi không xác định (Undefined Behavior), có thể sập chương trình hoặc biểu hiện khác (trong Python sẽ ném IndexError). Quy tắc bắt buộc là luôn kiểm tra !st.empty() (C++) hoặc if st: (Python) trước khi gọi top() / pop().

Ứng dụng 1: Kiểm tra dãy ngoặc hợp lệ (Valid Parentheses)

Ý tưởng LIFO và bảng chạy tay

Cho xâu s gồm các ký tự '(', ')', '{', '}', '[', ']'. Trong một biểu thức ngoặc lồng nhau hợp lệ, dấu ngoặc mở nào xuất hiện muộn nhất (nằm sâu nhất bên trong) phải được đóng lại sớm nhất:

• Gặp ngoặc mở ('(', '{', '['): đẩy (push) vào đỉnh ngăn xếp để chờ đóng.
• Gặp ngoặc đóng (')', '}', ']'): nếu ngăn xếp rỗng hoặc phần tử ở đỉnh (top) không cùng cặp với ngoặc đóng hiện tại thì kết luận ngay không hợp lệ; ngược lại, xóa đỉnh (pop) và duyệt tiếp.
• Duyệt hết xâu: hợp lệ khi và chỉ khi ngăn xếp rỗng hoàn toàn (st.empty()).

Bảng chạy tay với s = "({[]})" (Hợp lệ) và s = "([)]" (Sai thứ tự):

Code mẫu C++ và Python kiểm tra dãy ngoặc

Các hàm dưới đây nhận xâu chỉ gồm sáu ký tự ngoặc; xâu rỗng là hợp lệ. Mỗi code được lấy trực tiếp từ tệp đã chạy kiểm, nên không có một bản khác chép riêng trong bài.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool khop_cap(char mo, char dong) {
    return (mo == '(' && dong == ')') ||
           (mo == '[' && dong == ']') ||
           (mo == '{' && dong == '}');
}

// Kiểm tra dãy ngoặc hợp lệ bằng Ngăn xếp (Stack) trong O(n)
bool ngoac_hop_le(const string& s) {
    stack<char> st;
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);
        } else {
            // Bắt buộc kiểm tra st.empty() trước khi gọi st.top()
            if (st.empty() || !khop_cap(st.top(), ch)) {
                return false;
            }
            st.pop();
        }
    }
    // Cuối cùng ngăn xếp phải rỗng hoàn toàn (không còn ngoặc mở thừa)
    return st.empty();
}

int main() {
    cout << ngoac_hop_le("{[()]}") << " "
         << ngoac_hop_le("([)]") << " "
         << ngoac_hop_le(")(") << " "
         << ngoac_hop_le("(((") << "\n";
    return 0;
}

def ngoac_hop_le(s: str) -> bool:
    """Kiểm tra dãy ngoặc hợp lệ bằng Ngăn xếp (Stack) trong O(n)."""
    cap_mo = {")": "(", "]": "[", "}": "{"}
    st: list[str] = []
    for ch in s:
        if ch in "([{":
            st.append(ch)
        else:
            if not st or st[-1] != cap_mo.get(ch, ""):
                return False
            st.pop()
    return len(st) == 0


if __name__ == "__main__":
    cac_mau = ["{[()]}", "([)]", ")(", "((("]
    print(*(1 if ngoac_hop_le(m) else 0 for m in cac_mau))

Kết quả của tệp chạy bên dưới là 1 0 0 0, lần lượt cho {[()]}, ([)], )( và (((. Bảng chạy tay trước đó dùng thêm hai đầu vào khác để giải thích thao tác. Mỗi ký tự được push tối đa 1 lần và pop tối đa 1 lần nên độ phức tạp thời gian và bộ nhớ đều là O(n).

Ứng dụng 2: Tính giá trị biểu thức hậu tố (Reverse Polish Notation — RPN)

Nguyên tắc tính biểu thức hậu tố bằng Stack

Ví dụ giả định biểu thức hợp lệ, toán tử luôn có đủ hai toán hạng, mẫu số khác 0 và mọi kết quả trung gian vừa long long của C++. Nếu xử lý dữ liệu từ người dùng, cần kiểm các điều kiện này và yêu cầu còn đúng một giá trị ở cuối.

Khác với biểu thức trung tố (infix) như (2 + 1) * 3, biểu thức hậu tố (postfix / RPN) đặt toán tử ngay sau hai toán hạng của nó: 2 1 + 3 *, hoặc 4 13 5 / + cho 4 + (13 / 5). Cách biểu diễn này hoàn toàn không cần dấu ngoặc hay độ ưu tiên toán tử, và được tính trực tiếp trong O(n) bằng một ngăn xếp:

1. Duyệt từng phần tử (token) từ trái sang phải; nếu gặp số, đẩy (push) vào ngăn xếp.
2. Nếu gặp toán tử (+, -, *, /), lấy 2 số ở đỉnh ra tính rồi đẩy kết quả trở lại ngăn xếp.
3. Kết thúc biểu thức, phần tử duy nhất còn lại ở đỉnh ngăn xếp là đáp số.

Lưu ý thứ tự toán hạng khi trừ và chia: Với biểu thức 10 3 - (tức 10 - 3), số 10 vào trước và số 3 vào sau (nằm ở đỉnh). Do đó lần pop() thứ nhất lấy ra toán hạng bên phải b = 3, lần pop() thứ hai mới lấy ra toán hạng bên trái a = 10. Bạn phải tính a - b và a / b, không phải b - a!

#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

// Tính giá trị biểu thức hậu tố (Reverse Polish Notation - RPN) bằng Stack
long long tinh_rpn(const vector<string>& tokens) {
    stack<long long> st;
    for (const string& tk : tokens) {
        if (tk == "+" || tk == "-" || tk == "*" || tk == "/") {
            // Lưu ý thứ tự LIFO: lấy ra trước là toán hạng PHẢI (b), lấy ra sau là toán hạng TRÁI (a)
            long long b = st.top(); st.pop();
            long long a = st.top(); st.pop();
            if (tk == "+") st.push(a + b);
            else if (tk == "-") st.push(a - b);
            else if (tk == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(stoll(tk));
        }
    }
    return st.top();
}

int main() {
    vector<string> bt1 = {"2", "1", "+", "3", "*"};
    vector<string> bt2 = {"4", "13", "5", "/", "+"};
    cout << tinh_rpn(bt1) << " " << tinh_rpn(bt2) << "\n";
    return 0;
}

def tinh_rpn(tokens: list[str]) -> int:
    """Tính giá trị biểu thức hậu tố (Reverse Polish Notation - RPN) bằng Stack."""
    st: list[int] = []
    for tk in tokens:
        if tk in {"+", "-", "*", "/"}:
            b = st.pop()  # Toán hạng phải (vào sau nên ra trước)
            a = st.pop()  # Toán hạng trái (vào trước nên ra sau)
            if tk == "+":
                st.append(a + b)
            elif tk == "-":
                st.append(a - b)
            elif tk == "*":
                st.append(a * b)
            else:
                q = abs(a) // abs(b)
                st.append(-q if (a < 0) != (b < 0) else q)  # Chia nguyên chính xác về 0
        else:
            st.append(int(tk))
    return st[-1]


if __name__ == "__main__":
    bt1 = ["2", "1", "+", "3", "*"]
    bt2 = ["4", "13", "5", "/", "+"]
    print(tinh_rpn(bt1), tinh_rpn(bt2))

Kết quả chạy chương trình: 9 6. Sau khi nắm vững Stack cơ bản, bạn hãy khám phá tiếp kỹ thuật ngăn xếp đơn điệu (Monotonic Stack) để giải bài toán tìm phần tử lớn hơn gần nhất trong O(n).

Luyện ngay trên Big-O Coding

Bắt đầu bằng kiểm tra ngoặc, sau đó tính hậu tố và rút gọn đường dẫn; ba bài đều dùng thứ tự xử lý vào sau ra trước.

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::stack
• Python: Using Lists as Stacks
• cppreference: Arithmetic operators