Skip to content
TungDaDev's Blog

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

Stack queue.webp
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):

family-tree

# stack

# concept

push(A) → [A]
push(B) → [A, B]
push(C) → [A, B, C]
pop()   → C, stack = [A, B]
peek()  → B (không remove)
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

OperationThrows ExceptionReturns special value
Insertadd(e) → IllegalStateExceptionoffer(e) → false
Removeremove() → NoSuchElementExceptionpoll() → null
Examineelement() → NoSuchElementExceptionpeek() → 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ử:

array-deque

Ở 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íArrayDequeLinkedList
MemoryCompact (array)~24 bytes/node (compressed oops), 40 nếu tắt
CacheExcellent (contiguous)Poor (scattered)
addFirst/addLastO(1) amortizedO(1)
Null elementsNot allowedAllowed
As ListNot a ListImplements List
Thread-safeNoNo

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

OperationComplexity
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

ImplementationBoundedOrderingUse case
ArrayBlockingQueueYes (fixed)FIFOBounded producer-consumer
LinkedBlockingQueueOptionalFIFOUnbounded (careful!) or bounded
PriorityBlockingQueueNoPriorityPriority-based processing
DelayQueueNoDelay timeScheduled tasks, retry with delay
SynchronousQueue0 capacityN/ADirect 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

ImplementationThread-safeBoundedBlockingNullBest for
ArrayDequeNoNo (grows)NoNoStack/Queue single-thread
LinkedListNoNoNoYesDeque + List combo
PriorityQueueNoNoNoNoPriority ordering
ArrayBlockingQueueYesYesYesNoBounded producer-consumer
LinkedBlockingQueueYesOptionalYesNoFlexible producer-consumer
ConcurrentLinkedQueueYesNoNoNoHigh-throughput non-blocking
SynchronousQueueYes0YesNoDirect 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 😎 👍🏻 🚀 🔥.