Stack và Queue trong Java: ArrayDeque, PriorityQueue, BlockingQueue

- Published on
- 13 mins read
Stack<Integer> stack = new Stack<>(); Dòng này chạy đúng, qua review dễ dàng, và vẫn xuất hiện đều đặn trong lời giải phỏng vấn. Có điều chính Javadoc của JDK khuyên đừng dùng nó nữa.
Hệ thống có đồ sộ hay phân tán cỡ nào thì ở tầng sâu nhất, dữ liệu vẫn chảy qua những cấu trúc cơ bản nhất: Stack và Queue. Khác biệt giữa đoạn code chạy được và code chạy tốt thường nằm ở những quyết định nhỏ như thế: tại sao dùng ArrayDeque thay vì LinkedList? Khi nào nên khóa (block) một luồng, khi nào nên để nó chạy tự do (lock-free)?
# tổng quan
Trước khi vào chi tiết, thử nhìn nhanh cách Java tổ chức các cấu trúc dữ liệu này.
- Stack (LIFO - Last In, First Out): như một chồng đĩa, đĩa đặt lên sau cùng được lấy ra đầu tiên.
- Queue (FIFO - First In, First Out): như xếp hàng, ai đến trước được phục vụ trước.
Cây gia phả (và mấy đứa con bị bỏ rơi):

# stack
# concept
push(A) → [A]
push(B) → [A, B]
push(C) → [A, B, C]
pop() → C, stack = [A, B]
peek() → B (không remove)
# implementation: ArrayDeque (recommended)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // addFirst
stack.push(2); // addFirst
stack.push(3); // addFirst
stack.peek(); // 3 (top, không remove)
stack.pop(); // 3 (remove top)
stack.isEmpty(); // false
stack.size(); // 2# tại sao KHÔNG dùng java.util.Stack
Ra đời từ tận JDK 1.0, java.util.Stack mang hai lỗi thiết kế lớn: nó kế thừa trực tiếp từ Vector nên mọi thao tác push()/pop() đều bị bọc synchronized (tốn chi phí khoá vô ích khi chạy đơn luồng), đồng thời lại phơi bày các hàm truy cập ngẫu nhiên như get(index) hay removeElementAt(index) làm hỏng hoàn toàn tính đóng gói LIFO của một ngăn xếp. Ngay trong Javadoc chính thức, đội ngũ thiết kế JDK cũng khuyên dùng ArrayDeque thay cho Stack:
// Stack extends Vector → synchronized mọi method (slow, unnecessary)
// Stack cho phép random access (get(index)) → vi phạm Stack abstraction
// Stack là class, không phải interface → tight coupling
Stack<Integer> bad = new Stack<>(); // DON'T
Deque<Integer> good = new ArrayDeque<>(); // DO# use cases
- Undo/Redo operations
- Expression evaluation (postfix, infix)
- Balanced parentheses checking
- DFS (Depth-First Search)
- Call stack simulation
- Browser back/forward
# classic problems
# balanced parentheses
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (c == ')' && top != '(') return false;
if (c == '}' && top != '{') return false;
if (c == ']' && top != '[') return false;
}
}
return stack.isEmpty();
}# min stack (o(1) getMin)
class MinStack {
private Deque<Integer> stack = new ArrayDeque<>();
private Deque<Integer> minStack = new ArrayDeque<>();
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
int val = stack.pop();
if (val == minStack.peek()) minStack.pop();
}
public int getMin() { return minStack.peek(); }
}# queue
# concept
offer(A) → [A]
offer(B) → [A, B]
offer(C) → [A, B, C]
poll() → A, queue = [B, C]
peek() → B (không remove)
# queue interface methods
| Operation | Throws Exception | Returns special value |
|---|---|---|
| Insert | add(e) → IllegalStateException | offer(e) → false |
| Remove | remove() → NoSuchElementException | poll() → null |
| Examine | element() → NoSuchElementException | peek() → null |
Best practice: Dùng offer/poll/peek (graceful handling).
# implementation: ArrayDeque
Queue<String> queue = new ArrayDeque<>();
queue.offer("A"); // enqueue
queue.offer("B");
queue.offer("C");
queue.peek(); // "A" (front, không remove)
queue.poll(); // "A" (dequeue)
queue.size(); // 2# use cases
- BFS (Breadth-First Search)
- Task scheduling
- Print queue
- Message buffering
- Rate limiting (sliding window)
# deque (double-ended queue)
Có thể add/remove ở CẢ HAI đầu. Dùng được như cả Stack và Queue.
Deque<String> deque = new ArrayDeque<>();
// As Stack (LIFO)
deque.push("A"); // addFirst
deque.pop(); // removeFirst
// As Queue (FIFO)
deque.offer("A"); // addLast
deque.poll(); // removeFirst
// Double-ended operations
deque.addFirst("A");
deque.addLast("B");
deque.peekFirst(); // "A"
deque.peekLast(); // "B"
deque.pollFirst(); // "A"
deque.pollLast(); // "B"# ArrayDeque internal
Sở dĩ ArrayDeque vừa thêm/bớt ở cả hai đầu trong thời gian O(1) (amortized) vừa thân thiện với CPU cache là nhờ cấu trúc mảng vòng (circular array) kết hợp hai con trỏ head và tail. Hình dưới minh họa cách addFirst (thêm vào đầu) và addLast (thêm vào cuối) dịch chuyển con trỏ trên một mảng 8 phần tử:

Ở nửa trên của hình là trạng thái mảng vật lý ban đầu với Head = 5 và Tail = 2, chứa 5 phần tử [A, B, C, D, E] nối vòng từ cuối mảng (chỉ số 5, 6, 7) quay lại đầu mảng (chỉ số 0, 1). Ở nửa dưới, khi gọi addFirst (cột trái), ArrayDeque lùi con trỏ head về trước một ô theo công thức (5 - 1) & 7 = 4 rồi mới đặt phần tử mới vào ô số 4 (lúc này Head mới ở 4, Tail giữ nguyên ở 2). Ngược lại, khi gọi addLast (cột phải), nó đặt phần tử mới ngay vào vị trí Tail hiện tại (ô số 2), sau đó mới nhích tail lên một ô theo công thức (2 + 1) & 7 = 3.
Một chi tiết thú vị khi đọc source code qua các bản JDK: ở Java 8, kích thước mảng của ArrayDeque luôn bị ép là lũy thừa của 2 (power of 2) để dùng phép toán bit & (length - 1) thay cho phép chia lấy dư %, và cứ khi mảng đầy (head == tail) thì nhân đôi kích thước rồi copy sang mảng mới.
Nhưng từ Java 9 trở đi, ArrayDeque được viết lại: kích thước mảng không còn bắt buộc là lũy thừa của 2 nữa, việc quay vòng con trỏ chỉ dùng câu lệnh so sánh đơn giản (if (++i >= length) i = 0) thay vì AND. Khi đầy, mảng nhỏ (dưới 64) tăng khoảng gấp đôi, còn mảng lớn chỉ tăng thêm 50% để đỡ tốn bộ nhớ (chẳng hạn trên JDK 21, new ArrayDeque<>() lần lượt có sức chứa mảng ngầm là 17, 36, 74, 111, 166...). Ý tưởng mảng vòng thì vẫn y như hình.
Ngoài ra, ArrayDeque cấm tuyệt đối việc chèn phần tử null, vì bản thân giá trị null đã được dùng nội bộ để đánh dấu các ô trống trong mảng và làm giá trị trả về của poll() khi hàng đợi rỗng.
# ArrayDeque vs LinkedList (as Deque)
| Tiêu chí | ArrayDeque | LinkedList |
|---|---|---|
| Memory | Compact (array) | ~24 bytes/node (compressed oops), 40 nếu tắt |
| Cache | Excellent (contiguous) | Poor (scattered) |
| addFirst/addLast | O(1) amortized | O(1) |
| Null elements | Not allowed | Allowed |
| As List | Not a List | Implements List |
| Thread-safe | No | No |
Nhờ các phần tử nằm liền kề nhau trên một dải bộ nhớ liên tục (contiguous array), CPU nạp một Cache Line 64-byte là kéo lên được cả chục tham chiếu của ArrayDeque, trong khi mỗi mắt xích Node của LinkedList lại nằm rải rác khắp Heap và tốn thêm 24–40 bytes header/con trỏ. Vì vậy, ArrayDeque nhanh hơn LinkedList ở hầu hết các thao tác Stack/Queue thông thường.
# PriorityQueue (min-heap)
Elements được dequeue theo priority (smallest first by default).
// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5); minHeap.offer(1); minHeap.offer(3);
minHeap.poll(); // 1 (smallest)
minHeap.poll(); // 3
minHeap.poll(); // 5
// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3);
maxHeap.poll(); // 5 (largest)
// Custom priority
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
Comparator.comparingInt(Task::getPriority)
);# internal: binary heap (array-based)
Array: [1, 3, 5, 7, 4, 8, 6]
Tree representation:
1
/ \
3 5
/ \ / \
7 4 8 6
Parent of i: (i - 1) / 2
Left child of i: 2*i + 1
Right child of i: 2*i + 2
# complexity
| Operation | Complexity |
|---|---|
| offer(e) | O(log n), sift up |
| poll() | O(log n), sift down |
| peek() | O(1) |
| remove(Object) | O(n), linear search + sift |
| contains(Object) | O(n) |
# use cases
- Dijkstra's shortest path
- Task scheduling by priority
- Merge K sorted lists
- Top-K elements
- Median finding (2 heaps)
# top-k pattern
// Find K largest elements → use min-heap of size K
public List<Integer> topK(int[] nums, int 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); // K largest remain (thứ tự trong heap, chưa sort)
}# blockingqueue (thread-safe, producer-consumer)
Blocking operations: wait khi queue empty (take) hoặc full (put).
BlockingQueue<Task> queue = new ArrayBlockingQueue<>(100); // bounded
// Producer thread
queue.put(task); // blocks if full
// Consumer thread
Task task = queue.take(); // blocks if empty# implementations
| Implementation | Bounded | Ordering | Use case |
|---|---|---|---|
| ArrayBlockingQueue | Yes (fixed) | FIFO | Bounded producer-consumer |
| LinkedBlockingQueue | Optional | FIFO | Unbounded (careful!) or bounded |
| PriorityBlockingQueue | No | Priority | Priority-based processing |
| DelayQueue | No | Delay time | Scheduled tasks, retry with delay |
| SynchronousQueue | 0 capacity | N/A | Direct handoff (no buffering) |
# producer-consumer pattern
// Shared queue
BlockingQueue<Order> orderQueue = new ArrayBlockingQueue<>(1000);
// Producer
class OrderProducer implements Runnable {
public void run() {
try {
while (!Thread.currentThread().isInterrupted()) {
Order order = receiveOrder();
orderQueue.put(order); // blocks if queue full
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt(); // giữ cờ interrupt để thread dừng đúng cách
}
}
}
// Consumer
class OrderProcessor implements Runnable {
public void run() {
try {
while (!Thread.currentThread().isInterrupted()) {
Order order = orderQueue.take(); // blocks if queue empty
processOrder(order);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
// Start multiple consumers
ExecutorService executor = Executors.newFixedThreadPool(5);
executor.submit(new OrderProducer());
for (int i = 0; i < 4; i++) {
executor.submit(new OrderProcessor());
}put() và take() ném InterruptedException (checked exception), nên run() bắt buộc phải xử lý. Bắt rồi gọi lại interrupt() là cách chuẩn: executor.shutdownNow() interrupt các thread, consumer đang chờ take() sẽ thoát vòng lặp thay vì treo mãi.
# DelayQueue
class DelayedTask implements Delayed {
private final long executeAt;
private final Runnable task;
public DelayedTask(Runnable task, long delayMs) {
this.task = task;
this.executeAt = System.currentTimeMillis() + delayMs;
}
@Override
public long getDelay(TimeUnit unit) {
return unit.convert(executeAt - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
@Override
public int compareTo(Delayed other) {
return Long.compare(this.getDelay(TimeUnit.MILLISECONDS),
other.getDelay(TimeUnit.MILLISECONDS));
}
}
DelayQueue<DelayedTask> delayQueue = new DelayQueue<>();
delayQueue.put(new DelayedTask(() -> retry(), 5000)); // execute after 5s
DelayedTask task = delayQueue.take(); // blocks until delay expires# ConcurrentLinkedQueue (lock-free)
Khi cần một hàng đợi chia sẻ giữa nhiều luồng với thông lượng rất cao mà không muốn các luồng bị đình chỉ (park/unpark) vì chờ khoá mutex, ConcurrentLinkedQueue là lựa chọn hợp lý. Nó dựa trên thuật toán non-blocking (lock-free) của Michael & Scott, sử dụng lệnh nguyên tử CAS (Compare-And-Swap) ở tầng CPU.
ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();
queue.offer("A"); // never blocks, never fails
queue.poll(); // null if empty (never blocks)Vì là cấu trúc không khoá và không giới hạn kích thước (unbounded), hàm offer() luôn thành công ngay lập tức còn poll() trả về null ngay nếu hàng đợi trống chứ không bao giờ chặn luồng gọi. Tuy nhiên, có hai cái bẫy lớn khi đưa ConcurrentLinkedQueue lên production: một là vì không có giới hạn sức chứa, nếu tốc độ đẩy vào (producer) nhanh hơn tốc độ lấy ra (consumer) trong thời gian dài thì hàng đợi sẽ phình to tới khi nổ OutOfMemoryError; hai là hàm .size() không phải O(1) mà phải duyệt tuần tự qua toàn bộ danh sách liên kết với độ phức tạp O(n), và kết quả đếm được lúc đang có nhiều luồng ghi song song cũng chỉ mang tính xấp xỉ. Do đó, nếu chỉ cần kiểm tra hàng đợi có phần tử nào không, hãy luôn gọi queue.isEmpty() (O(1)) thay vì queue.size() > 0.
# so sánh tổng hợp
| Implementation | Thread-safe | Bounded | Blocking | Null | Best for |
|---|---|---|---|---|---|
| ArrayDeque | No | No (grows) | No | No | Stack/Queue single-thread |
| LinkedList | No | No | No | Yes | Deque + List combo |
| PriorityQueue | No | No | No | No | Priority ordering |
| ArrayBlockingQueue | Yes | Yes | Yes | No | Bounded producer-consumer |
| LinkedBlockingQueue | Yes | Optional | Yes | No | Flexible producer-consumer |
| ConcurrentLinkedQueue | Yes | No | No | No | High-throughput non-blocking |
| SynchronousQueue | Yes | 0 | Yes | No | Direct handoff |
# interview tips
- Stack: dùng ArrayDeque, KHÔNG dùng java.util.Stack (legacy, synchronized)
- Queue: dùng ArrayDeque (single-thread) hoặc BlockingQueue (multi-thread)
- ArrayDeque: circular array, O(1) amortized, no null, faster than LinkedList
- PriorityQueue: binary heap, O(log n) offer/poll, NOT thread-safe
- BlockingQueue: put() blocks when full, take() blocks when empty
- ConcurrentLinkedQueue: CAS-based, non-blocking, size() is O(n)
- Producer-Consumer: BlockingQueue là standard pattern
- DelayQueue: scheduled retry, delayed execution
- SynchronousQueue: zero capacity, direct handoff between threads
Chỉ là những ghi chép cá nhân với hy vọng mang lại chút giá trị. Nếu thấy hữu ích, đừng ngại chia sẻ cho bạn bè & đồng nghiệp nhé!
Happy coding 😎 👍🏻 🚀 🔥.
On this page
- # tổng quan
- # stack
- # concept
- # implementation: ArrayDeque (recommended)
- # tại sao KHÔNG dùng java.util.Stack
- # use cases
- # classic problems
- # balanced parentheses
- # min stack (o(1) getMin)
- # queue
- # concept
- # queue interface methods
- # implementation: ArrayDeque
- # use cases
- # deque (double-ended queue)
- # ArrayDeque internal
- # ArrayDeque vs LinkedList (as Deque)
- # PriorityQueue (min-heap)
- # internal: binary heap (array-based)
- # complexity
- # use cases
- # top-k pattern
- # blockingqueue (thread-safe, producer-consumer)
- # implementations
- # producer-consumer pattern
- # DelayQueue
- # ConcurrentLinkedQueue (lock-free)
- # so sánh tổng hợp
- # interview tips