Algorithms & Applications
Trang chủ / Module 2
🧱 Module 2 / 14 · 1 tuần

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).

ArrayLinked ListStack/Queue
📌 Vì sao module này quan trọng

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ácArrayLinked List
Truy cập theo indexO(1) — địa chỉ bộ nhớ liên tục, tính trực tiếp đượcO(n) — phải duyệt từ đầu
Thêm/xoá ở đầuO(n) — phải dịch chuyển toàn bộ phần tử còn lạiO(1) — chỉ đổi con trỏ
Thêm/xoá ở giữa (đã có vị trí)O(n) — dịch chuyển phần tử phía sauO(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ệuCấu trúc phù hợp
Truy cập ngẫu nhiên theo index thường xuyênArray
Insert/delete liên tục ở đầu danh sáchLinked 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

Triển khai Undo/Redo và Kiểm tra dấu ngoặc

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

✅ 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ể