04. Queues (Hàng đợi)
🎯 Mục tiêu học tập
- Hiểu nguyên lý FIFO (First In First Out)
- Cài đặt Queue bằng nhiều cách khác nhau
- Phân biệt các loại Queue và ứng dụng
- Áp dụng Queue vào các bài toán thực tế
📚 Lý thuyết
Queue là gì?
Định nghĩa: Cấu trúc dữ liệu tuyến tính hoạt động theo nguyên lý FIFO (First In First Out).
Hình ảnh:
ENQUEUE → ┌─────┬─────┬─────┬─────┐ → DEQUEUE
│ A │ B │ C │ D │
└─────┴─────┴─────┴─────┘
REAR FRONT
(Tail/Back) (Head)
Đặc điểm chính:
- Thêm ở cuối (rear/tail), lấy ở đầu (front/head)
- Phần tử vào trước sẽ ra trước
- Không truy cập ngẫu nhiên
- Phù hợp cho scheduling và buffering
🔧 Các thao tác cơ bản
1. enqueue(item): Thêm phần tử vào cuối
- Độ phức tạp: O(1)
- Tăng rear pointer
2. dequeue(): Lấy và xóa phần tử ở đầu
- Độ phức tạp: O(1)
- Tăng front pointer
3. front()/peek(): Xem phần tử đầu (không xóa)
- Độ phức tạp: O(1)
4. rear()/back(): Xem phần tử cuối
- Độ phức tạp: O(1)
5. isEmpty(): Kiểm tra queue rỗng
- Độ phức tạp: O(1)
6. size(): Đếm số phần tử
- Độ phức tạp: O(1)
7. isFull(): Kiểm tra queue đầy (với array)
- Độ phức tạp: O(1)
🏗️ Cách cài đặt
1. Array-based Queue (Simple)
class SimpleQueue {
private int[] queue;
private int front, rear, size;
// Vấn đề: Lãng phí không gian khi dequeue
}
2. Circular Array Queue
class CircularQueue {
private int[] queue;
private int front, rear, size, capacity;
// rear = (rear + 1) % capacity
// Tối ưu hóa không gian
}
3. Linked List Queue
class LinkedQueue {
private Node front, rear;
class Node {
int data;
Node next;
}
// Kích thước động, no overflow
}
4. Two Stacks Queue
class StackQueue {
private Stack<Integer> stack1, stack2;
// Enqueue: push to stack1
// Dequeue: pop from stack2 (transfer if needed)
}
📊 So sánh các implementation
| Cách cài đặt | Memory | Enqueue | Dequeue | Space Efficiency |
|---|---|---|---|---|
| Simple Array | O(n) | O(1) | O(1) | Kém (lãng phí) |
| Circular Array | O(n) | O(1) | O(1) | Tốt |
| Linked List | O(n) | O(1) | O(1) | Tốt (overhead pointer) |
| Two Stacks | O(n) | O(1) | O(1) amortized | Tốt |
🔍 Các loại Queue đặc biệt
1. Priority Queue
// Phần tử có priority cao ra trước
// Implementation: Heap, BST, Sorted Array
PriorityQueue<Integer> pq = new PriorityQueue<>();
2. Deque (Double-ended Queue)
// Thêm/xóa ở cả hai đầu
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1); // Thêm đầu
deque.addLast(2); // Thêm cuối
deque.removeFirst(); // Xóa đầu
deque.removeLast(); // Xóa cuối
3. Circular Queue
┌─────┬─────┬─────┬─────┐
│ 1 │ 2 │ │ 4 │
└─────┴─────┴─────┴─────┘
↑ ↑
REAR FRONT
🎯 Ứng dụng thực tế
1. Task Scheduling
// CPU scheduling, print queue
Queue<Task> taskQueue = new LinkedList<>();
// Tasks được xử lý theo thứ tự FIFO
2. Breadth-First Search (BFS)
// Duyệt graph/tree theo chiều rộng
Queue<Node> queue = new LinkedList<>();
queue.offer(startNode);
while (!queue.isEmpty()) {
Node current = queue.poll();
// Process current
// Add neighbors to queue
}
3. Buffer cho I/O Operations
// Keyboard buffer, network packet queue
// Producer-Consumer pattern
4. Cache Implementation
// LRU Cache sử dụng queue để track access order
5. Simulation Systems
// Bank queue, traffic light, call center
// Modeling real-world waiting systems
🧮 Bài toán kinh điển
1. Implement Queue using Stacks
// Sử dụng 2 stacks để tạo queue
// Stack1 cho enqueue, Stack2 cho dequeue
2. Implement Stack using Queues
// Sử dụng 1 hoặc 2 queues để tạo stack
3. First Non-repeating Character
// Stream of characters, tìm char đầu tiên không lặp
// Dùng queue + frequency map
4. Sliding Window Maximum
// Array và window size k
// Tìm max trong mỗi window
// Dùng Deque để tối ưu
5. Generate Binary Numbers
// In binary từ 1 đến n
// 1, 10, 11, 100, 101, 110, 111, 1000
// Dùng queue để generate pattern
🔍 Biến thể nâng cao
1. Multi-level Queue
- Nhiều queue với priority khác nhau
- Real-time systems, OS scheduling
2. Circular Buffer
- Fixed size circular queue
- Audio/video streaming
3. Blocking Queue
- Thread-safe queue
- Producer-Consumer pattern in multithreading
📋 Bài tập thực hành
Cơ bản:
- Cài đặt Queue bằng Array (simple + circular)
- Cài đặt Queue bằng Linked List
- Implement Queue using 2 Stacks
- Reverse first K elements of Queue
Trung bình:
- Generate binary numbers from 1 to n
- First non-repeating character in stream
- Implement Deque
- Level order traversal of binary tree
Nâng cao:
- Sliding window maximum
- Design circular deque
- Shortest path in unweighted graph (BFS)
- Implement LRU cache
⚠️ Lỗi thường gặp
1. Queue Overflow (Array)
// Kiểm tra trước khi enqueue
if (size == capacity) {
throw new QueueOverflowException();
}
2. Queue Underflow
// Kiểm tra trước khi dequeue
if (isEmpty()) {
throw new QueueUnderflowException();
}
3. Sai logic Circular Queue
// Sai: rear = rear + 1
// Đúng: rear = (rear + 1) % capacity
4. Memory leak (Linked List)
// Đặt next = null khi dequeue
public int dequeue() {
int data = front.data;
Node temp = front;
front = front.next;
temp.next = null; // Tránh memory leak
return data;
}
🚀 Chuẩn bị code
mkdir 04-queues
cd 04-queues
# Files sẽ được tạo:
# - ArrayQueue.java (Array implementation)
# - CircularQueue.java (Circular array)
# - LinkedQueue.java (Linked list implementation)
# - StackQueue.java (Using stacks)
# - QueueApplications.java (BFS, scheduling, etc.)
# - QueueProblems.java (Practice problems)