Cấu trúc dữ liệu nền tảng: Array, Linked List, Stack, Queue
4 cấu trúc dữ liệu cơ bản nhất, đánh đổi giữa chúng, và ứng dụng thực tế (undo/redo, BFS, task queue).
Mọi cấu trúc dữ liệu phức tạp hơn (cây, đồ thị, hash table) đều được xây dựng từ 4 khối nền tảng này. Hiểu sâu đánh đổi của chúng — không chỉ "cách dùng" mà "vì sao thao tác này nhanh, thao tác kia chậm" — là điều kiện để chọn đúng cấu trúc dữ liệu cho từng bài toán thay vì dùng Array/List một cách mặc định.
🎯 Mục tiêu học tập
- So sánh đánh đổi giữa Array và Linked List cho từng loại thao tác
- Triển khai và ứng dụng Stack (LIFO) cho các bài toán thực tế
- Triển khai và ứng dụng Queue (FIFO) cho các bài toán thực tế
- Chọn đúng cấu trúc dữ liệu nền tảng theo pattern truy cập dữ liệu của bài toán
Array vs Linked List — đánh đổi cốt lõi
| Thao tác | Array | Linked List |
|---|---|---|
| Truy cập theo index | O(1) — địa chỉ bộ nhớ liên tục, tính trực tiếp được | O(n) — phải duyệt từ đầu |
| Thêm/xoá ở đầu | O(n) — phải dịch chuyển toàn bộ phần tử còn lại | O(1) — chỉ đổi con trỏ |
| Thêm/xoá ở giữa (đã có vị trí) | O(n) — dịch chuyển phần tử phía sau | O(1) — chỉ đổi 2 con trỏ liền kề |
| Locality bộ nhớ (cache-friendly) | Tốt — dữ liệu liên tục, tận dụng CPU cache hiệu quả | Kém — các node rải rác trong bộ nhớ |
Bài học thực tế quan trọng: dù Linked List có Big-O tốt hơn cho insert/delete, Array (hoặc Dynamic Array — ArrayList/Vector) vẫn là lựa chọn mặc định trong phần lớn ngôn ngữ hiện đại vì locality bộ nhớ tốt hơn thường thắng cả về hiệu năng thực tế lẫn sự đơn giản — Linked List chỉ thực sự đáng dùng khi có nhu cầu insert/delete liên tục ở đầu/giữa với số lượng phần tử rất lớn.
Stack (LIFO) — Last In, First Out
stack = []
stack.append(1) # push
stack.append(2)
stack.append(3)
stack.pop() # lấy ra 3 (phần tử vào sau cùng, ra trước tiên)
Ứng dụng thực tế phổ biến nhất: Undo/Redo (mỗi hành động push vào stack, undo là pop), Call Stack của chương trình (mỗi lời gọi hàm push 1 frame, return thì pop — giải thích trực tiếp vì sao đệ quy quá sâu gây "Stack Overflow"), kiểm tra dấu ngoặc cân bằng (mỗi dấu mở push, dấu đóng thì pop và so khớp), và Depth-First Search (Module 9) — có thể triển khai bằng đệ quy (dùng call stack có sẵn) hoặc bằng stack tường minh.
Queue (FIFO) — First In, First Out
from collections import deque
queue = deque()
queue.append(1) # enqueue
queue.append(2)
queue.append(3)
queue.popleft() # lấy ra 1 (phần tử vào trước tiên, ra trước tiên)
Ứng dụng thực tế: Breadth-First Search (Module 9 — duyệt đồ thị theo từng "lớp"), Task Queue/Job Queue (đúng mô hình Message Queue đã học ở khoá Architecture Module 8 — xử lý công việc theo đúng thứ tự đến), và Rate Limiting kiểu Sliding Window (giữ queue các timestamp request gần nhất, loại bỏ timestamp cũ hơn ngưỡng thời gian).
Priority Queue (khác Queue thường — phần tử ra theo độ ưu tiên, không theo thứ tự vào) sẽ được học sâu ở Module 5 cùng với Heap — cấu trúc dữ liệu triển khai Priority Queue hiệu quả nhất.
Chọn đúng cấu trúc dữ liệu nền tảng
| Nhu cầu truy cập dữ liệu | Cấu trúc phù hợp |
|---|---|
| Truy cập ngẫu nhiên theo index thường xuyên | Array |
| Insert/delete liên tục ở đầu danh sách | Linked List, hoặc deque |
| Xử lý theo thứ tự "gần nhất trước" (LIFO) | Stack |
| Xử lý theo thứ tự "đến trước, xử lý trước" (FIFO) | Queue |
🏋️ Bài tập thực hành
Viết 1 class TextEditor đơn giản hỗ trợ undo/redo bằng 2 Stack (1 cho undo, 1 cho redo). Viết hàm kiểm tra 1 chuỗi có dấu ngoặc ({[]}) cân bằng hay không bằng Stack. Viết hàm mô phỏng hàng đợi task đơn giản (enqueue/dequeue) và giải thích vì sao FIFO là lựa chọn đúng cho bài toán xử lý job theo thứ tự.
📚 Tài nguyên học tập
-
VisuAlgo — Linked List, Stack, QueueTrực quan hoá tương tác các cấu trúc dữ liệu cơ bảnTool
✅ Tự đánh giá hoàn thành
- So sánh đúng đánh đổi Array vs Linked List cho từng loại thao tác
- Triển khai được Stack và giải quyết 1 bài toán thực tế bằng nó
- Triển khai được Queue và giải quyết 1 bài toán thực tế bằng nó
- Chọn đúng cấu trúc dữ liệu nền tảng theo pattern truy cập của bài toán cụ thể