Ngăn xếp và hàng đợi: LIFO, FIFO và lựa chọn cấu trúc dữ liệu

📚 Thứ tự lấy ra quyết định hành vi

Ngăn xếp dùng LIFO: phần tử thêm sau được lấy trước. Các thao tác cơ bản là push vào đỉnh, pop khỏi đỉnh và peek xem đỉnh. Hàng đợi dùng FIFO: phần tử vào trước được lấy trước, với enqueue ở cuối và dequeue ở đầu.

Một ngăn xếp dọc có thao tác push và pop cùng ở đỉnh, bên cạnh hàng đợi ngang có enqueue ở cuối và dequeue ở đầu — Danh sách hoặc mảng chỉ là cách cài đặt; quy tắc thứ tự trừu tượng mới xác định stack hay queue.

Ứng dụng

Stack: hoàn tác thao tác, kiểm tra dấu ngoặc, ngăn xếp lời gọi, duyệt sâu.
Queue: xử lí yêu cầu theo lượt, hàng đợi tác vụ, duyệt rộng.

Biên và độ phức tạp

Pop hoặc dequeue khi rỗng gây underflow và cần được kiểm tra. Cài đặt queue bằng mảng mà xóa phần tử đầu rồi dồn toàn bộ có thể tốn O(n); dùng chỉ số đầu–cuối hoặc hàng đợi vòng giúp thao tác trung bình/điển hình O(1).

⚠️ FIFO không tự bảo đảm công bằng tuyệt đối

Ưu tiên, hủy tác vụ hoặc nhiều hàng đợi có thể thay đổi thứ tự. Mô hình phải phù hợp yêu cầu hệ thống thay vì mặc định một cấu trúc giải mọi bài toán.

📚 Căn cứ biên soạn

Chương trình GDPT 2018.
Mạch kiến thức Kết nối tri thức với cuộc sống lớp 11 và Quyết định 3588/QĐ-BGDĐT.
Nội dung biên soạn độc lập, chú trọng điều kiện áp dụng và giới hạn của chỉ số.

📚 Lý thuyết trọng tâm

Mục tiêu: Mô phỏng push–pop và enqueue–dequeue, nhận diện underflow và chọn cấu trúc theo thứ tự xử lí thay vì hình thức cài đặt.. Khi học Ngăn xếp và hàng đợi: LIFO, FIFO và lựa chọn cấu trúc dữ liệu, hãy xác định khái niệm, điều kiện áp dụng và mối liên hệ giữa các dữ kiện; không chỉ ghi nhớ kết luận.

🧭 Ví dụ có hướng dẫn

Chọn một tình huống điển hình của bài. Bước 1: ghi dữ kiện và câu hỏi cần giải quyết. Bước 2: chọn khái niệm hoặc quy tắc phù hợp. Bước 3: giải thích từng bước và kiểm tra kết quả với điều kiện ban đầu. Nếu đổi một dữ kiện, hãy dự đoán kết quả thay đổi thế nào.

✍️ Luyện tập

Tóm tắt bài bằng ba ý: khái niệm, điều kiện và kết luận.
Tự tạo một ví dụ đúng và một phản ví dụ; chỉ ra điểm quyết định.
Giải lại ví dụ khi thay đổi một dữ kiện, sau đó nêu cách kiểm chứng.

Checklist tự đánh giá

Tôi giải thích được “vì sao”, không chỉ nêu đáp án.
Tôi nhận ra trường hợp không áp dụng được quy tắc.
Tôi kiểm tra được đơn vị, bằng chứng hoặc tính hợp lí của kết luận.