99 Ngày Java — Ngày 36: Queue, Deque & Stack

Ba tuần Collection sắp tròn bộ: List giữ thứ tự tự do (32), Set gác cửa duy nhất (33), Map tra theo key (34–35) — còn đúng một nhánh: Queue, cấu trúc có kỷ luật ra vào. Hôm nay ta học hai kỷ luật đối nhau — FIFO xếp hàng mua phở và LIFO chồng đĩa úp ngược — rồi gặp ArrayDeque, mảng vòng một mình đóng cả hai vai (và bản án cho class Stack đồ cổ), cùng PriorityQueue — hàng đợi phòng cấp cứu chạy trên binary heap, kèm cái bẫy phỏng vấn "in ra không sắp xếp" và bài toán top-K kinh điển.

Queue — kỷ luật FIFO và hai bộ method

// Nhánh cuối của cây Collection (Ngày 31): Queue — cấu trúc CÓ KỶ LUẬT
// List cho index tự do, Set lo duy nhất — Queue chỉ hỏi: AI ĐẾN LƯỢT?

// FIFO (First-In-First-Out) — xếp hàng mua phở: đến trước, ăn trước
Queue<String> hangCho = new ArrayDeque<>();
hangCho.offer("An");  hangCho.offer("Bình");  hangCho.offer("Chi");
hangCho.poll();   // "An"  — người ĐẦU hàng ra trước
hangCho.peek();   // "Bình" — xem đầu hàng, KHÔNG lấy ra

// Queue có HAI bộ method cùng chức năng — khác cách báo thất bại:
// ┌──────────┬───────────────┬──────────────────────┐
// │          │ ném exception │ trả giá trị đặc biệt │
// ├──────────┼───────────────┼──────────────────────┤
// │ thêm     │ add(e)        │ offer(e) → false     │
// │ lấy ra   │ remove()      │ poll()   → null      │
// │ xem đầu  │ element()     │ peek()   → null      │
// └──────────┴───────────────┴──────────────────────┘
// Queue thường: dùng bộ offer/poll/peek — hàng rỗng là chuyện thường,
// không phải tình huống bất thường đáng ném exception

// Vì poll/peek trả null làm tín hiệu → queue CẤM chứa null (mập mờ ngay!)
// LƯU Ý quen thuộc: đây là interface — ArrayDeque, LinkedList,
// PriorityQueue đều cài nó, mỗi loại một lời hứa riêng

• Queue thu hẹp quyền lực có chủ đích: không index, không chen ngang — chỉ vào đuôi, ra đầu. Chính sự gò bó đó làm code kể được chuyện: thấy Queue là biết dữ liệu chảy theo lượt.

• Hai bộ method là câu hỏi phỏng vấn ưa thích: add/remove/element ném exception, offer/poll/peek trả false/null — queue thường dùng bộ sau, vì hàng rỗng là chuyện thường ngày chứ không phải tai nạn.

• Hệ quả ít ai để ý: vì poll/peek lấy null làm tín hiệu rỗng nên queue cấm chứa null — nhét null vào ArrayDeque là NullPointerException ngay.

Deque & ArrayDeque — một mình hai vai

// Deque (Double-Ended Queue, đọc "đéc") — hàng đợi HAI ĐẦU
// Thêm/lấy được ở CẢ hai phía → một mình đóng HAI vai:

Deque<String> deque = new ArrayDeque<>();
deque.offerLast("cuối");   deque.offerFirst("đầu");   // thêm hai đầu
deque.pollFirst();          deque.pollLast();           // lấy hai đầu

// VAI 1 — Queue (FIFO): offer đuôi + poll đầu  (như trang trước)
// VAI 2 — Stack (LIFO): push/pop CÙNG một đầu — chồng đĩa: úp sau, nhấc trước
Deque<String> lichSu = new ArrayDeque<>();   // undo của editor
lichSu.push("gõ chữ A");
lichSu.push("xóa dòng 2");
lichSu.push("dán khối");
lichSu.pop();    // "dán khối"  — hành động MỚI NHẤT undo trước
lichSu.peek();   // "xóa dòng 2" — lượt undo kế tiếp

// Khoan — Java có sẵn class Stack mà? CÓ, và ĐỪNG DÙNG:
// class Stack kế thừa Vector (đồ cổ 1995): mọi method synchronized (chậm vô cớ),
// và vì là Vector nên... get(3) — CHỌC GIỮA chồng đĩa được?! Vỡ hợp đồng LIFO
// Javadoc của chính Stack khuyên: "nên dùng ArrayDeque" — án tự tuyên

// ArrayDeque bên trong: MẢNG VÒNG (circular array) — hai con trỏ head/tail
// đuổi nhau quanh mảng, đầy thì gấp đôi (quy luật Ngày 32 quay lại)
// → thêm/lấy hai đầu đều O(1), không node object rác như LinkedList
// LinkedList cũng cài Deque — nhưng thua ArrayDeque gần như mọi bàn (Ngày 32)

• Deque mở cả hai đầu nên gói được cả hai kỷ luật: offer đuôi + poll đầu = Queue, push + pop cùng một đầu = Stack — undo của editor, back của trình duyệt, call stack đều là chồng đĩa LIFO.

• Bản án cho class Stack cũ: kế thừa Vector 1995 nên mọi method synchronized (trả phí đồng bộ vô cớ) và... get(3) chọc giữa chồng — vỡ hợp đồng LIFO; Javadoc của chính nó khuyên dùng ArrayDeque.

• Bên trong ArrayDeque là mảng vòng: hai con trỏ head/tail đuổi nhau, đầy thì gấp đôi (quy luật Ngày 32 quay lại) — hai đầu đều O(1), không xả node rác như LinkedList.

PriorityQueue — hàng đợi phòng cấp cứu

// PriorityQueue — hàng đợi KHÔNG xếp theo lượt, xếp theo ĐỘ ƯU TIÊN
// Phòng cấp cứu: không phải ai đến trước khám trước — ai NẶNG nhất khám trước

record BenhNhan(String ten, int doNang) {}   // doNang: càng nhỏ càng nặng

PriorityQueue<BenhNhan> capCuu = new PriorityQueue<>(
    Comparator.comparingInt(BenhNhan::doNang));   // Comparator quyết định ưu tiên

capCuu.offer(new BenhNhan("An",   3));
capCuu.offer(new BenhNhan("Bình", 1));   // nặng nhất
capCuu.offer(new BenhNhan("Chi",  2));
capCuu.poll();   // Bình (1) — LUÔN ra phần tử ưu tiên cao nhất
capCuu.poll();   // Chi  (2)

// Bên trong: BINARY HEAP trên mảng — cây nhị phân "cha luôn nhỏ hơn con"
// offer/poll: O(log n) (nổi lên/chìm xuống theo chiều cao cây)
// peek: O(1) — đỉnh heap luôn là phần tử nhỏ nhất

// ⚠️ BẪY PHỎNG VẤN: heap CHỈ hứa "đỉnh là nhỏ nhất" —
// duyệt/in PriorityQueue KHÔNG ra thứ tự sắp xếp!
System.out.println(capCuu);   // thứ tự mảng heap, KHÔNG phải thứ tự ưu tiên
// Muốn lấy lần lượt theo ưu tiên: poll() từng phần tử (mỗi lần O(log n))

// Kinh điển top-K: tìm 10 sản phẩm bán chạy nhất trong 10 triệu
// → giữ heap NGƯỢC (min-heap) kích thước 10, hơn đỉnh thì thay — O(n log 10)
// Nhanh hơn hẳn sort cả 10 triệu O(n log n)

• Đổi luật chơi: không theo lượt đến mà theo độ ưu tiên do Comparator (hoặc Comparable của phần tử) định nghĩa — poll luôn nhả phần tử ưu tiên cao nhất.

• Bên trong là binary heap trên mảng: cha luôn nhỏ hơn con — offer/poll O(log n) theo chiều cao cây, peek O(1). Heap chỉ hứa đúng một điều: đỉnh là nhỏ nhất.

• Nên mới có bẫy phỏng vấn: in hay duyệt PriorityQueue không ra thứ tự sắp xếp — muốn lấy theo ưu tiên phải poll từng phần tử. Và bài top-K kinh điển: heap nhỏ k phần tử quét n dòng — O(n log k), rẻ hơn hẳn sort cả đống.

BFS, DFS và bảng chọn cuối

// BFS — thuật toán "loang" kinh điển chạy trên Queue
// Tìm đường ngắn nhất trong mê cung/đồ thị: thăm theo TỪNG LỚP lan ra
Queue<Node> bfs = new ArrayDeque<>();
bfs.offer(batDau);
while (!bfs.isEmpty()) {
    Node hienTai = bfs.poll();              // lấy node lớp gần
    for (Node ke : hienTai.hangXom())
        if (chuaTham(ke)) bfs.offer(ke);    // hàng xóm vào CUỐI hàng
}
// Đổi Queue thành Deque + push/pop → thành DFS (đào sâu)! Cùng khung code
// — cấu trúc dữ liệu QUYẾT ĐỊNH thuật toán

// Bảng chọn nhánh Queue — mảnh cuối của bộ Collection:
// ┌───────────────┬─────────────┬───────────┬───────────────────────────┐
// │               │ Lời hứa     │ offer/poll│ Chọn khi                  │
// ├───────────────┼─────────────┼───────────┼───────────────────────────┤
// │ ArrayDeque    │ FIFO + LIFO │ O(1)      │ queue & stack — mặc định  │
// │ PriorityQueue │ ưu tiên cao │ O(log n)  │ top-K, scheduler, Dijkstra│
// │ LinkedList    │ FIFO        │ O(1)      │ (Ngày 32: hiếm khi thắng) │
// └───────────────┴─────────────┴───────────┴───────────────────────────┘
// class Stack cũ: ❌ bỏ — ArrayDeque thay trọn vai
// Đa luồng (producer–consumer): họ BlockingQueue — hẹn phần concurrency

// Khai báo bằng interface (điệp khúc quen): Queue<T> q = new ArrayDeque<>();
// Deque<T> s = new ArrayDeque<>();  — vai nào khai interface nấy, code tự kể chuyện

• Khung BFS chạy trên Queue: lấy node gần, đẩy hàng xóm vào đuôi — loang theo từng lớp, ra đường ngắn nhất; đổi Queue thành Stack là thành DFS — cùng khung code, cấu trúc dữ liệu quyết định thuật toán.

• Bảng chọn gọn: ArrayDeque mặc định cho cả queue lẫn stack, PriorityQueue khi có độ ưu tiên (top-K, scheduler, Dijkstra), LinkedList gần như không còn cửa (Ngày 32), class Stack bỏ hẳn.

• Đa luồng producer–consumer thuộc về họ BlockingQueue — hẹn phần concurrency; còn điệp khúc quen: khai báo bằng interface, Queue<T> hay Deque<T> tùy vai — code tự kể chuyện.

Bài tập nhỏ

• Mô phỏng quầy phở: 5 khách offer vào ArrayDeque, phục vụ bằng poll tới rỗng — in từng bước, rồi thay bằng push/pop xem thứ tự phục vụ lộn ngược thế nào.

• Viết trình kiểm tra ngoặc cân bằng "([{}])" bằng Deque làm stack — bài stack kinh điển nhất mọi thời.

• Xây undo/redo bằng hai stack: làm hành động → push stack undo; undo → pop sang stack redo; hành động mới → xóa sạch redo. Đúng cách mọi editor làm.

• Top-3 sản phẩm bán chạy từ mảng 1 triệu số bằng PriorityQueue min-heap kích thước 3 — in heap sau mỗi lần thay để thấy nó không hề sắp xếp.

• Chạy khung BFS trên lưới 5×5 có vật cản tìm đường ngắn nhất — rồi đổi poll đầu thành pop đuôi và xem DFS đào sâu khác BFS loang rộng ra sao.

Kết luận

Bộ Collection tròn bộ hôm nay: Queue thêm kỷ luật ra vào — FIFO với offer/poll/peek (hàng rỗng trả null, đừng ném exception), LIFO với push/pop trên ArrayDeque (class Stack cũ đã có án), và PriorityQueue xếp theo độ ưu tiên trên binary heap — nhớ nằm lòng: in ra không sắp xếp, top-K là đất diễn của nó. Ngày 37 ta trả món nợ treo từ Ngày 32: Iterator & duyệt collection — ConcurrentModificationException thật sự là gì, vì sao removeIf thoát nạn, và Iterable ăn khớp với for-each thế nào. Hẹn gặp lại!