📚 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):

Python

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

C++

#include <stack>

int main() {
    std::stack<int> stk;
    stk.push(1);              // push
    stk.push(3);
    stk.push(2);
    int top = stk.top();      // peek: xem đỉnh mà không lấy ra, O(1)
    int val = stk.top();
    stk.pop();                 // pop: lấy và xóa đỉnh, O(1)
    bool isEmpty = stk.empty();
    return 0;
}

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);      // push
        stack.push(3);
        stack.push(2);
        int top = stack.peek();  // peek: xem đỉnh mà không lấy ra, O(1)
        int val = stack.pop();   // pop: lấy và xóa đỉnh, O(1)
        boolean isEmpty = stack.isEmpty();
    }
}

Kotlin

fun main() {
    val stack = ArrayDeque<Int>()
    stack.addLast(1)      // push
    stack.addLast(3)
    stack.addLast(2)
    val top = stack.last()          // peek: xem đỉnh mà không lấy ra, O(1)
    val value = stack.removeLast()  // pop: lấy và xóa đỉnh, O(1)
    val isEmpty = stack.isEmpty()
}

Dart

void main() {
  List<int> stack = [];
  stack.add(1);      // push
  stack.add(3);
  stack.add(2);
  int top = stack.last;         // peek: xem đỉnh mà không lấy ra, O(1)
  int val = stack.removeLast();  // pop: lấy và xóa đỉnh, O(1)
  bool isEmpty = stack.isEmpty;
}

Ghi chú

Cũng có thể cài đặt stack bằng linked list (đỉnh stack = đầu danh sách, push/pop đều thao tác ở head - xem Danh sách liên kết). Cách dùng array/list phổ biến hơn trong thực hành vì tận dụng được cache tốt hơn; cách dùng linked list tránh được chi phí resize khi mảng động phải cấp phát lại.

Ứ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”.

Python

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

C++

#include <string>
#include <stack>
#include <unordered_map>

bool isValid(const std::string& s) {
    std::unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    std::stack<char> stk;
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stk.push(ch);
        } else {
            if (stk.empty() || stk.top() != pairs[ch]) {
                return false;   // đóng sai loại, hoặc đóng khi chưa có gì để đóng
            }
            stk.pop();
        }
    }
    return stk.empty();     // còn ngoặc mở chưa đóng -> false
}

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static boolean isValid(String s) {
        Map<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put(']', '[');
        pairs.put('}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;   // đóng khi chưa có gì để đóng
                }
                char popped = stack.pop();
                if (popped != pairs.get(ch)) {
                    return false;   // đóng sai loại
                }
            }
        }
        return stack.isEmpty();     // còn ngoặc mở chưa đóng -> false
    }
}

Kotlin

fun isValid(s: String): Boolean {
    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
    val stack = ArrayDeque<Char>()
    for (ch in s) {
        if (ch in "([{") {
            stack.addLast(ch)
        } else {
            if (stack.isEmpty() || stack.removeLast() != pairs[ch]) {
                return false   // đóng sai loại, hoặc đóng khi chưa có gì để đóng
            }
        }
    }
    return stack.isEmpty()     // còn ngoặc mở chưa đóng -> false
}

Dart

bool isValid(String s) {
  final pairs = {')': '(', ']': '[', '}': '{'};
  final stack = <String>[];
  for (int i = 0; i < s.length; i++) {
    final ch = s[i];
    if ('([{'.contains(ch)) {
      stack.add(ch);
    } else {
      if (stack.isEmpty || stack.removeLast() != pairs[ch]) {
        return false; // đóng sai loại, hoặc đóng khi chưa có gì để đóng
      }
    }
  }
  return stack.isEmpty; // 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ụ (((((().

Mẹo

Mẫu số chung: bất cứ khi nào bài toán cần nhớ “cái gần nhất, chưa xử lý xong” để đối chiếu về sau (ngoặc, thẻ HTML lồng nhau, dấu ngoặc trong biểu thức toán học…), hãy nghĩ đến stack.