Queue

Đơn hàng đến trước phải được đóng gói trước. Stack lấy phần tử mới nhất, nên dùng cho đơn hàng thì khách đặt sớm nhất lại chờ lâu nhất. Queue làm ngược lại: ai đến trước được phục vụ trước.

Khái niệm

🎟️ Queue (hàng đợi): danh sách thêm vào ở cuối và lấy ra ở đầu, phần tử vào trước được lấy ra trước (FIFO: first in, first out).

Ví dụ

// Main.java
void main() {
    var orders = new ArrayDeque<String>();
    orders.offer("DH1");
    orders.offer("DH2");
    orders.offer("DH3");

    System.out.println(orders.poll());   // DH1
    System.out.println(orders.peek());   // DH2
    System.out.println(orders.size());   // 2
}

• offer xếp đơn vào cuối hàng, poll lấy đơn ở đầu hàng.
• DH1 vào trước nên ra trước. peek thấy DH2 đang đứng đầu.
• Cùng một ArrayDeque dùng được cho cả stack lẫn queue, tuỳ gọi method nào.

Bên trong Queue

Tự viết queue bằng ArrayList với add ở cuối và remove(0) ở đầu thì poll thành O(n), như bài Array và List bên trong. ArrayDeque không dời chỗ mà dùng array vòng tròn: giữ hai chỉ số đầu và cuối, lấy ra chỉ là tăng chỉ số đầu. Hết ô ở cuối array thì quay lại dùng các ô trống ở đầu.

Thử ngay

Xử lý đơn trong khi vẫn có đơn mới đến:

// Main.java
void main() {
    var orders = new ArrayDeque<String>();
    orders.offer("DH1");
    orders.offer("DH2");

    System.out.println("Đóng gói " + orders.poll());
    orders.offer("DH3");
    orders.offer("DH4");
    System.out.println("Đóng gói " + orders.poll());

    while (!orders.isEmpty()) {
        System.out.println("Còn chờ " + orders.poll());
    }
}

Đoán trước khi chạy: thứ tự các đơn được in ra là gì?

Đóng gói DH1
Đóng gói DH2
Còn chờ DH3
Còn chờ DH4

Lỗi hay gặp

Dùng ArrayList làm hàng đợi. remove(0) dời cả list mỗi lần lấy đơn, hàng dài thì chậm hẳn.

// SAI — mỗi lần lấy đơn là O(n)
List<String> orders = new ArrayList<>();
orders.add("DH1");
orders.add("DH2");
String next = orders.remove(0);

// ĐÚNG — poll là O(1)
var orders = new ArrayDeque<String>();
orders.offer("DH1");
orders.offer("DH2");
String next = orders.poll();

Khác pop của stack, poll khi hàng rỗng không ném exception mà trả về null, nên kiểm tra isEmpty() trước khi lấy.

Tóm tắt

• Queue thêm ở cuối, lấy ở đầu: vào trước ra trước (FIFO).
• poll, peek là O(1) nhờ array vòng tròn, offer là O(1) trung bình.
• Dùng cho đơn hàng chờ xử lý, và cho tìm kiếm theo chiều rộng (BFS) ở chương 5.
• Đừng dùng ArrayList với remove(0) làm hàng đợi.