Queue & Deque — FIFO, sliding window, ArrayDeque thay LinkedList

TL;DR: Queue là FIFO (First In, First Out): phần tử vào trước thì ra trước, thêm ở một đầu (tail) và lấy ở đầu kia (head). Deque (double-ended queue) mở rộng hơn: thêm/lấy được ở cả hai đầu, nên dùng làm stack lẫn queue đều được. Trong Java, ArrayDeque (cài bằng circular array) gần như luôn tốt hơn LinkedList cho queue/deque thông thường nhờ cache locality và ít tạo object cho GC dọn. Mẫu monotonic deque giải bài Sliding Window Maximum trong O(n) thay vì cách ngây thơ O(n*k).

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 xa vời: nó quyết định thứ tự phục vụ trong mọi hệ thống có nhiều request tranh nhau.

Bài này phân biệt 4 biến thể queue, giải thích khi nào chọn ArrayDeque thay LinkedList, và trình bày kỹ thuật cửa sổ trượt (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

Java có nhiều loại queue. Chọn sai sẽ dẫn đến chạy chậm hoặc bug khó thấy:

Queue cơ bản là trường hợp đơn giản nhất, và bài này tập trung vào nó cùng Deque.

Priority Queue dùng heap bên dưới, sẽ học ở bài 06.

Blocking Queue dùng trong lập trình đa luồng: mẫu producer/consumer, hàng đợi task của ThreadPoolExecutor.

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

Interface Queue của Java có hai phiên bản cho mỗi thao tác cơ bản: một bản ném exception khi thất bại, một bản trả về giá trị đặc biệt.

Quy tắc thực tế: chọn một kiểu và giữ nhất quán trong cả codebase. Code thật thường chuộng offer/poll/peek vì trả null dễ xử lý hơn ném exception: kiểm tra if (result != null) dễ hơn bắt exception ở đoạn code chạy dày. Chỉ dùng add/remove/element khi muốn lỗi nổ ra sớm và rõ (vi phạm hợp đồng là lỗi nghiêm trọng, không phải tình huống bình thường).

Queue rỗng là một edge case kinh điển: bài toán nào cũng cần tự hỏi "nếu rỗng thì sao" ngay từ đầu (nếu chưa quen thói quen đó, xem Edge case).

Thử ngẫmkhi review code, bạn gặp queue.remove() gọi trong một vòng lặp mà không kiểm tra rỗng trước. Theo bảng trên, khi queue cạn giữa chừng, chương trình sẽ dừng theo kiểu nào?

4. Pseudocode implement Queue bằng linked list

Linked list là cấu trúc tự nhiên nhất để cài 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.

-- Queue cài trên singly linked list
-- enqueue: thêm vào tail
-- dequeue: lấy từ head
Node:
    data
    next

Queue:
    head   -- đầu trước, dequeue từ đây
    tail   -- đầu sau, enqueue vào đây
    size

enqueue(Q, item):
    newNode <- Node(item, next=null)
    if Q.tail != null:
        Q.tail.next <- newNode
    Q.tail <- newNode
    if Q.head = null:
        Q.head <- newNode   -- phần tử đầu tiên
    Q.size <- Q.size + 1

Time: O(1) Space: O(1)

dequeue(Q):
    if Q.head = null: throw "Queue rỗng"
    item <- Q.head.data
    Q.head <- Q.head.next
    if Q.head = null:
        Q.tail <- null       -- queue vừa trở thành rỗng
    Q.size <- Q.size - 1
    return item

Time: O(1) Space: O(1)

Chi tiết then chốt: phải giữ cả pointer head lẫn tail. Nếu chỉ giữ head, mỗi lần enqueue phải duyệt đến cuối, tốn O(n). Cấu trúc Node và những điểm được/mất của singly linked list đã phân tích ở bài 02.

5. ArrayDeque internals: vì sao thay LinkedList

java.util.LinkedList cài cả List lẫn Deque, nghe có vẻ tiện. Nhưng thực tế ArrayDeque thắng rõ rệt cả về throughput (số thao tác mỗi giây) lẫn bộ nhớ. Hiểu cơ chế bên dưới sẽ thấy vì sao.

5.1 Circular array backing

ArrayDeque dùng một circular array: array thông thường nhưng head và tail có thể "quay vòng". Khi tail đến cuối array, nó quay về index 0 (wrap around) thay vì bắt array phải nở thêm.

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
Thứ tự phần tử trong queue: A, B, C, D, E

addLast đặt phần tử tại tail rồi tăng tail; pollFirst lấy phần tử tại head rồi tăng head. Khi chỉ số chạm cuối mảng thì quay về 0. Trong OpenJDK 21, việc quay vòng được viết bằng một phép so sánh đơn giản (if (++i >= length) i = 0). Mẹo AND bit (& (capacity - 1)) chỉ đúng khi capacity là luỹ thừa của 2, và bản ArrayDeque cũ (JDK 8) từng dùng nó. Bài Circular buffer sẽ giải thích mẹo đó.

5.2 Grow và amortized O(1)

Khi mảng nền đầy (head == tail), grow() tăng capacity (thêm capacity + 2 ô nếu mảng nhỏ hơn 64, còn lại thêm 50%) và copy toàn bộ mảng. Chi phí chia đều (amortized) vẫn là O(1), giống ArrayList.grow(), nhưng circular array phức tạp hơn vì khi copy phải "duỗi thẳng" vòng tròn ra.

grow(Q):
    newCapacity <- Q.capacity + (Q.capacity + 2 nếu nhỏ hơn 64, ngược lại Q.capacity / 2)
    newData <- Array kích thước newCapacity
    -- Sao chép từ head đến cuối mảng cũ
    copy Q.data[Q.head..Q.capacity-1] vào newData[0..]
    -- Sao chép từ đầu mảng cũ đến tail (phần wrap-around)
    copy Q.data[0..Q.tail-1] vào newData[Q.capacity-Q.head..]
    Q.head <- 0
    Q.tail <- Q.size
    Q.data <- newData
    Q.capacity <- newCapacity

Time: O(n) amortized O(1) Space: O(n) tổng thể

5.3 So sánh ArrayDeque vs LinkedList

Quy tắc thực tế: luôn dùng ArrayDeque thay LinkedList cho queue/deque trong code thật, trừ khi cần truy cập theo index (khi đó dùng danh sách động) hoặc cần null làm giá trị đánh dấu (nên thiết kế lại, dùng Optional).

Thử ngẫmbảng trên cho thấy ArrayDeque thắng LinkedList về throughput khi chèn. Một service lại cần null làm giá trị hợp lệ trong queue: dòng cuối bảng nói gì về lựa chọn lúc đó?

6. Sliding window pattern: monotonic deque

Đây là ứng dụng nổi tiếng nhất của Deque, hay gặp trong thi lập trình thi đấu và phỏng vấn coding.

6.1 Bài toán

Sliding Window Maximum: cho mảng A có n phần tử và cửa sổ (window) kích thước k, trả về mảng chứa giá trị lớn nhất của từng cửa sổ.

Ví dụ: A = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Hãy hình dung bạn đứng trong hàng chờ và chỉ người cao nhất còn trong tầm nhìn mới quan trọng: người thấp đứng trước một người cao hơn mình thì không bao giờ có cơ hội thành người cao nhất nữa, nên có thể cho đi luôn. Đó là toàn bộ ý tưởng bên dưới.

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

Cách ngây thơ (naive): với mỗi trong n - k + 1 cửa sổ, quét k phần tử, tổng O(n*k). Với n = 100.000 và k = 10.000, đó là khoảng 1 tỷ phép tính, quá chậm.

6.2 Ý tưởng monotonic deque

Dùng Deque lưu index (không lưu giá trị) và giữ một tính chất: các index trong deque ứng với giá trị giảm dần từ đầu đến cuối. Nhờ vậy front của deque luôn là index của phần tử lớn nhất trong cửa sổ hiện tại.

slidingWindowMax(A, k):
    dq <- Deque rỗng   -- lưu index, value giảm dần từ front đến back
    result <- Array kích thước (n - k + 1)

    for i <- 0 đến n-1:
        -- Bước 1: loại index đã ra khỏi cửa sổ
        while dq không rỗng and dq.peekFirst() <= i - k:
            dq.pollFirst()

        -- Bước 2: giữ tính giảm dần — loại index có giá trị nhỏ hơn A[i]
        while dq không rỗng and A[dq.peekLast()] < A[i]:
            dq.pollLast()

        dq.offerLast(i)

        -- Bước 3: ghi kết quả khi cửa sổ đã đủ k phần tử
        if i >= k - 1:
            result[i - k + 1] <- A[dq.peekFirst()]

    return result

Time: O(n) Space: O(k)

6.3 Trace ví dụ

A = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 (đọc bảng theo từng hàng, như cách vẽ bảng trace ở bài Bảng trace):

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

6.4 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 cả vòng lặp là 2n. Vòng lặp ngoài chạy n lần, còn hai vòng while bên trong không cộng thêm n lần nữa: chúng dùng chung một ngân sách 2n. Kết quả: O(n) time, O(k) space.

Thử ngẫmmỗi index push đúng một lần, pop tối đa một lần, nên ngân sách là 2n thao tác. Nếu đổi điều kiện pop-back từ "nhỏ hơn" thành "nhỏ hơn hoặc bằng", lập luận O(n) này còn đứng vững không?

7. Pitfall tổng hợp

Pitfall 1: poll() vs remove() trên queue rỗng

Xem bảng ở mục 3: remove() ném NoSuchElementException, poll() trả null (coi chừng unboxing null nếu gán vào int). Chọn một kiểu và giữ nhất quán.

Pitfall 2: ArrayDeque không cho phần tử null

dq <- ArrayDeque rỗng
dq.offer(null)   -- ném NullPointerException ngay

-- LinkedList cho phép null -- nhưng đây là dấu hiệu thiết kế kém
linked <- LinkedList rỗng
linked.offer(null)   -- OK, nhưng poll() trả null
                     -- không phân biệt được "queue rỗng" với "phần tử null hợp lệ"

Lý do ArrayDeque từ chối null: bên trong, null được dùng làm dấu hiệu (sentinel) cho ô trống trong circular array. Nếu cho phép phần tử null, code không phân biệt được ô 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 để queue không chứa null.

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

push(x) tương đương addFirst(x) (thêm vào HEAD), còn offer(x) tương đương addLast(x) (thêm vào TAIL); pop() và poll() đều lấy từ HEAD. Trộn push với offer thì thứ tự LIFO/FIFO lẫn lộn và kết quả không đoán được. Hãy chọn một quy ước và giữ đến cùng (xem câu tự kiểm tra số 4 để thử tay).

8. Applied to tech

Java ThreadPoolExecutor: hàng đợi task quyết định kiểu thread pool. LinkedBlockingQueue không giới hạn kích thước là queue mặc định của newFixedThreadPool. ArrayBlockingQueue có giới hạn capacity cố định → kiểm soát được backpressure (ép bên gửi chậm lại khi bên nhận không kịp). SynchronousQueue không đệm → mỗi task cần có sẵn thread rảnh ngay, và là queue của newCachedThreadPool. Chọn sai loại queue có thể gây OOM (queue không giới hạn mà producer nhanh hơn consumer) hoặc task bị từ chối (queue giới hạn quá nhỏ).

BFS shortest path: BFS dùng queue để duyệt theo từng lớp: phần tử gần điểm xuất phát (source) được duyệt trước. Khoá Thuật toán Cốt lõi (module Đồ thị) sẽ cài BFS đầy đủ. Nếu thay queue bằng stack, thuật toán thành DFS và không còn đảm bảo tìm ra đường ngắn nhất.

9. Deep Dive

10. Tóm tắt

• Queue là FIFO, deque có hai đầu. offer/poll/peek trả giá trị đặc biệt, còn add/remove/element ném exception khi thất bại.
• ArrayDeque thay LinkedList cho queue/deque thông thường: dữ liệu liền nhau nên thân thiện với cache, ít việc cho GC. ArrayDeque không cho phần tử null vì dùng null đánh dấu ô trống.
• Đừng trộn push với offer trên cùng một Deque: push = addFirst (LIFO), offer = addLast (FIFO).
• Monotonic deque giải Sliding Window Maximum trong O(n): mỗi index push đúng một lần và pop tối đa một lần, tổng thao tác tối đa 2n.

11. Tự kiểm tra

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