stack & queue

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

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

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();
}

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

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"

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

// 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<Task> queue = new ArrayBlockingQueue<>(100); // bounded
 
// Producer thread
queue.put(task);  // blocks if full
 
// Consumer thread
Task task = queue.take();  // blocks if empty

// 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());
}

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<String> queue = new ConcurrentLinkedQueue<>();
queue.offer("A"); // never blocks, never fails
queue.poll();     // null if empty (never blocks)