Stack, queue, deque: LIFO, FIFO và ứng dụng

Nắm nguyên tắc LIFO của ngăn xếp và FIFO của hàng đợi, các thao tác chuẩn cùng độ phức tạp, qua hai ẩn dụ đời thực trong bài này.

DễCấu trúc dữ liệu ~45 phút

Ôn lại trước khi học

Ký hiệu Big-O và các lớp tăng trưởng

Giới thiệu

Bài này học ngăn xếp LIFO và hàng đợi FIFO. Bạn biết khi nào dùng cấu trúc nào.

Kiến thức cần nhớ

Stack — vào sau ra trước

Quy tắc LIFO: mới vào thì ra trước.
push thêm lên đỉnh, pop lấy khỏi đỉnh.
peek chỉ nhìn đỉnh, không gỡ.
Ví dụ đời thường: chồng đĩa, lấy từ trên cùng.
Mọi thao tác đều $O(1)$ .

Queue — vào trước ra trước

Quy tắc FIFO: đến trước phục vụ trước.
enqueue xếp vào cuối, dequeue ra ở đầu.
Ví dụ đời thường: hàng vé, ai đến trước mua trước.
Mọi thao tác chuẩn đều $O(1)$ .
Đừng cài queue bằng mảng chèn đầu vì bị $O(n)$ .

Deque và ứng dụng

Deque thêm bớt được ở cả hai đầu.
Dùng một đầu thì thành stack.
Dùng hai đầu thì thành queue.
Ví dụ đời thường: hàng người cho chen hai đầu.
Ứng dụng: undo, lịch sử trình duyệt, BFS, DFS.

Tiêu chí	Stack	Queue
Quy tắc	LIFO	FIFO
Thao tác	push, pop, peek	enqueue, dequeue
Chi phí	$O(1)$	$O(1)$
Ví dụ dùng	Undo, DFS	Hàng in, BFS

Ví dụ

Input: push Đỏ rồi Xanh, pop 1 lần. Output: lấy ra Xanh, còn Đỏ.
Giải thích: phần tử vào sau ra trước đúng LIFO.

stack = []  # dùng list làm stack
stack.append("Do")  # push lên đỉnh
top = stack.pop()  # pop khỏi đỉnh

💻 Bài tập

Ngôn ngữ: C hoặc C++ không dùng std::stack, std::queue, std::deque. Nộp vào day-004/.

Bài 1: Stack trên mảng động

Hàm	Việc phải làm	Độ phức tạp
`bool st_push(Stack *s, int x)`	Đẩy lên đỉnh. Đầy thì nhân đôi	$O(1)$ trung bình
`bool st_pop(Stack s, int out)`	Lấy đỉnh. Rỗng trả `false`	$O(1)$
`bool st_peek(const Stack s, int out)`	Xem đỉnh, không gỡ	$O(1)$
`bool st_empty(const Stack *s)` / `size_t st_size(...)`		$O(1)$

Ứng dụng: viết bool balanced(const char *s) kiểm tra ngoặc ()[]{} cân bằng.

"([]{})"      -> true
"([)]"        -> false
"((("         -> false
""            -> true
"a(b[c]d)e"   -> true   (bỏ qua ký tự khác ngoặc)

Bài 2: Queue bằng mảng vòng (ring buffer)

typedef struct { int *buf; size_t head, count, capacity; } Queue;

Hàm	Việc phải làm	Độ phức tạp
`bool q_enqueue(Queue *q, int x)`	Ghi vào `buf[(head + count) % capacity]`. Đầy thì nhân đôi và sắp lại thứ tự	$O(1)$ trung bình
`bool q_dequeue(Queue q, int out)`	Đọc `buf[head]`, `head = (head + 1) % capacity`	$O(1)$
`bool q_front(const Queue q, int out)`	Xem đầu	$O(1)$

Ràng buộc: không dịch mảng khi dequeue. Mọi thao tác $O(1)$ (trừ lần nhân đôi).

cap=4; enqueue 1,2,3; dequeue x2   -> ra 1, 2; head=2
enqueue 4, 5, 6                     -> quấn vòng, nội dung [3, 4, 5, 6]
enqueue 7                           -> đầy, nhân đôi thành cap=8, thứ tự vẫn 3,4,5,6,7
dequeue 5 lần                       -> ra 3,4,5,6,7; lần 6 trả false

Bài 3: Deque và bài toán cửa sổ trượt (nâng cao)

Viết deque trên ring buffer: push_front, push_back, pop_front, pop_back, front, back, đều $O(1)$ .
Dùng deque giải: cho mảng a và k, in giá trị lớn nhất của mỗi cửa sổ độ dài k. Yêu cầu $O(n)$ .

a = [1, 3, -1, -3, 5, 3, 6, 7], k = 3  -> [3, 3, 5, 5, 6, 7]
a = [9, 8, 7], k = 1                    -> [9, 8, 7]
a = [2, 2, 2, 2], k = 2                 -> [2, 2, 2]

Deque giữ chỉ số, giá trị giảm dần từ đầu tới cuối. Chỉ số ra khỏi cửa sổ thì bỏ ở đầu.

✅ Tiêu chí hoàn thành

Test mẫu cả 3 bài pass bằng assert.
Ring buffer đúng khi quấn vòng và khi nhân đôi lúc head != 0.
Sanitizer sạch.
Giải thích được vì sao queue bằng mảng "xóa đầu rồi dịch" là $O(n)$ .

❓ Câu hỏi ôn tập

LIFO khác FIFO ở điểm nào?
push, pop, enqueue, dequeue làm gì?
Vì sao mọi thao tác chuẩn đều $O(1)$ ?
undo dùng stack hay queue?

🌕 Bạn đã hoàn thành ngày 4. Làm hết bài tập phía trên rồi sang ngày tiếp theo.

Ngày 3

SOLID, Open-Closed và Dependency Inversion thực hành

Ngày 5

Dictionary, set và ý tưởng băm