03. Stacks (Ngăn xếp)
🎯 Mục tiêu học tập
- Hiểu nguyên lý LIFO (Last In First Out)
- Cài đặt Stack bằng Array và Linked List
- Áp dụng Stack vào bài toán thực tế
- Phân tích độ phức tạp các thao tác
📚 Lý thuyết
Stack là gì?
Định nghĩa: Cấu trúc dữ liệu tuyến tính hoạt động theo nguyên lý LIFO (Last In First Out).
Hình ảnh:
↓ PUSH ↑ POP
┌─────────────────────┐
│ TOP │ ← Chỉ thao tác ở đây
├─────────────────────┤
│ │
├─────────────────────┤
│ │
├─────────────────────┤
│ │
└─────────────────────┘
Đặc điểm chính:
- Chỉ thao tác ở đỉnh (top)
- Phần tử vào sau sẽ ra trước
- Truy cập tuần tự (không random access)
- Kích thước có thể cố định hoặc động
🔧 Các thao tác cơ bản
1. push(item): Thêm phần tử vào đỉnh
- Độ phức tạp: O(1)
- Kiểm tra stack overflow (nếu array)
2. pop(): Lấy và xóa phần tử ở đỉnh
- Độ phức tạp: O(1)
- Kiểm tra stack underflow (stack rỗng)
3. peek()/top(): Xem phần tử ở đỉnh (không xóa)
- Độ phức tạp: O(1)
- Không thay đổi stack
4. isEmpty(): Kiểm tra stack rỗng
- Độ phức tạp: O(1)
5. size(): Đếm số phần tử
- Độ phức tạp: O(1)
6. isFull(): Kiểm tra stack đầy (với array)
- Độ phức tạp: O(1)
🏗️ Cách cài đặt
1. Array-based Stack
class ArrayStack {
private int[] stack;
private int top;
private int maxSize;
// Ưu điểm: Memory liên tiếp, cache-friendly
// Nhược điểm: Kích thước cố định
}
2. Linked List-based Stack
class LinkedStack {
private Node top;
class Node {
int data;
Node next;
}
// Ưu điểm: Kích thước động
// Nhược điểm: Memory overhead cho pointers
}
📊 So sánh Array vs Linked List Implementation
| Tiêu chí | Array Stack | Linked List Stack |
|---|---|---|
| Memory | Cố định, liên tiếp | Động, rải rác |
| Performance | Nhanh hơn | Chậm hơn (pointer overhead) |
| Memory Usage | Ít hơn | Nhiều hơn |
| Overflow | Có thể xảy ra | Không (chỉ hạn chế bởi heap) |
| Implementation | Đơn giản hơn | Phức tạp hơn |
🎯 Ứng dụng thực tế
1. Function Call Stack
// Call stack quản lý việc gọi hàm
void funcA() {
funcB(); // A được push vào stack
}
void funcB() {
funcC(); // B được push vào stack
}
// Khi return: C pop → B pop → A pop
2. Expression Evaluation
- Infix to Postfix conversion
- Postfix expression evaluation
- Balanced parentheses checking
3. Undo Operations
// Text editor, Photoshop, etc.
Stack<Command> undoStack = new Stack<>();
// Mỗi action được push vào stack
// Undo = pop và execute reverse command
4. Browser History
- Back button = pop from history stack
- New page = push to history stack
5. Memory Management
- Call stack trong programming languages
- Local variables scope
🧮 Bài toán kinh điển
1. Balanced Parentheses
// Input: "((()))" → Valid
// Input: "(()" → Invalid
// Dùng stack để track opening brackets
2. Infix to Postfix
// Input: "A + B * C"
// Output: "A B C * +"
// Dùng stack để manage operators
3. Next Greater Element
// Input: [4, 5, 2, 25]
// Output: [5, 25, 25, -1]
// Dùng stack để track pending elements
4. Valid Parentheses Combinations
// Generate all valid parentheses với n cặp
// n=2: ["(())", "()()"]
// Dùng stack-based backtracking
🔍 Các biến thể nâng cao
1. Min Stack
- Hỗ trợ getMin() trong O(1)
- Dùng auxiliary stack hoặc modified node
2. Two Stacks in One Array
- Chia array thành 2 phần
- Tối ưu hóa memory usage
3. Stack with Get Middle
- Hỗ trợ getMiddle() trong O(1)
- Dùng doubly linked list
📋 Bài tập thực hành
Cơ bản:
- Cài đặt Stack bằng Array
- Cài đặt Stack bằng Linked List
- Check balanced parentheses
- Reverse string using stack
Trung bình:
- Infix to Postfix conversion
- Evaluate postfix expression
- Next Greater Element
- Valid parentheses generation
Nâng cao:
- Min Stack implementation
- Largest rectangle in histogram
- Trapping rain water
- Basic calculator
⚠️ Lỗi thường gặp
1. Stack Overflow
// Với array-based stack
if (top >= maxSize - 1) {
throw new StackOverflowException();
}
2. Stack Underflow
// Pop từ empty stack
if (isEmpty()) {
throw new StackUnderflowException();
}
3. Memory Leaks (với Linked List)
// Không set next = null khi pop
public int pop() {
int data = top.data;
Node temp = top;
top = top.next;
temp.next = null; // Tránh memory leak
return data;
}
🚀 Chuẩn bị code
mkdir 03-stacks
cd 03-stacks
# Files sẽ được tạo:
# - ArrayStack.java (Array implementation)
# - LinkedStack.java (Linked List implementation)
# - StackApplications.java (Common applications)
# - StackProblems.java (Practice problems)