Stack là gì và nó được dùng để làm gì?

Question

Accepted Answer

**Stack** là một collection **LIFO** (Last-In, First-Out — vào sau, ra trước): phần tử được push vào cuối cùng là phần tử đầu tiên được pop ra. Bạn chỉ bao giờ chạm vào **đỉnh (top)**.

## Các thao tác

```text
push(3)   push(7)   pop()->7   peek()->3
 [ 3 ]     [ 7 ]      [ 3 ]      [ 3 ]
           [ 3 ]                 top
            top
```

## Ví dụ

```python
stack = []
stack.append('a')   # push
stack.append('b')   # push
top = stack[-1]     # peek -> 'b'
stack.pop()         # pop  -> 'b'
```

Tất cả các thao tác đều là **O(1)** khi được hiện thực bằng dynamic array hoặc linked list.

| Thao tác | Thời gian |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## Các ứng dụng phổ biến

- **Call stack của hàm** — theo dõi các lời gọi đang hoạt động và biến cục bộ.
- **Undo/redo** — push mỗi hành động; pop để hoàn tác.
- **Tính toán biểu thức / phân tích cú pháp** — khớp ngoặc, chuyển trung tố (infix) sang hậu tố (postfix).
- **Backtracking & DFS** — nhớ nơi cần quay lại.

## Tại sao điều này quan trọng

Stack mô hình hóa "làm việc gần đây nhất trước," điều này xuất hiện ở khắp nơi từ đệ quy đến nút back của trình duyệt.

Nhận ra một mẫu LIFO lập tức gợi ý dùng stack, thường biến một bài toán rối rắm thành vài dòng push/pop gọn gàng.