Queue và Deque

Mục tiêu bài học

Sau bài này, bạn sẽ:

• Hiểu Queue (FIFO) và Deque (double-ended queue) interfaces
• Phân biệt hai sets methods: throw exception (add/remove/element) vs return special value (offer/poll/peek)
• So sánh PriorityQueue (min-heap, O(log n)), ArrayDeque (fastest), LinkedList (slower)
• Sử dụng ArrayDeque cho Stack và Queue thay vì Stack class (legacy)
• Áp dụng cho BFS, task scheduling, sliding window, và expression evaluation

Bài trước: Map Interface — Đã học về Map với HashMap, LinkedHashMap, TreeMap. Bài này sẽ tìm hiểu Queue (FIFO) và Deque (double-ended queue).

Queue Interface

Queue là một interface đại diện cho cấu trúc dữ liệu FIFO (First In First Out) - phần tử vào trước sẽ ra trước.

Đặc điểm

• FIFO order: First In First Out
• Head & Tail: Có đầu (head) và đuôi (tail)
• Two sets of methods: Throw exception vs Return special value

public interface Queue<E> extends Collection<E> {
    // Throw exception nếu thất bại
    boolean add(E e);        // Thêm vào tail, throw exception nếu full
    E remove();              // Lấy và xóa head, throw exception nếu empty
    E element();             // Xem head, throw exception nếu empty

    // Return special value nếu thất bại
    boolean offer(E e);      // Thêm vào tail, return false nếu full
    E poll();                // Lấy và xóa head, return null nếu empty
    E peek();                // Xem head, return null nếu empty
}

Queue Methods - Throw Exception vs Return Special Value

Operation	Throw Exception	Return Special Value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

offer/poll vs add/remove Comparison Diagram

Recommendation: Dùng offer/poll/peek để xử lý failure gracefully (return false/null) thay vì throw exception.

import java.util.*;

public class QueueMethodsDemo {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // add() vs offer()
        queue.add("First");      // OK
        queue.offer("Second");   // OK
        // Với bounded queue đầy:
        // queue.add("X");       // IllegalStateException
        // queue.offer("X");     // return false

        // remove() vs poll()
        String item1 = queue.remove();  // "First"
        String item2 = queue.poll();    // "Second"
        // String item3 = queue.remove();  // NoSuchElementException (empty)
        String item3 = queue.poll();    // null (empty)

        // element() vs peek()
        queue.offer("Test");
        // String head1 = queue.element();  // "Test"
        String head2 = queue.peek();     // "Test"
        queue.poll();  // Remove "Test"
        // String head3 = queue.element();  // NoSuchElementException (empty)
        String head4 = queue.peek();     // null (empty)
    }
}

offer/poll vs add/remove - Detailed Comparison Table

Operation	Exception Methods	Return Special Value	Behavior on Failure
Insert	add(e)	offer(e)	add: IllegalStateException offer: return false
Remove	remove()	poll()	remove: NoSuchElementException poll: return null
Examine	element()	peek()	element: NoSuchElementException peek: return null

Queue<String> queue = new LinkedList<>();

// INSERT
queue.add("A");    // ✅ OK
queue.offer("B");  // ✅ OK, return true

// Với bounded queue đầy:
// queue.add("X");    // ❌ IllegalStateException
// queue.offer("X");  // ✅ return false

// REMOVE
String item1 = queue.remove();  // "A", ❌ throw exception if empty
String item2 = queue.poll();    // "B", ✅ return null if empty

queue.clear();  // Empty queue

// String item3 = queue.remove();  // ❌ NoSuchElementException
String item3 = queue.poll();    // ✅ null

// EXAMINE
queue.offer("Test");

// String head1 = queue.element();  // "Test", ❌ throw exception if empty
String head2 = queue.peek();     // "Test", ✅ return null if empty

queue.poll();  // Remove "Test", queue is empty

// String head3 = queue.element();  // ❌ NoSuchElementException
String head4 = queue.peek();     // ✅ null

Khi nào dùng phương thức nào?

• Dùng offer/poll/peek: Khi muốn xử lý failure gracefully (return false/null)
• Dùng add/remove/element: Khi failure là exceptional case (throw exception)

Trong hầu hết trường hợp, khuyến nghị dùng offer/poll/peek để tránh exception.

LinkedList as Queue

LinkedList implements cả List và Deque (extends Queue), nên có thể dùng làm Queue.

import java.util.*;

public class LinkedListQueueDemo {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // Enqueue (thêm vào tail)
        queue.offer("Customer 1");
        queue.offer("Customer 2");
        queue.offer("Customer 3");

        System.out.println("Queue: " + queue);
        // [Customer 1, Customer 2, Customer 3]

        // Peek (xem head)
        System.out.println("Next customer: " + queue.peek());
        // Customer 1

        // Dequeue (lấy và xóa head)
        while (!queue.isEmpty()) {
            String customer = queue.poll();
            System.out.println("Serving: " + customer);
        }
        // Output:
        // Serving: Customer 1
        // Serving: Customer 2
        // Serving: Customer 3
    }
}

PriorityQueue - Min-Heap

PriorityQueue là một Queue đặc biệt mà các phần tử được xử lý theo priority (ưu tiên), không theo FIFO.

PriorityQueue is Array-Based Heap (NOT Tree!)

Nhiều người nghĩ PriorityQueue dùng tree structure, nhưng thực tế nó dùng array-based binary heap:

// Simplified PriorityQueue internal structure
public class PriorityQueue<E> {
    private Object[] queue;  // Array (not tree nodes!)
    private int size = 0;

    // Heap property:
    // Parent index: (i - 1) / 2
    // Left child: 2 * i + 1
    // Right child: 2 * i + 2
}

Binary Min-Heap structure in array:

Array: [1, 2, 5, 8, 3, 9, 7]
Index:  0  1  2  3  4  5  6

Tree visualization:
        1 (index 0)
       / \
      2   5 (index 1, 2)
     / \ / \
    8  3 9  7 (index 3, 4, 5, 6)

Parent of index i: (i-1)/2
Left child of i: 2*i+1
Right child of i: 2*i+2

Heap operations:

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);  // [5]
pq.offer(2);  // [2, 5] - bubble up: 2 < 5, swap
pq.offer(8);  // [2, 5, 8]
pq.offer(1);  // [1, 2, 8, 5] - bubble up: 1 < 2, swap positions

// Internal array: [1, 2, 8, 5]
//        1
//       / \
//      2   8
//     /
//    5

System.out.println(pq.poll());  // 1 - remove root, heapify down
// Internal array: [2, 5, 8]

💡 Cách nhớ: Array-based heap = "Cây ảo trong mảng"

PriorityQueue lưu "cây" trong mảng bằng công thức toán học. Không có node objects hay pointers! Giống như lưu cây gia phả trong danh sách: con trái của người thứ i là người thứ 2i+1, con phải là 2i+2.

Đặc điểm

• Min-heap by default: Phần tử nhỏ nhất được ưu tiên (natural order)
• Array-based: Internal array, không phải tree nodes
• Not FIFO: Không theo thứ tự FIFO
• No null: Không chấp nhận null
• Not thread-safe
• O(log n) cho add, poll (heap operations)
• O(1) cho peek

import java.util.*;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // Min-heap (natural order)
        Queue<Integer> minHeap = new PriorityQueue<>();

        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);
        minHeap.offer(9);

        // Poll theo thứ tự tăng dần (min first)
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }
        // Output: 1 2 5 8 9

        System.out.println();

        // Max-heap (reverse order)
        Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(8);
        maxHeap.offer(1);
        maxHeap.offer(9);

        // Poll theo thứ tự giảm dần (max first)
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " ");
        }
        // Output: 9 8 5 2 1
    }
}

Custom Priority với Comparator

class Task {
    String name;
    int priority;  // 1 = high, 5 = low

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public String toString() {
        return name + "(P" + priority + ")";
    }
}

public class TaskScheduler {
    public static void main(String[] args) {
        // Sort by priority (low number = high priority)
        Queue<Task> taskQueue = new PriorityQueue<>(
            Comparator.comparingInt(t -> t.priority)
        );

        taskQueue.offer(new Task("Write report", 3));
        taskQueue.offer(new Task("Fix bug", 1));      // High priority
        taskQueue.offer(new Task("Update docs", 5));
        taskQueue.offer(new Task("Review code", 2));

        System.out.println("Tasks by priority:");
        while (!taskQueue.isEmpty()) {
            System.out.println(taskQueue.poll());
        }
        // Output:
        // Fix bug(P1)
        // Review code(P2)
        // Write report(P3)
        // Update docs(P5)
    }
}

PriorityQueue Applications

// Top K elements
public class TopKElements {
    public static List<Integer> findTopK(int[] nums, int k) {
        // Min-heap với size k
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();  // Remove smallest
            }
        }

        return new ArrayList<>(minHeap);
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
        List<Integer> topK = findTopK(nums, 3);
        System.out.println("Top 3: " + topK);  // [5, 6, 9]
    }
}

Deque Interface

Deque (Double Ended Queue - phát âm "deck") là một Queue mà có thể thêm/xóa từ cả hai đầu.

Đặc điểm

• Double-ended: Thao tác ở cả head và tail
• Can be used as Stack or Queue
• More flexible than Queue

public interface Deque<E> extends Queue<E> {
    // First element (head)
    void addFirst(E e);
    boolean offerFirst(E e);
    E removeFirst();
    E pollFirst();
    E getFirst();
    E peekFirst();

    // Last element (tail)
    void addLast(E e);
    boolean offerLast(E e);
    E removeLast();
    E pollLast();
    E getLast();
    E peekLast();

    // Stack operations
    void push(E e);    // = addFirst()
    E pop();           // = removeFirst()
}

Deque Methods Summary

Operation	Head - Exception	Head - Special	Tail - Exception	Tail - Special
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

ArrayDeque - Fastest Deque

ArrayDeque là implementation hiệu quả nhất của Deque, dựa trên resizable array.

ArrayDeque Internal Circular Array

ArrayDeque sử dụng circular array với head và tail pointers:

// Simplified ArrayDeque structure
public class ArrayDeque<E> {
    private Object[] elements;
    private int head;  // Index of first element
    private int tail;  // Index of next element to add
}

Circular array visualization:

Initial: [null, null, null, null] (capacity=4)
         head=0, tail=0

After addLast("A"):
[A, null, null, null]
 ↑head           ↑tail

After addLast("B"):
[A, B, null, null]
 ↑head        ↑tail

After addFirst("Z"):
[A, B, null, Z]
 ↑head   ↑tail↑head moves to end (circular!)

After addLast("C"):
[A, B, C, Z]
 ↑head  ↑tail (full, needs resize)

Resize (double): [Z, A, B, C, null, null, null, null]
                  ↑head     ↑tail

Circular wrap-around:

ArrayDeque<String> deque = new ArrayDeque<>(4);  // Small capacity for demo
deque.addLast("A");
deque.addLast("B");
deque.addFirst("Z");  // Wraps to end of array!
deque.addFirst("Y");  // Wraps to end-1

// Internal array: [A, B, null, Y, Z]
//                       ↑tail  ↑head
// Logical order: [Z, Y, A, B]

💡 Cách nhớ: Circular array = "Vòng tròn"

ArrayDeque array giống vòng tròn: khi đến cuối array, nó quay về đầu. Head và tail có thể ở bất kỳ đâu trong array. Giống như kim đồng hồ - sau 12 giờ là 1 giờ, không phải 13!

Đặc điểm

• Resizable circular array: Dynamic array với head/tail pointers
• Faster than LinkedList: Tốt hơn LinkedList cho cả Stack và Queue operations
• No null: Không chấp nhận null
• Not thread-safe
• O(1) amortized cho add/remove ở cả hai đầu

import java.util.*;

public class ArrayDequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Thêm vào head
        deque.addFirst("B");
        deque.addFirst("A");

        // Thêm vào tail
        deque.addLast("C");
        deque.addLast("D");

        System.out.println("Deque: " + deque);  // [A, B, C, D]

        // Xem head và tail
        System.out.println("First: " + deque.peekFirst());  // A
        System.out.println("Last: " + deque.peekLast());    // D

        // Xóa từ head
        System.out.println("Remove first: " + deque.pollFirst());  // A

        // Xóa từ tail
        System.out.println("Remove last: " + deque.pollLast());    // D

        System.out.println("Deque: " + deque);  // [B, C]
    }
}

ArrayDeque as Queue (FIFO)

public class DequeAsQueue {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();

        // Enqueue (addLast)
        queue.offerLast("First");
        queue.offerLast("Second");
        queue.offerLast("Third");

        // Dequeue (removeFirst)
        while (!queue.isEmpty()) {
            System.out.println(queue.pollFirst());
        }
        // Output:
        // First
        // Second
        // Third
    }
}

ArrayDeque as Stack (LIFO)

Quan trọng: push/pop/peek của Deque hoạt động ở FIRST (head), không phải last!

Deque as Stack vs Queue Diagram

Key difference:

• Stack: Push/pop at FIRST (head) → LIFO
• Queue: Offer at LAST (tail), poll at FIRST (head) → FIFO

public class DequeAsStack {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();

        // Push = addFirst (thêm vào HEAD, không phải tail!)
        stack.push("First");   // = addFirst()
        stack.push("Second");
        stack.push("Third");

        // Stack: [Third, Second, First]
        //         ↑HEAD (top of stack)

        // Pop = removeFirst (xóa từ HEAD)
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());  // = removeFirst()
        }
        // Output:
        // Third   ← top of stack
        // Second
        // First   ← bottom of stack

        // peek() cũng xem HEAD
        stack.push("A");
        stack.push("B");
        System.out.println(stack.peek());  // "B" (HEAD)
    }
}

Deque as Stack - push/pop use FIRST!

Nhiều người nghĩ stack "push lên top", nên push() sẽ dùng addLast(). SAI!

Deque.push() = addFirst() (thêm vào HEAD) Deque.pop() = removeFirst() (xóa từ HEAD) Deque.peek() = peekFirst() (xem HEAD)

Lý do: HEAD của Deque được coi là "top of stack". Push/pop luôn hoạt động ở HEAD (first), không phải tail (last).

Deque<String> stack = new ArrayDeque<>();
stack.push("A");  // addFirst: [A]
stack.push("B");  // addFirst: [B, A] ← B ở HEAD (top)
stack.push("C");  // addFirst: [C, B, A] ← C ở HEAD (top)

stack.pop();  // removeFirst → "C"
stack.pop();  // removeFirst → "B"

Stack Class (Legacy) vs Deque

Java có class Stack từ Java 1.0, nhưng hiện nay không khuyến khích dùng vì nhiều lý do:

// ❌ KHÔNG KHUYẾN KHÍCH: Stack class (legacy)
Stack<String> stack = new Stack<>();
stack.push("A");
stack.push("B");
stack.pop();

// ✅ KHUYẾN KHÍCH: Deque interface với ArrayDeque
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
stack.pop();

Tại sao không dùng Stack class?

Lý do	Giải thích
Extends Vector	Vector là synchronized (chậm), thường không cần
Legacy design	Thiết kế cũ, không consistent với Collections Framework
Exposes internal	Có thể truy cập phần tử ở giữa stack (vi phạm stack principle)
Performance	ArrayDeque nhanh hơn

Quy tắc vàng

Luôn dùng Deque (ArrayDeque) thay vì Stack class!

// Stack operations với Deque
Deque<String> stack = new ArrayDeque<>();
stack.push("item");    // Push
String top = stack.pop();    // Pop
String peek = stack.peek();  // Peek

Min-Heap Array Representation Diagram

ArrayDeque Circular Array Diagram

OCP Traps - Bẫy thường gặp trong kỳ thi

🔥 Bẫy 1: PriorityQueue forbids null

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(null);  // ❌ NullPointerException!

// PriorityQueue cần compare elements → null không thể compare
// LinkedList allows null
Queue<Integer> linkedList = new LinkedList<>();
linkedList.offer(null);  // ✅ OK

🔥 Bẫy 2: PriorityQueue.iterator() KHÔNG trả về sorted order!

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(8);
pq.offer(1);

// Iterator KHÔNG guarantee sorted order!
for (Integer num : pq) {
    System.out.print(num + " ");
}
// Output có thể là: 1 2 8 5 (KHÔNG sorted!)

// CHỈ poll() guarantee min element
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
}
// Output: 1 2 5 8 (sorted!)

Giải thích: Iterator chỉ traverse internal array, không poll elements. Array không phải sorted array, chỉ đảm bảo heap property (parent < children).

🔥 Bẫy 3: ArrayDeque forbids null (unlike LinkedList)

// ArrayDeque: null forbidden
Deque<String> arrayDeque = new ArrayDeque<>();
arrayDeque.offer(null);  // ❌ NullPointerException!

// LinkedList: null allowed
Deque<String> linkedList = new LinkedList<>();
linkedList.offer(null);  // ✅ OK

🔥 Bẫy 4: Deque.push() uses FIRST, not LAST!

Deque<String> stack = new ArrayDeque<>();
stack.push("A");  // addFirst: [A]
stack.push("B");  // addFirst: [B, A]
stack.push("C");  // addFirst: [C, B, A]

// HEAD (index 0) là top of stack!
System.out.println(stack.getFirst());  // "C"
System.out.println(stack.getLast());   // "A"

stack.pop();  // removeFirst → "C" (from HEAD, not tail!)

Ví dụ thực hành

Ví dụ 1: Task Scheduling với PriorityQueue

class Task implements Comparable<Task> {
    String name;
    int priority;
    long timestamp;

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
        this.timestamp = System.currentTimeMillis();
    }

    @Override
    public int compareTo(Task other) {
        // Sort by priority first, then by timestamp
        int priorityCompare = Integer.compare(this.priority, other.priority);
        if (priorityCompare != 0) return priorityCompare;
        return Long.compare(this.timestamp, other.timestamp);
    }

    @Override
    public String toString() {
        return name + "(P" + priority + ")";
    }
}

public class TaskScheduler {
    private Queue<Task> taskQueue = new PriorityQueue<>();

    public void scheduleTask(String name, int priority) {
        taskQueue.offer(new Task(name, priority));
        System.out.println("Scheduled: " + name + " with priority " + priority);
    }

    public void processTasks() {
        System.out.println("\nProcessing tasks:");
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();
            System.out.println("Processing: " + task);
            // Simulate work
            try { Thread.sleep(100); } catch (InterruptedException e) {}
        }
    }

    public static void main(String[] args) {
        TaskScheduler scheduler = new TaskScheduler();

        scheduler.scheduleTask("Send email", 3);
        scheduler.scheduleTask("Fix critical bug", 1);
        scheduler.scheduleTask("Write documentation", 5);
        scheduler.scheduleTask("Code review", 2);
        scheduler.scheduleTask("Deploy hotfix", 1);

        scheduler.processTasks();
    }
}

Ví dụ 2: Undo System với Deque (Stack)

class TextEditor {
    private StringBuilder content = new StringBuilder();
    private Deque<String> undoStack = new ArrayDeque<>();
    private Deque<String> redoStack = new ArrayDeque<>();

    public void type(String text) {
        undoStack.push(content.toString());  // Save current state
        content.append(text);
        redoStack.clear();  // Clear redo history
        System.out.println("Content: " + content);
    }

    public void undo() {
        if (undoStack.isEmpty()) {
            System.out.println("Nothing to undo");
            return;
        }
        redoStack.push(content.toString());
        content = new StringBuilder(undoStack.pop());
        System.out.println("Undo -> Content: " + content);
    }

    public void redo() {
        if (redoStack.isEmpty()) {
            System.out.println("Nothing to redo");
            return;
        }
        undoStack.push(content.toString());
        content = new StringBuilder(redoStack.pop());
        System.out.println("Redo -> Content: " + content);
    }

    public static void main(String[] args) {
        TextEditor editor = new TextEditor();

        editor.type("Hello");
        editor.type(" World");
        editor.type("!");

        editor.undo();  // Remove "!"
        editor.undo();  // Remove " World"
        editor.redo();  // Add back " World"
    }
}

Ví dụ 3: Sliding Window Maximum với Deque

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k == 0) return new int[0];

        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();  // Store indices

        for (int i = 0; i < nums.length; i++) {
            // Remove elements out of window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove smaller elements (they won't be max)
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // Add to result
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        int[] result = maxSlidingWindow(nums, k);
        System.out.println("Sliding window max: " + Arrays.toString(result));
        // Output: [3, 3, 5, 5, 6, 7]
    }
}

Ví dụ 4: Browser History với Deque

class BrowserHistory {
    private Deque<String> backStack = new ArrayDeque<>();
    private Deque<String> forwardStack = new ArrayDeque<>();
    private String currentPage;

    public BrowserHistory(String homepage) {
        currentPage = homepage;
    }

    public void visit(String url) {
        if (currentPage != null) {
            backStack.push(currentPage);
        }
        currentPage = url;
        forwardStack.clear();  // Clear forward history
        System.out.println("Visited: " + currentPage);
    }

    public void back() {
        if (backStack.isEmpty()) {
            System.out.println("No previous page");
            return;
        }
        forwardStack.push(currentPage);
        currentPage = backStack.pop();
        System.out.println("Back to: " + currentPage);
    }

    public void forward() {
        if (forwardStack.isEmpty()) {
            System.out.println("No forward page");
            return;
        }
        backStack.push(currentPage);
        currentPage = forwardStack.pop();
        System.out.println("Forward to: " + currentPage);
    }

    public static void main(String[] args) {
        BrowserHistory browser = new BrowserHistory("google.com");

        browser.visit("facebook.com");
        browser.visit("youtube.com");
        browser.visit("linkedin.com");

        browser.back();     // youtube.com
        browser.back();     // facebook.com
        browser.forward();  // youtube.com
        browser.visit("twitter.com");  // Clear forward history
        browser.forward();  // No forward page
    }
}

Performance Comparison

Operation	LinkedList	ArrayDeque	PriorityQueue
addFirst/offerFirst	O(1)	O(1) amortized	N/A
addLast/offerLast	O(1)	O(1) amortized	N/A
removeFirst/pollFirst	O(1)	O(1)	N/A
removeLast/pollLast	O(1)	O(1)	N/A
add/offer	O(1)	O(1) amortized	O(log n)
remove/poll	O(1)	O(1)	O(log n)
peek	O(1)	O(1)	O(1)
Memory overhead	High (nodes)	Low (array)	Medium (heap)

Khi nào dùng gì?

• ArrayDeque: Default choice cho Stack và Queue (nhanh nhất)
• LinkedList: Khi cần List interface cùng lúc với Deque
• PriorityQueue: Khi cần xử lý theo priority, không theo FIFO

Bài tập thực hành

Bài 1: Validate Parentheses

Viết method boolean isValid(String s) kiểm tra một string có parentheses hợp lệ không. Ví dụ: "()[]{}"→ true, "([)]"→ false. Dùng Stack (Deque).

Bài 2: Recent Counter

Implement class RecentCounter đếm số requests trong 3000ms gần nhất. Dùng Queue.

Bài 3: Kth Largest Element

Viết method int findKthLargest(int[] nums, int k) tìm phần tử lớn thứ k. Dùng PriorityQueue.

Bài 4: Design Circular Queue

Implement Circular Queue với capacity cố định bằng array.

Tổng kết

Trong bài này, bạn đã học:

• Queue: FIFO, hai sets methods (throw exception vs return special value)
• PriorityQueue: Min-heap mặc định, xử lý theo priority (O(log n))
• Deque: Double-ended queue, có thể dùng làm Stack hoặc Queue
• ArrayDeque: Implementation nhanh nhất, khuyến khích dùng thay vì Stack class và LinkedList cho queue/stack operations
• LinkedList: Có thể dùng làm Queue/Deque nhưng chậm hơn ArrayDeque
• Stack class: Legacy, không khuyến khích dùng

Quy tắc vàng:

1. Cần Stack → Dùng ArrayDeque (push/pop)
2. Cần Queue (FIFO) → Dùng ArrayDeque (offer/poll)
3. Cần priority → Dùng PriorityQueue
4. Không bao giờ dùng Stack class!

Đọc thêm

• Queue Interface - Oracle
• Deque Interface - Oracle
• PriorityQueue API - Oracle