Chuyển tới nội dung chính

Ngăn xếp (Stack)

Bạn sẽ học được gì

Ngăn xếp (stack) là cấu trúc "vào sau ra trước" (LIFO). Đơn giản nhưng có mặt khắp nơi: nút Undo, ngăn xếp lời gọi hàm, duyệt DFS, kiểm tra ngoặc. Mọi thao tác đều O(1).

1. Trực quan: chồng đĩa​

Stack giống chồng đĩa: bạn chỉ thêm/lấy ở đỉnh. Đĩa đặt sau cùng lại là đĩa được lấy đầu tiên. Đó là LIFO — Last In, First Out (vào sau, ra trước).

        push 30 ▼        ▲ pop (lấy 30 ra trước)
       ┌────────┐
       │   30   │ ← đỉnh (top)
       ├────────┤
       │   20   │
       ├────────┤
       │   10   │ ← đáy
       └────────┘

2. Ba thao tác (đều O(1))​

Thao tácÝ nghĩaĐộ phức tạp
push(x)thêm x lên đỉnhO(1)
pop()lấy & bỏ phần tử đỉnhO(1)
peek()xem đỉnh, không lấy raO(1)

Vì chỉ động vào đỉnh, không phải dịch gì → tất cả O(1).

3. Chạy debug: push rồi pop​

Bước qua để thấy LIFO: phần tử vào sau (3) ra trước.

🐞 push 1, 2, 3 rồi popBước 1/5
1stack = []
2stack.append(1)    # push 1
3stack.append(2)    # push 2
4stack.append(3)    # push 3
5x = stack.pop()    # pop -> lay dinh
Biến tại bước này
stack[]
👉 Stack rỗng.

4. Cài đặt: dùng mảng động là đủ​

Trong Python, list với append/pop (cuối) chính là stack — cả hai O(1):

Đang tải trình chạy code…

Lưu ý: dùng append/pop ở CUỐI mảng (O(1)). Đừng dùng pop(0) (đầu, O(n)) cho stack.

5. Vì sao stack quan trọng?​

Stack mô hình hoá "việc đang làm dở, quay lại sau". Máy tính dùng nó cho ngăn xếp lời gọi hàm (nhớ bài 1.3.2 — mỗi lời gọi push một khung). Đệ quy thực chất là một stack ẩn. Bạn sẽ gặp lại stack ở DFS, kiểm tra ngoặc, undo... (bài 2.3.4).

6. Mẫu nhận diện​

  • "Hoàn tác (undo)", "quay lui", "khớp cặp gần nhất", "đảo ngược" → nghĩ tới stack.
  • Cần xử lý phần tử mới nhất trước → LIFO → stack.
  • Đệ quy ↔ stack: bài đệ quy thường viết lại được bằng vòng lặp + stack thủ công.

7. 🎮 Trò chơi: Hiểu stack​

🎮 Hiểu stack (LIFO)Câu 1/4· Điểm 0· 🔥 0

LIFO: vào sau ra trước. Mọi thao tác ở đỉnh, O(1).

Stack hoạt động theo nguyên tắc?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. LIFO nghĩa là gì?
2. Cấu trúc nào của máy tính chính là một stack?
3. Trong Python, nên cài stack bằng?

9. Hoàn thành​

…

☑️ Tiếp theo: 2.3.2 — Hàng đợi (Queue) (FIFO — ngược với stack).