Queue & Deque — FIFO scheduler, sliding window, và ArrayDeque thay LinkedList

Bạn ra ga mua vé tàu. Có 50 người xếp hàng — người đến trước được phục vụ trước. Không ai được chen ngang, không ai được phục vụ từ giữa hàng. Đây là FIFO: First In, First Out.

Cùng cơ chế đó chạy bên dưới rất nhiều hệ thống: ThreadPoolExecutor nhận task theo thứ tự, BFS duyệt đồ thị theo từng lớp, Kafka giữ event theo offset, máy in xử lý tài liệu theo thứ tự nộp, OS scheduler đưa process vào CPU theo ready queue. Queue không phải khái niệm trừu tượng — nó là thứ quyết định thứ tự phục vụ trong mọi hệ thống có nhiều request cạnh tranh.

Bài này phân biệt 4 biến thể queue trong Java (Queue, Deque, PriorityQueue, BlockingQueue), giải thích khi nào chọn ArrayDeque thay LinkedList, và trình bày pattern sliding window dùng monotonic deque để đạt O(n).

1. Analogy — Hàng đợi mua vé

Hình dung hàng người xếp tại quầy vé tàu:

• Người mới đến đứng vào cuối hàng (enqueue / offer).
• Người đứng đầu hàng được phục vụ và rời đi (dequeue / poll).
• Không ai được nhảy vào giữa hoặc bị gọi ngẫu nhiên.

Đây là FIFO — phần tử vào trước sẽ ra trước.

2. Bốn biến thể queue trong Java

Java cung cấp nhiều hơn một loại queue. Lựa chọn sai dẫn đến performance kém hoặc bug tinh vi:

Queue basic là trường hợp đơn giản nhất — bài này tập trung vào đây và Deque.

PriorityQueue dùng cấu trúc heap bên dưới — sẽ phân tích chi tiết ở Module 4 khi học về heap sort và Dijkstra.

BlockingQueue dùng trong concurrent programming — producer/consumer pattern, ThreadPoolExecutor task queue. Sẽ deep dive trong Java Concurrency course (JCIP Chapter 5).

3. Hai API của Queue — throw vs return-special

Java Queue interface cung cấp hai phiên bản cho mỗi thao tác cơ bản: một ném exception khi fail, một trả về giá trị đặc biệt. Hiểu sự khác biệt tránh NPE và NoSuchElementException bất ngờ trong production:

Rule thực tế: chọn một phong cách và nhất quán trong codebase. Production code thường ưa offer/poll/peek vì trả null an toàn hơn là throw — dễ kiểm tra if (result != null) hơn là bắt exception trong hot path. Chỉ dùng add/remove/element khi muốn fail nhanh và rõ ràng (contract violation là lỗi nghiêm trọng, không phải condition thông thường).

4. Implement Queue bằng linked list

Linked list là cấu trúc tự nhiên nhất để implement queue: enqueue thêm vào tail, dequeue lấy từ head — cả hai đều O(1) nếu giữ tham chiếu đến cả hai đầu.

public class MyQueue<T> {
    // Doubly linked node -- prev not needed for queue, but next is
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }

    private Node<T> head; // front -- dequeue from here
    private Node<T> tail; // back -- enqueue here
    private int size;

    // O(1): add new node at tail
    public void enqueue(T item) {
        Node<T> node = new Node<>(item);
        if (tail != null) tail.next = node;
        tail = node;
        if (head == null) head = node; // first element
        size++;
    }

    // O(1): remove node from head
    public T dequeue() {
        if (head == null) throw new IllegalStateException("Queue is empty");
        T item = head.data;
        head = head.next;
        if (head == null) tail = null; // queue is now empty
        size--;
        return item;
    }

    public T peek() {
        if (head == null) throw new IllegalStateException("Queue is empty");
        return head.data;
    }

    public boolean isEmpty() { return head == null; }
    public int size() { return size; }
}

Key detail: giữ cả head và tail pointer. Nếu chỉ giữ head, mỗi enqueue phải traverse đến cuối — O(n). Cross-link: cấu trúc Node và trade-off singly linked list đã phân tích ở bài 02 Module 2.

5. ArrayDeque internals — vì sao thay LinkedList

java.util.LinkedList implement cả List và Deque — nghe có vẻ tiện. Nhưng trong thực tế, ArrayDeque thắng đáng kể về throughput và memory. Hiểu cơ chế bên dưới giải thích tại sao.

5.1 Circular array backing

ArrayDeque dùng một circular array — array thông thường nhưng với head và tail index có thể "quay vòng". Khi tail đến cuối array, nó wrap around về index 0 thay vì làm array grow.

Circular array với capacity=8, head=5, tail=2:
Index:  0   1   2   3   4   5   6   7
        [D] [E] [ ] [ ] [ ] [A] [B] [C]
                 ^tail               ^head
Elements in queue order: A, B, C, D, E

addLast tăng tail: tail = (tail + 1) & (capacity - 1). pollFirst tăng head: head = (head + 1) & (capacity - 1).

Bit trick (index + 1) & (capacity - 1) thay cho (index + 1) % capacity — hoạt động vì capacity luôn là power of 2. Bit AND nhanh hơn modulo đáng kể trong tight loop. Cross-link: tại sao power-of-2 và cache layout quan trọng — bài 04 Module 1.

5.2 OpenJDK source — addFirst và addLast

// Trich tu OpenJDK 21 -- java.util.ArrayDeque
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    es[head = dec(head, es.length)] = e;
    if (head == tail)
        grow(1);
}

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    es[tail] = e;
    if (head == (tail = inc(tail, es.length)))
        grow(1);
}

// Circular increment: (i + 1) & (length - 1)
static final int inc(int i, int modulus) {
    if (++i >= modulus) i = 0;
    return i;
}

// Circular decrement: (i - 1) & (length - 1)
static final int dec(int i, int modulus) {
    if (--i < 0) i = modulus - 1;
    return i;
}

Lưu ý addFirst kiểm tra null ngay đầu — đây là lý do ArrayDeque không cho phép null elements (xem Pitfall section).

5.3 Grow và amortized O(1)

Khi backing array đầy (head == tail), grow() double capacity và copy toàn bộ array. Amortized O(1) — giống ArrayList.grow() ở bài 07 Module 1, nhưng circular array phức tạp hơn vì phải unwrap vòng tròn khi copy.

5.4 So sánh ArrayDeque vs LinkedList

Rule thực tế: luôn dùng ArrayDeque thay LinkedList cho queue/deque trong production Java, trừ khi cần random access (dùng ArrayList) hoặc cần null sentinel (thiết kế lại — dùng Optional).

6. Sliding window pattern — monotonic deque

Đây là ứng dụng nổi tiếng nhất của Deque trong competitive programming và system coding interview.

6.1 Bài toán

Sliding Window Maximum (LeetCode 239): Cho array nums kích thước n và window size k, trả về mảng max của từng window có size k.

Ví dụ: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3.

Window [1, 3, -1]  -> max = 3
Window [3, -1, -3] -> max = 3
Window [-1, -3, 5] -> max = 5
Window [-3, 5, 3]  -> max = 5
Window [5, 3, 6]   -> max = 6
Window [3, 6, 7]   -> max = 7

Naive: với mỗi trong n - k + 1 window, scan k phần tử → O(n*k). Với n = 100.000 và k = 10.000, đây là 1 tỷ phép tính — quá chậm.

6.2 Ý tưởng monotonic deque

Dùng Deque<Integer> lưu index (không phải value), duy trì tính chất: các index trong deque ứng với value giảm dần từ đầu đến cuối deque. Front của deque luôn là index của max trong window hiện tại.

Tại mỗi bước i:

1. Loại index cũ hơn window: nếu dq.peekFirst() <= i - k, pop front.
2. Duy trì giảm dần: pop back cho đến khi nums[dq.peekLast()] >= nums[i], rồi push i vào back.
3. Ghi kết quả: khi i >= k - 1, max của window là nums[dq.peekFirst()].

6.3 Code Java đầy đủ

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        // Step 1: remove indices that have fallen out of window
        while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
            dq.pollFirst();
        }
        // Step 2: remove from back while back value is smaller than nums[i]
        // (they can never be the max of any future window)
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
            dq.pollLast();
        }
        dq.offerLast(i);
        // Step 3: record max for current window (once first window is complete)
        if (i >= k - 1) {
            result[i - k + 1] = nums[dq.peekFirst()];
        }
    }
    return result;
}

6.4 Trace ví dụ

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

Output: [3, 3, 5, 5, 6, 7] — đúng.

6.5 Tại sao O(n)?

Mỗi index i được push vào deque đúng một lần và pop ra tối đa một lần (từ front hoặc back). Tổng số thao tác push + pop trên toàn bộ vòng lặp là 2n. Vòng lặp bên ngoài chạy n lần, hai vòng while bên trong không chạy thêm n lần — chúng chia sẻ budget 2n tổng cộng. Kết quả: O(n) time, O(k) space.

7. Pitfall tổng hợp

Pitfall 1 — LinkedList.poll() vs Queue.remove()

Queue<String> q = new LinkedList<>();
// q is empty

q.remove(); // throws NoSuchElementException -- dangerous in production
q.poll();   // returns null -- safe, but watch for NPE if you unbox

Chọn API nhất quán trong codebase. offer/poll/peek an toàn hơn cho business logic thông thường. add/remove/element phù hợp cho contract violation (invariant bị phá là bug nghiêm trọng, không phải case thông thường).

Pitfall 2 — ArrayDeque không cho null elements

Deque<String> dq = new ArrayDeque<>();
dq.offer(null); // throws NullPointerException immediately

// LinkedList cho phep null -- nhung day la dau hieu thiet ke kem
Deque<String> linked = new LinkedList<>();
linked.offer(null); // OK, but poll() returns null -- indistinguishable from "empty"

Lý do ArrayDeque từ chối null: null được dùng làm sentinel bên trong implementation để detect "slot trống" trong circular array. Nếu cho phép null element, code không thể phân biệt slot chưa dùng với phần tử null hợp lệ.

Nếu cần biểu diễn "không có giá trị", dùng Optional<T> hoặc thiết kế lại để tránh null trong queue.

Pitfall 3 — Nhầm Deque.push() với Deque.offer()

Deque có thể dùng cả làm stack (LIFO) lẫn queue (FIFO). Hai convention thao tác ở hai đầu khác nhau:

Deque<Integer> dq = new ArrayDeque<>();

// Stack semantics (LIFO): push/pop/peek -- thao tac o HEAD
dq.push(1); dq.push(2); dq.push(3);
dq.pop();  // returns 3 -- LIFO

// Queue semantics (FIFO): offer/poll/peek -- offer vao TAIL, poll tu HEAD
dq.offer(1); dq.offer(2); dq.offer(3);
dq.poll(); // returns 1 -- FIFO

push(x) tương đương addFirst(x) — thêm vào HEAD. offer(x) tương đương addLast(x) — thêm vào TAIL. poll() tương đương pollFirst() — lấy từ HEAD.

Nếu mix push và offer, queue lẫn lộn LIFO/FIFO — kết quả không đoán được. Chọn một convention và nhất quán. Khi review code thấy Deque dùng lẫn lộn push và offer, đó là bug.

8. Applied to tech

Java ThreadPoolExecutor: task queue quyết định loại thread pool. LinkedBlockingQueue unbounded → newCachedThreadPool. ArrayBlockingQueue bounded với capacity cố định → kiểm soát backpressure. SynchronousQueue không buffer → mỗi task cần thread available ngay. Chọn sai queue type có thể dẫn đến OOM (unbounded queue với producer nhanh hơn consumer) hoặc task rejection (bounded queue quá nhỏ).

Kafka topic partition: mỗi partition là append-only log — về bản chất là queue không giới hạn. Consumer đọc theo offset — giống poll nhưng không xóa, nhiều consumer group có thể đọc cùng offset độc lập. Module 8 (Big Data & Streaming) sẽ phân tích chi tiết.

BFS shortest path: BFS dùng queue để đảm bảo duyệt theo từng lớp — phần tử gần source được duyệt trước. Module 5 (Graph) sẽ implement BFS đầy đủ. Nếu thay queue bằng stack, thuật toán biến thành DFS — không còn đảm bảo tìm đường ngắn nhất.

ConcurrentLinkedQueue: lock-free queue dùng thuật toán Michael & Scott (1996) với CAS (Compare-And-Swap). Không block — producer và consumer có thể chạy concurrent mà không cần synchronized. Phù hợp khi cần non-blocking concurrency. Sẽ phân tích trong Module 2 extension về concurrent data structures.

OS scheduler ready queue: process chờ CPU được đưa vào ready queue. FIFO scheduler đơn giản. Round-robin thêm time quantum. Priority scheduler dùng PriorityQueue. Linux Completely Fair Scheduler (CFS) dùng red-black tree — nhưng nguyên lý cơ bản vẫn là "queue của process chờ được phục vụ".

9. Deep Dive

10. Tóm tắt

• Queue là FIFO: phần tử vào đầu tiên sẽ ra đầu tiên. offer/poll/peek là API an toàn hơn add/remove/element.
• 4 biến thể: Queue (FIFO), Deque (two-ended), PriorityQueue (heap-backed), BlockingQueue (concurrent). Chọn đúng loại theo use case.
• ArrayDeque thay LinkedList trong mọi trường hợp queue/deque thông thường: cache-friendly, ít GC, throughput cao hơn khoảng 5x.
• ArrayDeque không cho null: null là sentinel nội bộ cho "slot trống". Dùng Optional<T> nếu cần biểu diễn giá trị vắng mặt.
• Circular array với head/tail index và bit trick (i + 1) & (capacity - 1) — hiệu quả hơn modulo, capacity luôn là power of 2.
• Đừng mix push và offer trên cùng một Deque — push = addFirst (LIFO), offer = addLast (FIFO), trộn lẫn → undefined ordering.
• Monotonic deque giải bài Sliding Window Maximum trong O(n): mỗi index push/pop tối đa 1 lần, tổng thao tác là 2n.

11. Tự kiểm tra

Queue<Node> q = new ArrayDeque<>();
q.offer(start);
while (!q.isEmpty()) {
  Node curr = q.poll();          // FIFO: nearest node first
  for (Node neighbor : curr.neighbors) {
      if (!visited(neighbor)) {
          q.offer(neighbor);     // add to tail -- farther nodes wait
      }
  }
}

Bài tiếp theo: Circular buffer / ring queue