📚 Ngăn xếp (Stack)

Xếp một chồng đĩa lên nhau: đĩa nào đặt lên sau cùng sẽ là đĩa lấy ra đầu tiên, vì bạn không thể rút một chiếc đĩa ở giữa chồng mà không làm đổ những chiếc bên trên. Đó chính là quy tắc LIFO - Last In, First Out (vào sau, ra trước) mà ngăn xếp (stack) mô phỏng lại: chỉ được thêm hoặc lấy phần tử ở một đầu duy nhất, gọi là đỉnh (top).

Hai thao tác nền tảng của stack:

push - đặt thêm một phần tử lên đỉnh.
pop - lấy và xóa phần tử đang ở đỉnh.

Cả hai đều chỉ động vào đúng một vị trí (đỉnh), nên đều chạy trong O(1) - không cần dịch chuyển phần tử nào khác.

Vì sao chỉ thao tác được ở một đầu lại hữu ích?

Nghe có vẻ là một giới hạn, nhưng chính giới hạn này khiến stack mô tả rất tự nhiên nhiều tình huống thực tế:

Nút Undo/Redo: mỗi hành động được push vào một stack lịch sử; Undo chính là pop hành động gần nhất ra và hoàn tác nó.
Nút Back của trình duyệt: mỗi trang bạn mở được đẩy vào stack; bấm Back là pop trang hiện tại để quay về trang trước đó.
Ngăn xếp lời gọi hàm (call stack): mỗi khi một hàm gọi hàm khác, hệ thống push một khung nhớ mới chứa biến cục bộ của hàm đó; khi hàm return, khung nhớ bị pop ra. Đây là lý do đệ quy quá sâu gây tràn stack (stack overflow) - xem thêm ở trang Đệ quy.

Cài đặt

Vì push/pop chỉ động vào một đầu, bạn có thể cài đặt stack dựa trên bất kỳ cấu trúc nào hỗ trợ thêm/xóa nhanh ở một đầu - phổ biến nhất là dùng thẳng list của Python (thao tác ở cuối mảng động đều là O(1) trung bình):

stack = []
stack.append(1)      # push
stack.append(3)
stack.append(2)
top = stack[-1]       # peek: xem đỉnh mà không lấy ra, O(1)
val = stack.pop()      # pop: lấy và xóa đỉnh, O(1)
is_empty = len(stack) == 0

Ứng dụng: kiểm tra ngoặc hợp lệ

Một bài toán kinh điển thể hiện rõ sức mạnh của LIFO: cho một chuỗi chứa (, ), [, ], {, }, kiểm tra các cặp ngoặc có “khớp lồng nhau” đúng cách không (ví dụ ([{}]) hợp lệ, ([)] thì không).

Ý tưởng: mỗi khi gặp ngoặc mở, đẩy nó vào stack; mỗi khi gặp ngoặc đóng, ngoặc mở gần nhất chưa đóng (tức đỉnh stack) bắt buộc phải là loại tương ứng - đây chính xác là tính chất “vào sau ra trước”.

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack.pop() != pairs[ch]:
                return False   # đóng sai loại, hoặc đóng khi chưa có gì để đóng
    return len(stack) == 0     # còn ngoặc mở chưa đóng -> False

Độ phức tạp: O(n) thời gian (duyệt chuỗi một lượt) và O(n) bộ nhớ trong trường hợp xấu nhất (chuỗi toàn ngoặc mở, ví dụ (((((().