stack-queue

Dẫu hệ thống của bạn có đồ sộ nhường nào, kiến trúc có phân tán ra sao, thì ở tầng sâu nhất, dữ liệu vẫn luôn chảy qua những cấu trúc nguyên thủy nhất: Stack và Queue.

Sự khác biệt giữa một đoạn code chạy được và một hệ thống đạt chuẩn "công nghiệp" thường nằm ở những quyết định tưởng chừng nhỏ bé: Tại sao lại dùng ArrayDeque thay vì LinkedList? Khi nào thì khóa (block) một luồng, và khi nào nên để nó trôi chảy tự do (lock-free)? Bài viết này không chỉ liệt kê API. Hãy cùng nhau bước vào hành trình tinh gọn hóa tư duy lập trình, dọn dẹp những "di sản" kỹ thuật cũ kỹ (như java.util.Stack), và chọn đúng công cụ cho từng bài toán cụ thể.

# tổng quan

Trước khi đi sâu vào chi tiết, chúng ta cần thống nhất một góc nhìn tối giản về cách Java tổ chức các cấu trúc dữ liệu này.

Stack (LIFO - Last In, First Out): Giống như một chồng đĩa, cái nào đặt lên sau cùng sẽ được lấy ra đầu tiên.

Queue (FIFO - First In, First Out): Dòng chảy tự nhiên của vạn vật, ai đến trước phục vụ trước.

Cây gia phả (Và những đứa con bị chối bỏ):

Collection
├── Stack (Legacy, extends Vector) ❌ TUYỆT ĐỐI TRÁNH
├── Deque (Double-Ended Queue)
│   ├── ArrayDeque ★ (Lựa chọn số 1 cho Stack/Queue đơn luồng)
│   └── LinkedList
├── Queue
│   ├── PriorityQueue (Min-heap/Max-heap)
│   ├── BlockingQueue (Thread-safe, Producer-Consumer)
│   │   ├── ArrayBlockingQueue (Có giới hạn)
│   │   └── LinkedBlockingQueue (Linh hoạt)
│   └── ConcurrentLinkedQueue (Thread-safe, Lock-free bằng CAS)

# 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

// 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

Circular array (ring buffer):

head=5, tail=2, capacity=8
[_, _, T, _, _, H, x, x]
0  1  2  3  4  5  6  7

Elements: [5, 6, 7, 0, 1] (wrap around)

addFirst: head = (head - 1) & (capacity - 1)  // move head left
addLast:  tail = (tail + 1) & (capacity - 1)  // move tail right

Capacity luôn là power of 2 (cho bitwise AND thay vì modulo)
Grow: double capacity khi full, copy elements
No null elements allowed

# ArrayDeque vs LinkedList (as Deque)

Tiêu chí	ArrayDeque	LinkedList
Memory	Compact (array)	40 bytes/node
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

Kết luận: ArrayDeque nhanh hơn LinkedList cho hầu hết Deque/Stack/Queue operations.

# 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
}

# 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() {
       while (true) {
           Order order = receiveOrder();
           orderQueue.put(order); // blocks if queue full
       }
   }
}
 
// Consumer
class OrderProcessor implements Runnable {
   public void run() {
       while (true) {
           Order order = orderQueue.take(); // blocks if queue empty
           processOrder(order);
       }
   }
}
 
// Start multiple consumers
ExecutorService executor = Executors.newFixedThreadPool(5);
executor.submit(new OrderProducer());
for (int i = 0; i < 4; i++) {
   executor.submit(new OrderProcessor());
}

# 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)

Non-blocking, thread-safe queue dùng CAS (Compare-And-Swap).

ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();
queue.offer("A"); // never blocks, never fails
queue.poll();     // null if empty (never blocks)

Không bounded (unbounded)
Không blocking (offer/poll luôn return immediately)
Lock-free (CAS-based, no mutex)
size() là O(n) — phải traverse!

Use case: High-throughput, non-blocking scenarios. Khi không cần blocking semantics.

# 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

Bài viết mang tính chất "ghi chú - chia sẻ và phi lợi nhuận". Nếu thấy hữu ích, hãy chia sẻ nó tới bạn bè và đồng nghiệp của bạn nhé!

Happy coding 😎 👍🏻 🚀 🔥.