[Advanced Java] Queue, Deque, Stack và PriorityQueue trong Java

Một List cho bạn chạm vào bất kỳ element nào ở bất kỳ vị trí nào. Bốn type trong bài này làm điều ngược lại: mỗi cái giới hạn chỗ bạn được phép thêm vào và chỗ bạn được phép lấy ra, và chính giới hạn đó mới là giá trị của chúng. Queue cho bạn phần đầu, Deque cho bạn cả hai đầu, còn PriorityQueue cho bạn element nhỏ nhất theo một thứ tự nào đó.

Kèm theo những giới hạn ấy là một contract rất dễ dùng sai, vì gần như mọi thao tác đều tồn tại hai lần dưới hai cái tên khác nhau với hai cách báo lỗi khác nhau. Bài này đi qua contract đó từng method một, qua class Stack cũ kỹ cùng đúng cái cách thiết kế của nó rò rỉ ra ngoài, và qua hiểu lầm phổ biến nhất trong cả collection framework — rằng PriorityQueue giữ một collection đã sort. Nó không hề như vậy.

Mọi dòng output, mọi exception và mọi con số đếm so sánh dưới đây đều được tạo ra bằng cách compile và chạy code trên OpenJDK 21.0.6. Không có bất kỳ số đo thời gian nào trong bài; chỗ nào chi phí quan trọng thì nó được diễn đạt theo cấu trúc, bằng số lần so sánh và số lần copy array đếm được.

Bốn type này nằm ở đâu

Queue là một interface nằm ngay dưới Collection. Deque extends Queue, và từ Java 21 nó còn extends SequencedCollection. ArrayDeque và LinkedList implement Deque; PriorityQueue implement Queue thông qua AbstractQueue; Stack là kẻ lạc loài và extends Vector.

import java.util.*;

public class Hierarchy {
    static void show(Class<?> c) {
        System.out.printf("%-16s extends %-22s implements %s%n",
            c.getSimpleName(),
            c.getSuperclass() == null ? "-" : c.getSuperclass().getSimpleName(),
            Arrays.stream(c.getInterfaces()).map(Class::getSimpleName).toList());
    }
    public static void main(String[] args) {
        show(ArrayDeque.class);
        show(LinkedList.class);
        show(PriorityQueue.class);
        show(Stack.class);
        System.out.println();
        System.out.println("Queue interfaces:  " + Arrays.toString(Queue.class.getInterfaces()));
        System.out.println("Deque interfaces:  " + Arrays.toString(Deque.class.getInterfaces()));
        System.out.println("ArrayDeque is a List? " + List.class.isAssignableFrom(ArrayDeque.class));
        System.out.println("Stack is a List?   " + List.class.isAssignableFrom(Stack.class));
    }
}

ArrayDeque       extends AbstractCollection     implements [Deque, Cloneable, Serializable]
LinkedList       extends AbstractSequentialList implements [List, Deque, Cloneable, Serializable]
PriorityQueue    extends AbstractQueue          implements [Serializable]
Stack            extends Vector                 implements []

Queue interfaces:  [interface java.util.Collection]
Deque interfaces:  [interface java.util.Queue, interface java.util.SequencedCollection]
ArrayDeque is a List? false
Stack is a List?   true

Có hai dòng đáng nhớ ở đó. ArrayDeque không phải là List, nên nó không có get(i) và không có add(i, e) — giới hạn được chính type ép buộc. Còn Stack là một List, và đó là toàn bộ nội dung của một phần phía sau.

Hai họ method của Queue: ném exception, hoặc trả về một giá trị đặc biệt

Queue khai báo sáu method, và thực chất đó là ba thao tác được viết hai lần. Insert, remove và examine, mỗi cái có một phiên bản ném exception khi không làm được việc và một phiên bản báo thất bại bằng cách trả về một giá trị.

Sáu method

add trả về true khi thành công còn offer trả về true hoặc false. remove và poll đều trả về element bị lấy đi. element và peek đều trả về phần tử đầu mà không lấy nó ra.

Khi queue rỗng

Đây là chỗ khác biệt lộ ra, vì "rỗng" là trạng thái mà mọi queue đều đi qua.

import java.util.*;

public class EmptyQueue {
    public static void main(String[] args) {
        Queue<String> q = new ArrayDeque<>();
        System.out.println("empty queue: " + q);
        System.out.println("poll()    -> " + q.poll());
        System.out.println("peek()    -> " + q.peek());
        try { q.remove(); } catch (Exception e) { System.out.println("remove()  -> " + e); }
        try { q.element(); } catch (Exception e) { System.out.println("element() -> " + e); }
    }
}

empty queue: []
poll()    -> null
peek()    -> null
remove()  -> java.util.NoSuchElementException
element() -> java.util.NoSuchElementException

NoSuchElementException không mang theo message nào, nên nó là thứ khó chịu khi gặp trong log production — bạn chỉ có mỗi stack trace. poll và peek thì trả về null.

Khi queue có giới hạn dung lượng

ArrayDeque, LinkedList và PriorityQueue đều không giới hạn: chúng tự lớn ra chứ không từ chối. Nên trên chúng add và offer hành xử y hệt nhau, và khác biệt chỉ hiện ra khi queue có capacity. Implementation có giới hạn dung lượng tiêu chuẩn là ArrayBlockingQueue, ở đây được dùng thuần túy như một Queue bị giới hạn capacity, không dính gì tới thread.

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

public class BoundedQueue {
    public static void main(String[] args) {
        Queue<String> bounded = new ArrayBlockingQueue<>(2);
        System.out.println("offer(x) -> " + bounded.offer("x"));
        System.out.println("offer(y) -> " + bounded.offer("y"));
        System.out.println("offer(z) -> " + bounded.offer("z"));
        try { bounded.add("z"); } catch (Exception e) { System.out.println("add(z)   -> " + e); }
        System.out.println("bounded: " + bounded);
    }
}

offer(x) -> true
offer(y) -> true
offer(z) -> false
add(z)   -> java.lang.IllegalStateException: Queue full
bounded: [x, y]

offer trả về false và vứt element đi mất; add ném IllegalStateException: Queue full. Cả hai đều để lại queue với [x, y]. Phiên bản nguy hiểm là offer, vì một chương trình bỏ qua giá trị boolean trả về sẽ mất dữ liệu trong im lặng.

java.util.concurrent còn có BlockingQueue, bổ sung thêm một cặp thao tác nữa biết chờ chỗ trống hoặc chờ element thay vì thất bại — phần đó thuộc về concurrency và không nằm trong bài này.

Nên dùng họ nào

Chọn theo việc queue rỗng hay đầy có ý nghĩa gì trong chương trình của bạn:

• Nếu nó nghĩa là có bug, dùng remove và element. Exception dừng chương trình ngay tại chỗ sai thay vì để một null đi qua vài stack frame rồi mới có ai đó dereference nó.
• Nếu đó là trạng thái bình thường — một worker đang rút dần một queue thường xuyên rỗng — dùng poll và peek, và kiểm tra kết quả ở mọi chỗ gọi.
• Với insert vào queue không giới hạn thì chọn gì cũng như nhau, vì không cái nào thất bại được. Chọn một cái và nhất quán; đa số code dùng offer.

Trộn hai họ trong cùng một vòng lặp mới là nơi sinh ra bug: while (!q.isEmpty()) { process(q.poll()); } thì an toàn, nhưng cũng vòng lặp đó với thêm một consumer thứ hai có thể thấy isEmpty() trả về false mà poll() vẫn trả về null.

Deque: một cấu trúc, mở ở cả hai đầu

Deque — viết tắt của "double ended queue", thường đọc là "đek" — cho phép insert, remove và examine ở cả đầu lẫn cuối. Chỉ một khái quát hóa đó thay thế được cả hai cấu trúc kinh điển: dùng một đầu thì nó là stack, dùng một đầu để vào và đầu kia để ra thì nó là queue.

Bảng method đầy đủ

Mọi thao tác của Queue xuất hiện hai lần, mỗi đầu một lần, và mỗi cái trong số đó lại vẫn có dạng ném exception và dạng trả về giá trị đặc biệt. Tổng cộng mười hai method, xếp trên một lưới hoàn toàn đều đặn.

Các method thừa kế từ Queue chỉ là tên gọi khác của cặp head–tail cho ra thứ tự FIFO: add là addLast, offer là offerLast, remove là removeFirst, poll là pollFirst, element là getFirst, peek là peekFirst.

import java.util.*;

public class DequeBasics {
    public static void main(String[] args) {
        Deque<String> d = new ArrayDeque<>();
        d.addFirst("B");
        d.addLast("C");
        d.offerFirst("A");
        d.offerLast("D");
        System.out.println("deque: " + d);
        System.out.println("getFirst()  -> " + d.getFirst());
        System.out.println("getLast()   -> " + d.getLast());
        System.out.println("pollFirst() -> " + d.pollFirst());
        System.out.println("pollLast()  -> " + d.pollLast());
        System.out.println("deque: " + d);

        Deque<String> empty = new ArrayDeque<>();
        System.out.println("pollFirst() -> " + empty.pollFirst());
        try { empty.getFirst(); } catch (Exception e) { System.out.println("getFirst()  -> " + e); }
    }
}

deque: [A, B, C, D]
getFirst()  -> A
getLast()   -> D
pollFirst() -> A
pollLast()  -> D
deque: [B, C]
pollFirst() -> null
getFirst()  -> java.util.NoSuchElementException

push, pop và peek: cách dùng như stack

Deque còn khai báo ba method mang tên của stack. Chúng được định nghĩa là thao tác trên đầu head: push là addFirst, pop là removeFirst, và peek kiểu stack chính là peekFirst. Vì head là đỉnh stack nên iteration chạy từ element được push gần nhất đi xuống — đúng bằng thứ tự pop.

import java.util.*;

public class DequeAsStack {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("bottom");
        stack.push("middle");
        stack.push("top");
        System.out.println("stack: " + stack);
        System.out.println("peek() -> " + stack.peek());
        System.out.println("for-each order:");
        for (String e : stack) System.out.println("  " + e);
        System.out.println("pop() -> " + stack.pop());
        System.out.println("pop() -> " + stack.pop());
        System.out.println("stack: " + stack);
        System.out.println("descendingIterator gives bottom-to-top if you want it:");
        Iterator<String> it = stack.descendingIterator();
        while (it.hasNext()) System.out.println("  " + it.next());
    }
}

stack: [top, middle, bottom]
peek() -> top
for-each order:
  top
  middle
  bottom
pop() -> top
pop() -> middle
stack: [bottom]
descendingIterator gives bottom-to-top if you want it:
  bottom

pop trên một ArrayDeque rỗng ném java.util.NoSuchElementException, không phải EmptyStackException như class cũ. Không có phiên bản trả-về-giá-trị của pop; khi rỗng là chuyện bình thường thì dùng pollFirst.

Chọn ArrayDeque hay LinkedList

Cả hai đều implement Deque, và chúng khác nhau ở chi phí cho mỗi element. ArrayDeque giữ một Object[] cùng hai index là head và tail, hai index này quay vòng qua cuối array — đó chính là ý nghĩa của "circular array". Không có gì bị dịch chuyển khi bạn thêm hay bớt ở hai đầu; chỉ có một index đổi giá trị. Đọc ngược các field private ra là thấy ngay:

import java.lang.reflect.Field;
import java.util.*;

public class Circular {
    static Field ELEMENTS, HEAD, TAIL;
    static {
        try {
            ELEMENTS = ArrayDeque.class.getDeclaredField("elements"); ELEMENTS.setAccessible(true);
            HEAD = ArrayDeque.class.getDeclaredField("head"); HEAD.setAccessible(true);
            TAIL = ArrayDeque.class.getDeclaredField("tail"); TAIL.setAccessible(true);
        } catch (Exception e) { throw new RuntimeException(e); }
    }
    static void dump(String label, ArrayDeque<?> d) throws Exception {
        Object[] es = (Object[]) ELEMENTS.get(d);
        System.out.printf("%-24s head=%d tail=%d  capacity=%d  %s%n",
            label, HEAD.getInt(d), TAIL.getInt(d), es.length, Arrays.toString(es));
    }
    public static void main(String[] args) throws Exception {
        ArrayDeque<String> d = new ArrayDeque<>(5);
        dump("new ArrayDeque<>(5)", d);
        d.addLast("a"); d.addLast("b"); d.addLast("c");
        dump("addLast a, b, c", d);
        d.pollFirst(); d.pollFirst();
        dump("pollFirst twice", d);
        d.addLast("d"); d.addLast("e"); d.addLast("f");
        dump("addLast d, e, f", d);
        d.addLast("g");
        dump("addLast g", d);
        System.out.println("                         iteration: " + d);
        d.addLast("h");
        dump("addLast h (resize)", d);
        System.out.println("                         iteration: " + d);
    }
}

Chạy nó với module được mở ra, vì các field đó là private:

java --add-opens java.base/java.util=ALL-UNNAMED Circular

new ArrayDeque<>(5)      head=0 tail=0  capacity=6  [null, null, null, null, null, null]
addLast a, b, c          head=0 tail=3  capacity=6  [a, b, c, null, null, null]
pollFirst twice          head=2 tail=3  capacity=6  [null, null, c, null, null, null]
addLast d, e, f          head=2 tail=0  capacity=6  [null, null, c, d, e, f]
addLast g                head=2 tail=1  capacity=6  [g, null, c, d, e, f]
                         iteration: [c, d, e, f, g]
addLast h (resize)       head=10 tail=2  capacity=14  [g, h, null, null, null, null, null, null, null, null, c, d, e, f]
                         iteration: [c, d, e, f, g, h]

g rơi vào index 0 trong khi element đầu tiên về mặt logic vẫn nằm ở index 2 — array đã quay vòng. Hai lần pollFirst không dời gì cả; chúng chỉ set một ô thành null rồi đẩy head tiến lên. Đến khi array đầy hẳn, nó được thay bằng một array lớn hơn và nội dung được copy qua.

Mấy lần copy đó là chi phí cấu trúc duy nhất mà ArrayDeque có còn LinkedList thì không, và số lần rất ít. Đoạn này cũng cần --add-opens:

import java.lang.reflect.Field;
import java.util.*;

public class CopyCost {
    public static void main(String[] args) throws Exception {
        Field f = ArrayDeque.class.getDeclaredField("elements"); f.setAccessible(true);
        int n = 1_000_000;
        ArrayDeque<Integer> d = new ArrayDeque<>();
        int last = ((Object[]) f.get(d)).length, resizes = 0; long copied = 0;
        for (int i = 0; i < n; i++) {
            d.addLast(i);
            int cap = ((Object[]) f.get(d)).length;
            if (cap != last) { resizes++; copied += i; last = cap; }
        }
        System.out.printf("ArrayDeque: %d addLast -> %d resizes, %d elements copied, final capacity %d%n",
            n, resizes, copied, last);
        System.out.printf("LinkedList: %d addLast -> %d Node objects allocated, 0 copies%n", n, n);
    }
}

ArrayDeque: 1000000 addLast -> 26 resizes, 2475359 elements copied, final capacity 1237734
LinkedList: 1000000 addLast -> 1000000 Node objects allocated, 0 copies

Hai mươi sáu lần resize và khoảng 2,5 reference được copy cho mỗi element thêm vào, so với một object node cấp phát trên heap cho mỗi element kèm hai field reference phụ. Đó là lý do ArrayDeque là lựa chọn mặc định cho cả việc dùng như stack lẫn như queue, và cũng là lý do tài liệu của ArrayDeque nói nó nhanh hơn Stack khi dùng như stack và nhanh hơn LinkedList khi dùng như queue.

Chỉ nên chọn LinkedList khi bạn thật sự cần nửa List của nó — truy cập theo index, ListIterator, hoặc element null.

ArrayDeque từ chối null, còn poll lại trả về null

ArrayDeque từ chối null ở mọi method thêm vào:

import java.util.*;

public class NullTrace {
    public static void main(String[] args) {
        Deque<String> d = new ArrayDeque<>();
        d.push(null);
    }
}

Exception in thread "main" java.lang.NullPointerException
	at java.base/java.util.ArrayDeque.addFirst(ArrayDeque.java:285)
	at java.base/java.util.ArrayDeque.push(ArrayDeque.java:578)
	at NullTrace.main(NullTrace.java:6)

Nhìn thì tưởng bất tiện, thật ra đó mới là điểm mấu chốt. poll, peek, pollFirst và peekLast đều dùng null để nói "chẳng có gì ở đó cả", nên một collection có thể chứa null sẽ làm giá trị trả về trở nên nhập nhằng. LinkedList cho phép null, và sự nhập nhằng đó là có thật:

import java.util.*;

public class NullQueue {
    public static void main(String[] args) {
        Deque<String> ll = new LinkedList<>();
        ll.add(null);
        System.out.println("size = " + ll.size() + ", isEmpty = " + ll.isEmpty());
        System.out.println("poll() -> " + ll.poll() + "   (a real element)");
        System.out.println("poll() -> " + ll.poll() + "   (now genuinely empty)");
    }
}

size = 1, isEmpty = false
poll() -> null   (a real element)
poll() -> null   (now genuinely empty)

Hai giá trị trả về giống hệt nhau, hai ý nghĩa khác nhau. ArrayDeque chặn khả năng đó ngay từ cửa.

⚠️ Lập luận y hệt áp dụng cho PriorityQueue, vốn cũng ném NullPointerException khi offer(null).

Stack là di sản cũ: cái giá của extends Vector

java.util.Stack có mặt trong JDK từ bản 1.0 và vẫn chạy được. Nó cũng là ví dụ kinh điển của việc dùng inheritance ở chỗ lẽ ra phải dùng composition, và hậu quả thì nhìn thấy được ngay từ code thường ngày.

Khai báo của nó là class Stack<E> extends Vector<E>, mà Vector thì implement List. Vậy nên một Stack là một List: nó có get, set, add(int, E), remove(int), insertElementAt, subList, indexOf và mọi thứ khác, tất cả đều public, tất cả đều tác động lên đúng vùng lưu trữ mà push và pop đang dùng.

Mọi method của Vector đều nằm trên stack của bạn

import java.util.*;

public class StackMess {
    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
        s.push("bottom");
        s.push("middle");
        s.push("top");
        System.out.println("stack: " + s);

        s.insertElementAt("SMUGGLED", 1);
        System.out.println("after insertElementAt(\"SMUGGLED\", 1): " + s);
        System.out.println("s.get(0)       -> " + s.get(0));
        System.out.println("s.elementAt(1) -> " + s.elementAt(1));
        s.set(2, "REWRITTEN");
        System.out.println("after set(2, \"REWRITTEN\"): " + s);
        s.remove(0);
        System.out.println("after remove(0): " + s);
        System.out.println("pop() -> " + s.pop());
        System.out.println("stack now: " + s);
    }
}

stack: [bottom, middle, top]
after insertElementAt("SMUGGLED", 1): [bottom, SMUGGLED, middle, top]
s.get(0)       -> bottom
s.elementAt(1) -> SMUGGLED
after set(2, "REWRITTEN"): [bottom, SMUGGLED, REWRITTEN, top]
after remove(0): [SMUGGLED, REWRITTEN, top]
pop() -> top
stack now: [SMUGGLED, REWRITTEN]

Một element đã bị chèn vào giữa stack, một element khác bị ghi đè tại chỗ, và element dưới đáy bị xóa — chẳng cái nào là thứ một stack được phép cho làm. Mọi lời gọi đó compile trót lọt không một warning, vì type thật sự có sẵn những method ấy. Một method nhận Stack của bạn làm parameter có thể làm tất cả những chuyện trên, và type system sẽ không phản đối.

Thứ tự iteration ngược với thứ tự pop

Bất ngờ thứ hai kín tiếng hơn nên cũng tệ hơn. Stack thừa kế iterator của Vector, vốn đi từ index 0 trở lên — mà index 0 là đáy stack.

import java.util.*;

public class StackOrder {
    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
        s.push("bottom");
        s.push("middle");
        s.push("top");

        System.out.println("for-each order:");
        for (String e : s) System.out.println("  " + e);

        System.out.println("pop order:");
        @SuppressWarnings("unchecked")
        Stack<String> copy = (Stack<String>) s.clone();
        while (!copy.isEmpty()) System.out.println("  " + copy.pop());
    }
}

for-each order:
  bottom
  middle
  top
pop order:
  top
  middle
  bottom

In một Stack ra, stream nó, copy nó vào một List hay ghi nó vào log đều cho ra thứ tự ngược với thứ tự các element thật sự sẽ đi ra. toString() hiện [bottom, middle, top] trong khi pop() trả về top trước tiên. Cái ArrayDeque ở phần trước in ra [top, middle, bottom] và pop theo đúng thứ tự đó.

Cho đủ bộ, cách hành xử khi rỗng cũng là một kiểu riêng — không thuộc họ nào trong hai họ của Queue:

import java.util.*;

public class StackQuirks {
    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
        try { s.peek(); } catch (Exception e) { System.out.println("empty.peek() -> " + e); }
        try { s.pop(); }  catch (Exception e) { System.out.println("empty.pop()  -> " + e); }
        System.out.println("EmptyStackException extends " + EmptyStackException.class.getSuperclass().getName());
        s.push(null);
        s.push("a");
        System.out.println("Stack accepts null:  " + s);
        System.out.println("search(\"a\")  -> " + s.search("a"));
        System.out.println("search(\"zz\") -> " + s.search("zz"));
    }
}

empty.peek() -> java.util.EmptyStackException
empty.pop()  -> java.util.EmptyStackException
EmptyStackException extends java.lang.RuntimeException
Stack accepts null:  [null, a]
search("a")  -> 1
search("zz") -> -1

EmptyStackException extends thẳng RuntimeException và tồn tại chỉ để phục vụ class này. search(Object) trả về khoảng cách tính từ đỉnh, đếm từ 1 chứ không phải index, và -1 khi không tìm thấy — những quy ước không xuất hiện ở bất kỳ đâu khác trong framework.

Còn một cái giá nữa: Vector synchronize các method của nó, nên pop() và peek() là synchronized còn push thì ủy quyền cho addElement cũng synchronized. Bạn trả tiền cho cái lock đó ở mọi lời gọi dù chỉ chạy một thread, mà nó vẫn không làm cho chuỗi thao tác kiểu "kiểm tra isEmpty rồi pop" trở nên atomic.

Thứ thay thế là ArrayDeque

Đây không phải chuyện khẩu vị. Chính tài liệu của Stack trong JDK viết rằng một tập thao tác LIFO đầy đủ và nhất quán hơn được cung cấp bởi interface Deque cùng các implementation của nó, "which should be used in preference to this class". Việc chuyển đổi hoàn toàn máy móc, và code kết quả còn ngắn hơn:

Hãy khai báo biến kiểu Deque chứ không phải ArrayDeque, để phần code còn lại chỉ nhìn thấy đúng những thao tác mà một stack nên có. Chỉ giữ Stack khi một API có sẵn ép bạn dùng type đó.

PriorityQueue là một binary heap, không phải list đã sort

PriorityQueue trả element ra theo thứ tự priority khi bạn gọi poll, và đúng một câu đúng đó bị khái quát thành một câu sai: rằng collection này đã được sort. Không hề. Nó là một binary heap lưu trong một array, và tính chất duy nhất nó duy trì là mỗi element nhỏ hơn hoặc bằng hai con của nó.

toString in ra array, không phải thứ tự

import java.util.*;

public class HeapOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int[] input = {5, 1, 8, 3, 9, 2, 7, 4, 6};
        for (int n : input) pq.offer(n);
        System.out.println("inserted:  " + Arrays.toString(input));
        System.out.println("toString:  " + pq);
        System.out.println("toArray:   " + Arrays.toString(pq.toArray()));
        System.out.println("copy:      " + new ArrayList<>(pq));
        System.out.println("peek():    " + pq.peek());

        PriorityQueue<Integer> c = new PriorityQueue<>(pq);
        StringJoiner j = new StringJoiner(", ", "[", "]");
        while (!c.isEmpty()) j.add(String.valueOf(c.poll()));
        System.out.println("poll loop: " + j);
    }
}

inserted:  [5, 1, 8, 3, 9, 2, 7, 4, 6]
toString:  [1, 3, 2, 4, 9, 8, 7, 5, 6]
toArray:   [1, 3, 2, 4, 9, 8, 7, 5, 6]
copy:      [1, 3, 2, 4, 9, 8, 7, 5, 6]
peek():    1
poll loop: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Đọc kỹ chỗ đó. toString() in ra [1, 3, 2, 4, 9, 8, 7, 5, 6] — element nhỏ nhất đứng đầu, còn sau đó thì thứ tự chẳng phải thứ tự thêm vào cũng chẳng phải thứ tự sort. Đó là bố cục array của heap: index 0 là gốc, và con của index i nằm ở 2i+1 và 2i+2. Vậy index 0 giữ 1, hai con của nó ở index 1 và 2 giữ 3 và 2, con của chúng ở index 3, 4, 5, 6 giữ 4, 9, 8, 7, và cứ thế. Mỗi parent nhỏ hơn cả hai con, và không có gì được đảm bảo thêm.

Dòng peek() ở trên chính là cái bẫy thu nhỏ: element đầu tiên trong toString() đúng là element sẽ ra tiếp theo thật, và đó là lý do ảo tưởng này sống lâu đến vậy. Chỉ có vòng poll đầy đủ mới cho ra [1, 2, 3, 4, 5, 6, 7, 8, 9].

Dựng heap lên từng offer một sẽ thấy bố cục đó từ đâu ra — mỗi giá trị mới đặt vào cuối rồi hoán đổi ngược lên chừng nào nó còn nhỏ hơn parent:

offer(5) -> [5]
offer(1) -> [1, 5]
offer(8) -> [1, 5, 8]
offer(3) -> [1, 3, 8, 5]
offer(9) -> [1, 3, 8, 5, 9]
offer(2) -> [1, 3, 2, 5, 9, 8]
offer(7) -> [1, 3, 2, 5, 9, 8, 7]
offer(4) -> [1, 3, 2, 4, 9, 8, 7, 5]
offer(6) -> [1, 3, 2, 4, 9, 8, 7, 5, 6]

offer(2) là bước thú vị: 2 được nối vào index 5, so với parent của nó là 8 ở index 2, hoán đổi, rồi so với gốc là 1 và dừng lại. Hai lần so sánh, và array bị xáo trộn đúng bằng mức tối thiểu cần thiết.

Iterate không đi theo thứ tự priority

Vì toString() đi qua array bên dưới, nên mọi thứ xây trên iterator cũng vậy. Không có view đã sort nào ở đâu cả.

import java.util.*;

public class HeapIteration {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 8, 3, 9, 2, 7, 4, 6));
        System.out.print("for-each:         ");
        for (int n : pq) System.out.print(n + " ");
        System.out.println();
        System.out.println("stream().toList() " + pq.stream().toList());
        System.out.println("stream().sorted() " + pq.stream().sorted().toList());
    }
}

for-each:         1 3 2 4 9 8 7 5 6 
stream().toList() [1, 3, 2, 4, 9, 8, 7, 5, 6]
stream().sorted() [1, 2, 3, 4, 5, 6, 7, 8, 9]

Vòng for-each và stream().toList() đều trả về đúng array heap thô. Chỉ có sorted() cho ra giá trị tăng dần, và đó là một lần sort được thực hiện dọc đường chứ không phải tính chất của queue. PriorityQueue ghi rõ trong tài liệu rằng iterator của nó không đảm bảo duyệt element theo bất kỳ thứ tự cụ thể nào, nên rút cạn queue là cách đọc có thứ tự duy nhất mà nó cung cấp:

while (!pq.isEmpty()) {
    process(pq.poll());
}

Nếu bạn cần element theo thứ tự và cần giữ chúng lại, hãy poll vào một List, hoặc copy collection ra rồi sort bản copy. Đừng iterate rồi hy vọng.

Thứ tự đến từ đâu

Hoặc element implement Comparable, hoặc bạn đưa một Comparator vào constructor. Không có cái nào thì ngay lần offer đầu tiên đã hỏng:

import java.util.*;

record Task(String name, int priority) {}

public class NoOrdering {
    public static void main(String[] args) {
        PriorityQueue<Task> pq = new PriorityQueue<>();
        try { pq.offer(new Task("A", 1)); } catch (Exception e) { System.out.println(e); }
    }
}

java.lang.ClassCastException: class Task cannot be cast to class java.lang.Comparable (Task is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')

Một ClassCastException cho một lời gọi chẳng hề nhắc tới cast nào — cái cast nằm bên trong siftUpComparable. Đưa vào một Comparator là xong, và đảo ngược comparator đó biến min-heap thành max-heap:

import java.util.*;

public class MaxHeap {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int n : new int[]{5, 1, 8, 3, 9, 2, 7}) maxHeap.offer(n);
        System.out.println("toString: " + maxHeap);
        System.out.print("poll:     ");
        while (!maxHeap.isEmpty()) System.out.print(maxHeap.poll() + " ");
        System.out.println();
    }
}

toString: [9, 8, 7, 1, 3, 2, 5]
poll:     9 8 7 5 3 2 1 

Cùng class, cùng quy tắc bố cục array, hướng ngược lại. Invariant của heap giờ đọc là "mỗi parent lớn hơn hoặc bằng các con của nó", và toString() vẫn lộn xộn y như trước.

Priority bằng nhau thì không có thứ tự nào được đảm bảo

PriorityQueue không ổn định: hai element so sánh bằng nhau sẽ ra theo đúng thứ tự mà các thao tác heap tình cờ để lại. Chuyện này dễ chứng minh và cũng dễ dính đòn, vì với dữ liệu nhỏ nó thường trông y như thứ tự thêm vào.

import java.util.*;

record Task(String name, int priority) {
    @Override public String toString() { return name + "(" + priority + ")"; }
}

public class Ties {
    public static void main(String[] args) {
        PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        String[] names = {"A", "B", "C", "D", "E", "F"};
        int[] prios = {2, 1, 2, 1, 2, 1};
        for (int i = 0; i < names.length; i++) pq.offer(new Task(names[i], prios[i]));
        System.out.println("offered: A(2) B(1) C(2) D(1) E(2) F(1)");
        System.out.println("heap:    " + pq);
        System.out.print("poll:    ");
        while (!pq.isEmpty()) System.out.print(pq.poll() + " ");
        System.out.println();
    }
}

offered: A(2) B(1) C(2) D(1) E(2) F(1)
heap:    [B(1), D(1), F(1), A(2), E(2), C(2)]
poll:    B(1) D(1) F(1) A(2) E(2) C(2) 

Ba task priority 1 ra theo đúng thứ tự thêm vào, B D F. Ba task priority 2 thì không: chúng vào theo A C E mà ra theo A E C. Chẳng có gì là bug ở đây — comparator đã nói ba cái đó bằng nhau, nên heap được tự do sắp xếp chúng theo bất kỳ cách nào thỏa mãn invariant, và nó đã làm vậy.

Cách sửa là làm cho không còn hòa nhau nữa. Gắn cho mỗi element một số thứ tự tăng dần và so sánh theo nó ở tiêu chí thứ hai:

Comparator<Job> order = Comparator.comparingInt(Job::priority)
                                  .thenComparingLong(Job::seq);

Giờ không có hai element nào so sánh bằng nhau nữa, và thứ tự được quyết định hoàn toàn bởi comparator của bạn thay vì bởi nội tình của heap.

Không giới hạn, và không nhận null

PriorityQueue tự lớn khi cần; tham số truyền vào constructor là capacity ban đầu, không phải giới hạn. Capacity bằng 0 thì bị từ chối thẳng, còn null bị từ chối vì đúng lý do ArrayDeque từ chối nó — kèm một lý do thứ hai ở đây, vì null không so sánh được.

import java.util.*;

public class PQLimits {
    public static void main(String[] args) {
        PriorityQueue<Integer> g = new PriorityQueue<>(3);
        for (int i = 0; i < 100_000; i++) g.offer(i);
        System.out.println("capacity 3, after 100000 offers: size=" + g.size() + " peek=" + g.peek());
        try { new PriorityQueue<Integer>(0); } catch (Exception e) { System.out.println("new PriorityQueue<>(0) -> " + e); }
        try { g.offer(null); } catch (Exception e) { System.out.println("offer(null)            -> " + e); }
    }
}

capacity 3, after 100000 offers: size=100000 peek=0
new PriorityQueue<>(0) -> java.lang.IllegalArgumentException
offer(null)            -> java.lang.NullPointerException

Cả hai exception đều không mang message, nên một NullPointerException bắn ra từ sâu trong vòng lặp scheduling thường là một null lọt vào offer từ chỗ khác hoàn toàn.

offer và poll thật sự tốn gì

Heap không giữ collection theo thứ tự; nó chỉ giữ vừa đủ thứ tự để biết element nhỏ nhất. Điều đó thể hiện thành một số rất nhỏ lần so sánh cho mỗi lần insert và một số lớn hơn nhưng vẫn logarit cho mỗi lần lấy ra. Đếm chúng không cần đo thời gian gì cả — chỉ cần bọc comparator lại:

import java.util.*;

public class HeapCost {
    static long comparisons = 0;
    public static void main(String[] args) {
        for (int n : new int[]{1000, 10_000, 100_000}) {
            Random r = new Random(42);
            Integer[] data = new Integer[n];
            for (int i = 0; i < n; i++) data[i] = r.nextInt(1_000_000);

            comparisons = 0;
            PriorityQueue<Integer> pq =
                new PriorityQueue<>((a, b) -> { comparisons++; return Integer.compare(a, b); });
            for (Integer v : data) pq.offer(v);
            long ins = comparisons;

            comparisons = 0;
            while (!pq.isEmpty()) pq.poll();
            long ext = comparisons;

            System.out.printf("n=%-7d offer total=%-9d avg=%.2f  poll total=%-9d avg=%.2f  log2(n)=%.1f%n",
                n, ins, (double) ins / n, ext, (double) ext / n, Math.log(n) / Math.log(2));
        }
    }
}

n=1000    offer total=2232      avg=2.23  poll total=14994     avg=14.99  log2(n)=10.0
n=10000   offer total=22593     avg=2.26  poll total=216736    avg=21.67  log2(n)=13.3
n=100000  offer total=227662    avg=2.28  poll total=2831463   avg=28.31  log2(n)=16.6

Insert tốn khoảng 2,3 lần so sánh trung bình bất kể kích thước: một giá trị mới thường dừng sau một hai lần hoán đổi, vì đa số vị trí trong heap nằm gần đáy. Lấy ra mới là nửa đắt đỏ — element cuối được đưa lên gốc rồi sift xuống, và mỗi tầng tốn hai lần so sánh, một để chọn con nhỏ hơn và một để so con đó với giá trị đang sift. Các số trung bình đo được xác nhận đúng dáng đó: log2(n) tăng từ 10,0 lên 16,6 qua ba lần chạy trong khi trung bình mỗi lần poll tăng từ 14,99 lên 28,31, độ dốc gần như chính xác hai lần so sánh cho mỗi tầng thêm vào.

Có hai thao tác hoàn toàn không scale: contains(Object) và remove(Object) là quét tuyến tính qua array, vì heap không có index theo giá trị. peek() chỉ là một lần đọc array.

Dòng cuối cùng đó cũng đo được bằng đúng kỹ thuật trên: dựng heap từ một list 100.000 phần tử tốn 188.424 lần so sánh, so với 227.662 lần khi offer từng giá trị một. Khi đã có sẵn dữ liệu thì hãy ưu tiên constructor nhận collection.

Ba ví dụ thực tế

Task scheduler theo priority

Scheduler là hình hài tự nhiên của PriorityQueue: job đến theo thứ tự bất kỳ, job chạy tiếp theo luôn là job gấp nhất, và chạy một job có thể sinh thêm việc. Số thứ tự trong comparator chính là thứ làm cho các priority bằng nhau chạy theo kiểu đến trước làm trước thay vì tùy tiện.

import java.util.*;

public class Scheduler {
    record Job(String name, int priority, long seq) {}

    public static void main(String[] args) {
        Comparator<Job> byPriorityThenArrival =
            Comparator.comparingInt(Job::priority).thenComparingLong(Job::seq);

        PriorityQueue<Job> queue = new PriorityQueue<>(byPriorityThenArrival);
        long seq = 0;
        queue.offer(new Job("send-invoice", 5, seq++));
        queue.offer(new Job("page-oncall", 1, seq++));
        queue.offer(new Job("rebuild-index", 9, seq++));
        queue.offer(new Job("refund-charge", 1, seq++));
        queue.offer(new Job("warm-cache", 5, seq++));

        while (!queue.isEmpty()) {
            Job job = queue.poll();
            System.out.printf("run %-14s priority=%d arrived=%d%n",
                job.name(), job.priority(), job.seq());
            if (job.name().equals("page-oncall")) {
                queue.offer(new Job("escalate", 1, seq++));
            }
        }
    }
}

run page-oncall    priority=1 arrived=1
run refund-charge  priority=1 arrived=3
run escalate       priority=1 arrived=5
run send-invoice   priority=5 arrived=0
run warm-cache     priority=5 arrived=4
run rebuild-index  priority=9 arrived=2

escalate được đưa vào giữa vòng lặp ở priority 1 và vẫn chạy trước mọi job priority 5, mà không có gì phải sort lại. Một List đã sort sẽ phải chèn vào đúng index ở mỗi lần offer; heap chỉ cần vài lần so sánh.

Trộn nhiều nguồn đã sort

Ứng dụng kinh điển còn lại là k-way merge. Giữ mỗi nguồn một cursor trong heap, lấy cái nhỏ nhất ra, rồi đẩy cursor kế tiếp của nguồn đó vào. Heap không bao giờ giữ quá một entry cho mỗi nguồn, nên trộn một trăm file chỉ tốn một heap một trăm element bất kể file dài bao nhiêu.

import java.util.*;

public class MergeSorted {
    record Cursor(List<Integer> src, int idx) {
        int value() { return src.get(idx); }
        Cursor next() { return idx + 1 < src.size() ? new Cursor(src, idx + 1) : null; }
    }

    public static void main(String[] args) {
        List<List<Integer>> inputs = List.of(
            List.of(1, 4, 9, 12),
            List.of(2, 3, 10),
            List.of(5, 6, 7, 8, 11));

        PriorityQueue<Cursor> heap = new PriorityQueue<>(Comparator.comparingInt(Cursor::value));
        for (List<Integer> in : inputs) if (!in.isEmpty()) heap.offer(new Cursor(in, 0));

        List<Integer> merged = new ArrayList<>();
        while (!heap.isEmpty()) {
            Cursor c = heap.poll();
            merged.add(c.value());
            Cursor n = c.next();
            if (n != null) heap.offer(n);
        }
        System.out.println("inputs: " + inputs);
        System.out.println("merged: " + merged);
        System.out.println("heap never held more than " + inputs.size() + " cursors");
    }
}

inputs: [[1, 4, 9, 12], [2, 3, 10], [5, 6, 7, 8, 11]]
merged: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
heap never held more than 3 cursors

Lịch sử trình duyệt với hai deque

Back và forward là hai stack cộng với một giá trị hiện tại. Đi lùi thì push trang hiện tại vào stack forward và pop stack back; đi tới thì làm ngược lại; mở một trang mới thì push trang hiện tại vào stack back và xóa sạch forward. Quy tắc cuối cùng đó là cái người ta hay quên, mà nó chỉ có một dòng.

import java.util.*;

public class History {
    private final Deque<String> back = new ArrayDeque<>();
    private final Deque<String> forward = new ArrayDeque<>();
    private String current;

    History(String home) { current = home; }

    void visit(String url) {
        back.push(current);
        current = url;
        forward.clear();
    }

    void back() {
        if (back.isEmpty()) { System.out.println("  back: nothing to go back to"); return; }
        forward.push(current);
        current = back.pop();
    }

    void forward() {
        if (forward.isEmpty()) { System.out.println("  forward: nothing to go forward to"); return; }
        back.push(current);
        current = forward.pop();
    }

    @Override public String toString() {
        return String.format("back=%s current=%s forward=%s", back, current, forward);
    }

    public static void main(String[] args) {
        History h = new History("/home");
        System.out.println("start          " + h);
        h.visit("/docs");    System.out.println("visit /docs    " + h);
        h.visit("/docs/io"); System.out.println("visit /docs/io " + h);
        h.visit("/pricing"); System.out.println("visit /pricing " + h);
        h.back();            System.out.println("back           " + h);
        h.back();            System.out.println("back           " + h);
        h.forward();         System.out.println("forward        " + h);
        h.visit("/blog");    System.out.println("visit /blog    " + h);
        h.forward();
        System.out.println("forward        " + h);
    }
}

start          back=[] current=/home forward=[]
visit /docs    back=[/home] current=/docs forward=[]
visit /docs/io back=[/docs, /home] current=/docs/io forward=[]
visit /pricing back=[/docs/io, /docs, /home] current=/pricing forward=[]
back           back=[/docs, /home] current=/docs/io forward=[/pricing]
back           back=[/home] current=/docs forward=[/docs/io, /pricing]
forward        back=[/docs, /home] current=/docs/io forward=[/pricing]
visit /blog    back=[/docs/io, /docs, /home] current=/blog forward=[]
  forward: nothing to go forward to
forward        back=[/docs/io, /docs, /home] current=/blog forward=[]

Các deque in ra theo kiểu đỉnh trước, nên back=[/docs/io, /docs, /home] nghĩa là bước lùi tiếp theo sẽ về /docs/io — đúng thứ tự người dùng nhìn thấy. Tính dễ đọc đó là hệ quả trực tiếp của việc ArrayDeque iterate từ head. Cũng cấu trúc này viết bằng hai object Stack sẽ in ra ngược.

Một lịch sử undo cũng là đúng class đó với tên khác: undo và redo thay cho back và forward, cùng một biến thể có giới hạn gọi pollLast() sau mỗi lần push để bỏ mục cũ nhất khi deque vượt quá hạn mức.

Chọn cái nào

Hai quy tắc là đủ cho phần lớn trường hợp. Khai báo biến kiểu Queue hoặc Deque chứ đừng khai báo kiểu class implementation, để compiler ép giữ giới hạn. Và cứ chọn ArrayDeque trừ khi bạn có lý do cụ thể để không chọn.

FAQ

add và offer trong Queue của Java khác nhau thế nào?

Chúng thêm cùng một element vào cùng một chỗ và chỉ khác nhau ở cách báo thất bại. add(e) ném java.lang.IllegalStateException: Queue full khi queue hết chỗ; offer(e) trả về false. Trên ArrayDeque, LinkedList và PriorityQueue — đều không giới hạn — không cái nào thất bại được, nên hai method thay thế nhau được. Khác biệt chỉ có ý nghĩa với queue bị giới hạn capacity như ArrayBlockingQueue.

poll và remove trong Queue của Java khác nhau thế nào?

Cả hai đều lấy phần tử đầu ra và trả về nó. Khi queue rỗng, poll() trả về null còn remove() ném java.util.NoSuchElementException, vốn không mang message nào. Dùng poll khi rỗng là trạng thái bình thường và bạn sẽ kiểm tra kết quả; dùng remove khi rỗng nghĩa là có bug và bạn muốn chương trình dừng ngay tại đó. Cùng một sự phân đôi áp dụng cho peek và element, hai method trả về phần tử đầu mà không lấy nó ra.

Nên dùng Stack hay ArrayDeque trong Java?

ArrayDeque, trong code mới thì không có ngoại lệ. Stack extends Vector nên nó cũng là một List: get(i), set(i, e) và insertElementAt(e, i) đều chạy được trên nó và cho phép người gọi sửa vào giữa stack của bạn. Thứ tự iteration và toString() của nó là từ đáy lên đỉnh, ngược với thứ tự pop. Và mọi method đều synchronized, khiến bạn trả tiền cho một lock ở mọi lời gọi mà vẫn không làm chuỗi kiểm-tra-rồi-pop trở nên atomic. ArrayDeque với push, pop và peek không dính vấn đề nào trong số đó.

Vì sao in một PriorityQueue ra lại không thấy giá trị đã sort?

Vì toString() đi qua array bên dưới, mà array đó là một binary heap chứ không phải một dãy đã sort. Offer 5 1 8 3 9 2 7 4 6 cho ra [1, 3, 2, 4, 9, 8, 7, 5, 6]: index 0 là element nhỏ nhất, còn sau đó quy tắc duy nhất là element ở index i nhỏ hơn hoặc bằng element ở 2i+1 và 2i+2. poll() lặp lại cho ra [1, 2, 3, 4, 5, 6, 7, 8, 9]; không cách nào khác cho ra được điều đó.

Vì sao iterate một PriorityQueue lại không theo thứ tự priority?

Iterator trả về array bên dưới theo thứ tự index, và PriorityQueue nói rõ là nó không đảm bảo thứ tự duyệt nào cả. Vòng for-each, stream(), toArray() và new ArrayList<>(pq) đều cho ra cùng một bố cục heap chưa sort. Muốn đọc element theo thứ tự priority thì phải rút cạn queue bằng poll(), hoặc copy nó ra rồi sort bản copy — pq.stream().sorted().toList() chạy được, nhưng đó là một lần sort, không phải tính chất của queue.

Queue trong Java có chứa được null không?

ArrayDeque và PriorityQueue đều ném java.lang.NullPointerException khi thêm null vào. LinkedList thì cho phép, và đó là cái bẫy chứ không phải tính năng: poll() trả về null để nói "queue rỗng", nên một queue có thể chứa cả element null sẽ làm giá trị trả về trở nên nhập nhằng. Stack, vốn là một Vector, cũng nhận null.

Làm max-heap với PriorityQueue trong Java thế nào?

Truyền một comparator đảo ngược vào constructor: new PriorityQueue<>(Comparator.reverseOrder()) cho element có natural ordering, hoặc Comparator.comparingInt(Task::priority).reversed() cho type của riêng bạn. Class không đổi; chỉ có invariant lật lại, nên mỗi parent thành lớn hơn hoặc bằng các con và poll() trả về element lớn nhất. toString() thì kiểu nào cũng vẫn chưa sort.

PriorityQueue có giữ nguyên thứ tự thêm vào cho các element cùng priority không?

Không. Các trường hợp hòa nhau được phá tùy tiện theo đúng những gì thao tác heap tình cờ làm. Offer A(2) B(1) C(2) D(1) E(2) F(1) với comparator chỉ theo priority sẽ poll ra B(1) D(1) F(1) A(2) E(2) C(2) — nhóm priority 1 tình cờ giữ đúng thứ tự thêm vào còn nhóm priority 2 thì không. Nếu thứ tự đến có ý nghĩa, hãy loại bỏ khả năng hòa: gắn cho mỗi element một số thứ tự tăng dần rồi nối vào bằng thenComparingLong.

Kết luận

Bốn type trong bài này là một ý tưởng duy nhất áp dụng ở bốn mức độ. Queue lấy đi mọi vị trí trừ phần đầu. Deque trả lại đầu còn lại và không gì hơn, chừng đó đã đủ để nó vừa là stack, vừa là queue, hoặc cả hai cùng lúc. PriorityQueue thay vị trí bằng một thứ tự. Còn Stack có trước tất cả và từ bỏ giới hạn hoàn toàn, nên nó chỉ còn sống trong code cũ.

Ba điều đáng nhớ là ba điều mà runtime dạy bạn một cách đau đớn. Các method của Queue đi theo cặp, và chọn giữa poll với remove là một quyết định về việc queue rỗng là bug hay là một trạng thái. ArrayDeque từ chối null chính là để một null trả về từ poll chỉ có thể mang đúng một nghĩa. Và PriorityQueue là một heap: phần đầu của nó là element nhỏ nhất, còn mọi thứ phía sau phần đầu nằm theo một thứ tự tồn tại để lần poll sau rẻ tiền, chứ không phải để đọc.

Bài tiếp theo trong series: Iterator và ListIterator — iteration thật sự hoạt động thế nào bên dưới vòng for-each, ConcurrentModificationException thật ra phát hiện điều gì, và khác biệt giữa iterator fail-fast với fail-safe.