Ngăn xếp — Stack
Ngăn xếp (stack) là cấu trúc "vào sau ra trước" (LIFO): phần tử thêm vào sau cùng sẽ được lấy ra đầu tiên. Mọi thao tác push, pop và xem đỉnh đều chỉ đụng tới đỉnh nên đạt O(1).
Ngăn xếp hợp khi bài cần ghi nhớ thứ tự "mở" để khớp với "đóng" (kiểm tra dấu ngoặc cân bằng), lưu lịch sử để hoàn tác, hay so phần tử hiện tại với phần tử gần nhất chưa xử lý (monotonic stack). Đệ quy thực chất cũng chạy trên một ngăn xếp ngầm của hệ thống.
Như chồng đĩa trong bếp — đĩa bỏ vào sau cùng là đĩa lấy ra đầu tiên (LIFO).
- Muốn lấy đĩa dưới đáy phải nhấc hết đĩa trên ra trước.
- Mỗi thao tác push/pop chỉ đụng tới đỉnh chồng.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Ngăn xếp
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| khớp cặp mở-đóng | Ngoặc, thẻ HTML — đẩy khi mở, lấy ra khi đóng |
| phần tử lớn/nhỏ kế tiếp | Monotonic stack giữ thứ tự tăng/giảm |
| undo / hoàn tác | Cái mới nhất phải xử lý trước (LIFO) |
Khi nào dùng
4 tình huống điển hình cần nghĩ đến chủ đề này
Cần ghi nhớ thứ tự "mở" để khớp với "đóng" (ngoặc, thẻ HTML)
Cần undo/quay lại trạng thái gần nhất
Cần so phần tử hiện tại với phần tử gần nhất chưa xử lý (monotonic stack)
Mô phỏng đệ quy bằng vòng lặp + ngăn xếp tường minh
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Cần FIFO (vào trước ra trước): dùng Queue, không phải Stack
Cần truy cập phần tử bất kỳ vị trí (random access): Stack chỉ thao tác đỉnh
Cần duy trì thứ tự xuất hiện gốc khi xử lý: cân nhắc dùng Queue hoặc duyệt mảng trực tiếp
Hình minh hoạ
Sơ đồ thể hiện cách giải của chủ đề này.
Vào sau ra trước (LIFO): chỉ thêm/lấy ở đỉnh. push đẩy phần tử lên đỉnh, pop lấy phần tử ở đỉnh — đều O(1).
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function stackPattern(items: T[]): R {
const stack: T[] = []
for (const item of items) {
// Khớp / gộp với đỉnh khi thoả điều kiện
while (stack.length && shouldPop(stack[stack.length - 1], item)) {
stack.pop()
}
stack.push(item) // hoặc push giá trị suy ra từ item
}
return assembleResult(stack)
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
push() và pop() đều O(1) — chỉ thao tác ở đỉnh
Trong JS dùng mảng: push() để thêm, pop() để lấy đỉnh
monotonic stack giữ phần tử tăng/giảm dần, mỗi phần tử vào/ra tối đa 1 lần → O(n)
Lỗi thường gặp
Quên check ngăn xếp rỗng trước khi pop → undefined
Khớp sai cặp ngoặc vì so với phần tử dưới đáy thay vì đỉnh
Quên xử lý phần tử còn sót trong ngăn xếp sau vòng lặp
Độ phức tạp
push/pop/peek O(1), duyệt 1 lần O(n)Bài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay