[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":93,"_73":94,"_35":95},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",112,"title","Queue, Deque, and ArrayDeque","slug","java-collections-part-16-queue-deque-arraydeque","excerpt","Master queue abstractions: FIFO Queue interface, double-ended Deque, ArrayDeque's circular buffer implementation beating LinkedList and deprecated Stack.","# Java Collections Compendium Part 16: Queue, Deque & ArrayDeque\n\nMaster Java's queue abstractions for FIFO processing, double-ended operations, and stack replacement. Learn why ArrayDeque outperforms both LinkedList and Stack, and when to use each queue variant.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| **Topic** | Queue, Deque, ArrayDeque, LinkedList as Queue |\n| **Complexity** | Intermediate |\n| **Prerequisites** | Part 1 (Framework Architecture), Part 7 (LinkedList) |\n| **Time to Master** | 2-3 hours |\n| **Interview Frequency** | High (Queue operations, Stack replacement) |\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. Understand Queue and Deque interfaces and their operation pairs\n2. Master ArrayDeque's circular buffer implementation\n3. Replace deprecated Stack with ArrayDeque\n4. Choose between ArrayDeque and LinkedList for queue operations\n5. Implement BFS, undo/redo, and other classic patterns\n\n---\n\n## Production Story: The Stack Overflow That Wasn't\n\n### The Incident\n\nOur expression parser was crashing with `StackOverflowError` - but not the JVM stack kind. We were using Java's `Stack` class and hitting unexpected performance issues:\n\n```java\n// ExpressionParser.java - The problematic code\npublic class ExpressionParser {\n private Stack operatorStack = new Stack<>();\n\n public Expression parse(String input) {\n for (Token token : tokenize(input)) {\n if (token.isOperator()) {\n operatorStack.push(token);\n } else if (token.isCloseParen()) {\n while (!operatorStack.isEmpty()) {\n Token op = operatorStack.pop(); // Very slow!\n // process...\n }\n }\n }\n return buildExpression();\n }\n}\n```\n\n### The Problem with Stack\n\n```java\n// Stack extends Vector, which is synchronized\npublic class Stack extends Vector {\n public E push(E item) {\n addElement(item); // Synchronized!\n return item;\n }\n\n public synchronized E pop() { // Synchronized!\n // ...\n }\n}\n\n// Every push/pop acquires a lock - unnecessary overhead!\n// Plus, Stack grows like Vector (doubles), less efficient than ArrayDeque\n```\n\n### The ArrayDeque Solution\n\n```java\n// ExpressionParser.java - The fast solution\npublic class ExpressionParser {\n private Deque operatorStack = new ArrayDeque<>();\n\n public Expression parse(String input) {\n for (Token token : tokenize(input)) {\n if (token.isOperator()) {\n operatorStack.push(token); // O(1), no synchronization\n } else if (token.isCloseParen()) {\n while (!operatorStack.isEmpty()) {\n Token op = operatorStack.pop(); // O(1), no synchronization\n // process...\n }\n }\n }\n return buildExpression();\n }\n}\n```\n\n### Performance Comparison\n\n```java\n// Benchmark: 1 million push/pop operations\n\n// Stack: ~150ms (synchronized overhead)\nStack stack = new Stack<>();\nfor (int i = 0; i < 1_000_000; i++) {\n stack.push(i);\n stack.pop();\n}\n\n// ArrayDeque: ~20ms (7.5x faster!)\nDeque deque = new ArrayDeque<>();\nfor (int i = 0; i < 1_000_000; i++) {\n deque.push(i);\n deque.pop();\n}\n```\n\n### Lessons Learned\n\n1. **Never use Stack class** - it's a legacy class from Java 1.0\n2. **ArrayDeque is the modern replacement** for both Stack and Queue\n3. **Synchronization has cost** - don't pay for it when you don't need it\n4. **Check for legacy classes** - Vector, Stack, Hashtable are outdated\n\n---\n\n## Mental Model: The Double-Ended Line\n\n```text\n┌─────────────────────────────────────────────────────────────────────┐\n│ QUEUE vs DEQUE vs STACK │\n├─────────────────────────────────────────────────────────────────────┤\n│ │\n│ Queue (FIFO - First In, First Out) │\n│ Like a line at a store: │\n│ │\n│ IN → [Person1] [Person2] [Person3] [Person4] → OUT │\n│ (oldest) (newest) │\n│ │\n│ offer(x) adds to tail (end of line) │\n│ poll() removes from head (front of line) │\n│ │\n│ ───────────────────────────────────────────────────────────────── │\n│ │\n│ Deque (Double-Ended Queue) │\n│ Like a line where you can enter/exit at both ends: │\n│ │\n│ ← IN/OUT [E1] [E2] [E3] [E4] IN/OUT → │\n│ (head) (tail) │\n│ │\n│ offerFirst()/offerLast() - add at either end │\n│ pollFirst()/pollLast() - remove from either end │\n│ │\n│ ───────────────────────────────────────────────────────────────── │\n│ │\n│ Stack (LIFO - Last In, First Out) │\n│ Like a stack of plates: │\n│ │\n│ ┌─────┐ ← push()/pop() only at top │\n│ │ E4 │ │\n│ ├─────┤ │\n│ │ E3 │ │\n│ ├─────┤ │\n│ │ E2 │ │\n│ ├─────┤ │\n│ │ E1 │ │\n│ └─────┘ │\n│ │\n│ Deque as Stack: push() = addFirst(), pop() = removeFirst() │\n│ │\n└─────────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## Deep Dive: Queue Interface\n\n### Queue Method Pairs\n\n```java\npublic interface Queue extends Collection {\n // Throws exception on failure:\n boolean add(E e); // Add to tail, throws if full\n E remove(); // Remove from head, throws if empty\n E element(); // Peek head, throws if empty\n\n // Returns special value on failure:\n boolean offer(E e); // Add to tail, returns false if full\n E poll(); // Remove from head, returns null if empty\n E peek(); // Peek head, returns null if empty\n}\n```\n\n### When to Use Which\n\n```java\nQueue queue = new LinkedList<>();\n\n// Use throwing versions when empty/full is a bug:\ntry {\n String item = queue.remove(); // Throws if empty\n} catch (NoSuchElementException e) {\n // This shouldn't happen in correct code\n throw new IllegalStateException(\"Queue should not be empty here\");\n}\n\n// Use returning versions when empty/full is normal:\nString item = queue.poll(); // Returns null if empty\nif (item != null) {\n process(item);\n}\n\n// Common pattern: process until empty\nwhile ((item = queue.poll()) != null) {\n process(item);\n}\n```\n\n---\n\n## Deep Dive: Deque Interface\n\n### Double-Ended Operations\n\n```java\npublic interface Deque extends Queue {\n // Head operations (front of deque)\n void addFirst(E e);\n boolean offerFirst(E e);\n E removeFirst();\n E pollFirst();\n E getFirst();\n E peekFirst();\n\n // Tail operations (back of deque)\n void addLast(E e);\n boolean offerLast(E e);\n E removeLast();\n E pollLast();\n E getLast();\n E peekLast();\n\n // Stack operations (using head)\n void push(E e); // Same as addFirst\n E pop(); // Same as removeFirst\n E peek(); // Same as peekFirst\n\n // Queue operations (head to tail)\n boolean add(E e); // Same as addLast\n boolean offer(E e);// Same as offerLast\n E remove(); // Same as removeFirst\n E poll(); // Same as pollFirst\n}\n```\n\n### Deque as Stack vs Queue\n\n```java\nDeque deque = new ArrayDeque<>();\n\n// As Stack (LIFO) - use push/pop\ndeque.push(\"first\");\ndeque.push(\"second\");\ndeque.push(\"third\");\nSystem.out.println(deque.pop()); // \"third\" - last in, first out\n\n// As Queue (FIFO) - use offer/poll\ndeque.offer(\"first\");\ndeque.offer(\"second\");\ndeque.offer(\"third\");\nSystem.out.println(deque.poll()); // \"first\" - first in, first out\n```\n\n---\n\n## Deep Dive: ArrayDeque Internals\n\n### Circular Buffer Implementation\n\n```java\n// ArrayDeque uses a circular buffer\npublic class ArrayDeque ... {\n transient Object[] elements; // The buffer\n transient int head; // Index of first element\n transient int tail; // Index after last element\n}\n\n// Circular indexing:\n// If capacity = 8, and we add/remove:\n// After addLast(A, B, C):\n// elements: [A, B, C, _, _, _, _, _]\n// head: 0, tail: 3\n\n// After addFirst(X):\n// elements: [A, B, C, _, _, _, _, X]\n// head: 7, tail: 3\n\n// After pollFirst(): (removes X)\n// elements: [A, B, C, _, _, _, _, _]\n// head: 0, tail: 3\n```\n\n### Visual: Circular Buffer\n\n```text\nArrayDeque with capacity 8:\n\nInitial (empty):\nhead = 0, tail = 0\n┌───┬───┬───┬───┬───┬───┬───┬───┐\n│ │ │ │ │ │ │ │ │\n└───┴───┴───┴───┴───┴───┴───┴───┘\n 0 1 2 3 4 5 6 7\n\nAfter addLast(A), addLast(B), addLast(C):\nhead = 0, tail = 3\n┌───┬───┬───┬───┬───┬───┬───┬───┐\n│ A │ B │ C │ │ │ │ │ │\n└───┴───┴───┴───┴───┴───┴───┴───┘\n ↑ ↑\n head tail\n\nAfter addFirst(X), addFirst(Y):\nhead = 6, tail = 3\n┌───┬───┬───┬───┬───┬───┬───┬───┐\n│ A │ B │ C │ │ │ │ Y │ X │\n└───┴───┴───┴───┴───┴───┴───┴───┘\n ↑\n head\nIteration order: Y, X, A, B, C (head to tail, wrapping)\n\nAfter pollFirst() (removes Y):\nhead = 7, tail = 3\n┌───┬───┬───┬───┬───┬───┬───┬───┐\n│ A │ B │ C │ │ │ │ │ X │\n└───┴───┴───┴───┴───┴───┴───┴───┘\n ↑\n head\n```\n\n### Resize Strategy\n\n```java\n// ArrayDeque doubles when full\nprivate void doubleCapacity() {\n int p = head;\n int n = elements.length;\n int r = n - p; // Elements to the right of head\n int newCapacity = n << 1; // Double\n Object[] a = new Object[newCapacity];\n System.arraycopy(elements, p, a, 0, r); // Copy right part\n System.arraycopy(elements, 0, a, r, p); // Copy left part\n elements = a;\n head = 0;\n tail = n;\n}\n\n// Example: Resize from 8 to 16\n// Before: [A, B, C, _, _, _, Y, X] head=6, tail=3\n// After: [Y, X, A, B, C, _, _, _, _, _, _, _, _, _, _, _] head=0, tail=5\n```\n\n### Why No Nulls?\n\n```java\nArrayDeque deque = new ArrayDeque<>();\ndeque.add(null); // 💥 NullPointerException\n\n// Reason: ArrayDeque uses null to detect empty slots\n// poll() returns null for empty - can't distinguish from stored null\n// Also enables efficient isEmpty() check\n```\n\n---\n\n## Deep Dive: ArrayDeque vs LinkedList\n\n### Performance Comparison\n\n| Operation | ArrayDeque | LinkedList |\n|-----------|------------|------------|\n| addFirst/addLast | O(1)* | O(1) |\n| removeFirst/removeLast | O(1) | O(1) |\n| get(index) | N/A | O(n) |\n| Memory per element | ~8 bytes | ~40 bytes |\n| Cache locality | Excellent | Poor |\n| Null elements | Not allowed | Allowed |\n\n*Amortized O(1) for ArrayDeque (occasional resize)\n\n### When to Use Which\n\n```java\n// ✅ Use ArrayDeque for:\n// - Stack operations (faster than Stack class)\n// - Queue operations (faster than LinkedList)\n// - When you don't need null elements\n// - Most general cases\nDeque taskQueue = new ArrayDeque<>();\n\n// ✅ Use LinkedList for:\n// - When you need null elements\n// - When you need List operations (get, set by index)\n// - When you're frequently removing from middle (via iterator)\nList taskList = new LinkedList<>();\n\n// ❌ Never use Stack class\n// ❌ Avoid LinkedList for pure queue/stack operations\n```\n\n### BFS Example: ArrayDeque vs LinkedList\n\n```java\n// BFS with ArrayDeque (3x faster for large graphs)\npublic List bfs(Node start) {\n List visited = new ArrayList<>();\n Deque queue = new ArrayDeque<>(); // Fast!\n Set seen = new HashSet<>();\n\n queue.offer(start);\n seen.add(start);\n\n while (!queue.isEmpty()) {\n Node current = queue.poll();\n visited.add(current);\n\n for (Node neighbor : current.neighbors()) {\n if (seen.add(neighbor)) {\n queue.offer(neighbor);\n }\n }\n }\n return visited;\n}\n\n// Same with LinkedList would work but be slower\n// LinkedList: more cache misses, more memory\n```\n\n---\n\n## Deep Dive: Common Patterns\n\n### Pattern 1: Sliding Window\n\n```java\npublic double[] movingAverage(int[] data, int windowSize) {\n double[] result = new double[data.length - windowSize + 1];\n Deque window = new ArrayDeque<>();\n long sum = 0;\n\n for (int i = 0; i < data.length; i++) {\n // Add new element\n window.addLast(data[i]);\n sum += data[i];\n\n // Remove old element if window full\n if (window.size() > windowSize) {\n sum -= window.removeFirst();\n }\n\n // Calculate average when window is full\n if (window.size() == windowSize) {\n result[i - windowSize + 1] = (double) sum / windowSize;\n }\n }\n return result;\n}\n```\n\n### Pattern 2: Undo/Redo Stack\n\n```java\npublic class UndoManager {\n private final Deque undoStack = new ArrayDeque<>();\n private final Deque redoStack = new ArrayDeque<>();\n private T currentState;\n\n public void execute(T newState) {\n if (currentState != null) {\n undoStack.push(currentState);\n }\n currentState = newState;\n redoStack.clear(); // New action clears redo history\n }\n\n public T undo() {\n if (undoStack.isEmpty()) return currentState;\n redoStack.push(currentState);\n currentState = undoStack.pop();\n return currentState;\n }\n\n public T redo() {\n if (redoStack.isEmpty()) return currentState;\n undoStack.push(currentState);\n currentState = redoStack.pop();\n return currentState;\n }\n}\n```\n\n### Pattern 3: Monotonic Deque (Sliding Window Maximum)\n\n```java\npublic int[] maxSlidingWindow(int[] nums, int k) {\n int n = nums.length;\n int[] result = new int[n - k + 1];\n Deque deque = new ArrayDeque<>(); // Stores indices\n\n for (int i = 0; i < n; i++) {\n // Remove elements outside window\n while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {\n deque.pollFirst();\n }\n\n // Remove smaller elements (they'll never be the max)\n while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {\n deque.pollLast();\n }\n\n deque.offerLast(i);\n\n if (i >= k - 1) {\n result[i - k + 1] = nums[deque.peekFirst()];\n }\n }\n return result;\n}\n```\n\n### Pattern 4: Level-Order Tree Traversal\n\n```java\npublic List> levelOrder(TreeNode root) {\n List> result = new ArrayList<>();\n if (root == null) return result;\n\n Deque queue = new ArrayDeque<>();\n queue.offer(root);\n\n while (!queue.isEmpty()) {\n int levelSize = queue.size();\n List level = new ArrayList<>(levelSize);\n\n for (int i = 0; i < levelSize; i++) {\n TreeNode node = queue.poll();\n level.add(node.val);\n\n if (node.left != null) queue.offer(node.left);\n if (node.right != null) queue.offer(node.right);\n }\n result.add(level);\n }\n return result;\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Using Stack Instead of ArrayDeque\n\n```java\n// ❌ WRONG: Stack is legacy and synchronized\nStack stack = new Stack<>();\nstack.push(1);\nstack.pop();\n\n// ✅ CORRECT: ArrayDeque is faster\nDeque stack = new ArrayDeque<>();\nstack.push(1);\nstack.pop();\n```\n\n### Mistake 2: Adding Null to ArrayDeque\n\n```java\n// ❌ WRONG: ArrayDeque doesn't allow null\nDeque deque = new ArrayDeque<>();\ndeque.add(null); // 💥 NullPointerException\n\n// ✅ CORRECT: Use LinkedList if you need nulls\nDeque deque = new LinkedList<>();\ndeque.add(null); // OK\n\n// Or use Optional/sentinel value\nDeque> deque = new ArrayDeque<>();\ndeque.add(Optional.empty()); // OK\n```\n\n### Mistake 3: Confusing add/offer Behavior\n\n```java\n// For unbounded queues (ArrayDeque, LinkedList):\n// add() and offer() behave the same - both always succeed\n\n// For bounded queues (ArrayBlockingQueue):\n// add() throws if full, offer() returns false\nBlockingQueue bounded = new ArrayBlockingQueue<>(2);\nbounded.add(\"A\");\nbounded.add(\"B\");\nbounded.add(\"C\"); // 💥 IllegalStateException\nbounded.offer(\"C\"); // Returns false\n\n// Use offer() for bounded queues to avoid exceptions\n```\n\n### Mistake 4: Wrong Direction for Stack Operations\n\n```java\nDeque deque = new ArrayDeque<>();\n\n// ❌ CONFUSING: Using queue methods for stack\ndeque.addLast(1); // Don't use for stack\ndeque.removeLast(); // Inconsistent\n\n// ✅ CORRECT: Use push/pop for stack (operates on head)\ndeque.push(1); // addFirst\ndeque.pop(); // removeFirst\n\n// Stack grows \"down\" from head in ArrayDeque\n// push -> head, pop -> head\n```\n\n### Mistake 5: Modifying During Iteration\n\n```java\nDeque deque = new ArrayDeque<>(Arrays.asList(\"A\", \"B\", \"C\"));\n\n// ❌ WRONG: ConcurrentModificationException\nfor (String s : deque) {\n if (s.equals(\"B\")) {\n deque.remove(s); // 💥 ConcurrentModificationException\n }\n}\n\n// ✅ CORRECT: Use iterator.remove()\nIterator it = deque.iterator();\nwhile (it.hasNext()) {\n if (it.next().equals(\"B\")) {\n it.remove();\n }\n}\n\n// ✅ CORRECT: Use removeIf()\ndeque.removeIf(s -> s.equals(\"B\"));\n```\n\n---\n\n## 🐛 Debug This\n\n### Challenge 1: The Disappearing Elements\n\n```java\nDeque deque = new ArrayDeque<>();\ndeque.offer(1);\ndeque.offer(2);\ndeque.offer(3);\n\ndeque.push(0);\n\nSystem.out.println(deque.poll());\nSystem.out.println(deque.pollLast());\n```\n\n**✅ Answer:**\n\nOutput:\n```text\n0\n3\n```\n\n- `offer` adds to tail: [1, 2, 3]\n- `push` adds to head: [0, 1, 2, 3]\n- `poll` (= pollFirst) removes from head: returns 0, deque is [1, 2, 3]\n- `pollLast` removes from tail: returns 3, deque is [1, 2]\n\n### Challenge 2: The Iterator Direction\n\n```java\nDeque deque = new ArrayDeque<>();\ndeque.addLast(\"A\");\ndeque.addFirst(\"B\");\ndeque.addLast(\"C\");\n\nIterator it = deque.iterator();\nwhile (it.hasNext()) {\n System.out.print(it.next() + \" \");\n}\nSystem.out.println();\n\nit = deque.descendingIterator();\nwhile (it.hasNext()) {\n System.out.print(it.next() + \" \");\n}\n```\n\n**✅ Answer:**\n\nOutput:\n```text\nB A C\nC A B\n```\n\n- addLast(\"A\"): [A]\n- addFirst(\"B\"): [B, A]\n- addLast(\"C\"): [B, A, C]\n- iterator(): head to tail → B A C\n- descendingIterator(): tail to head → C A B\n\n### Challenge 3: The Queue vs Stack\n\n```java\nDeque deque = new ArrayDeque<>();\n\n// Queue operations\ndeque.offer(1);\ndeque.offer(2);\n\n// Stack operations\ndeque.push(3);\ndeque.push(4);\n\n// What's the order?\nwhile (!deque.isEmpty()) {\n System.out.print(deque.poll() + \" \");\n}\n```\n\n**✅ Answer:**\n\nOutput: `4 3 1 2`\n\n- offer(1): [1]\n- offer(2): [1, 2]\n- push(3): [3, 1, 2]\n- push(4): [4, 3, 1, 2]\n- poll removes from head: 4, 3, 1, 2\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Browser History\n\nImplement browser back/forward using two stacks:\n\n```java\npublic class BrowserHistory {\n public BrowserHistory(String homepage);\n public void visit(String url);\n public String back(int steps);\n public String forward(int steps);\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class BrowserHistory {\n private final Deque backStack = new ArrayDeque<>();\n private final Deque forwardStack = new ArrayDeque<>();\n private String current;\n\n public BrowserHistory(String homepage) {\n this.current = homepage;\n }\n\n public void visit(String url) {\n backStack.push(current);\n current = url;\n forwardStack.clear();\n }\n\n public String back(int steps) {\n while (steps > 0 && !backStack.isEmpty()) {\n forwardStack.push(current);\n current = backStack.pop();\n steps--;\n }\n return current;\n }\n\n public String forward(int steps) {\n while (steps > 0 && !forwardStack.isEmpty()) {\n backStack.push(current);\n current = forwardStack.pop();\n steps--;\n }\n return current;\n }\n}\n```\n\n### Exercise 2: Valid Parentheses\n\nCheck if brackets are balanced:\n\n```java\npublic boolean isValid(String s);\n// \"()\" → true\n// \"()[]{}\" → true\n// \"(]\" → false\n// \"([)]\" → false\n// \"{[]}\" → true\n```\n\n**✅ Solution:**\n\n```java\npublic boolean isValid(String s) {\n Deque stack = new ArrayDeque<>();\n Map pairs = Map.of(')', '(', ']', '[', '}', '{');\n\n for (char c : s.toCharArray()) {\n if (pairs.containsValue(c)) {\n stack.push(c);\n } else if (pairs.containsKey(c)) {\n if (stack.isEmpty() || stack.pop() != pairs.get(c)) {\n return false;\n }\n }\n }\n return stack.isEmpty();\n}\n```\n\n### Exercise 3: Recent Counter\n\nCount requests in last 3000ms:\n\n```java\npublic class RecentCounter {\n public RecentCounter();\n public int ping(int t); // t is in milliseconds\n}\n// ping(1) → 1\n// ping(100) → 2\n// ping(3001) → 3\n// ping(3002) → 3 (request at t=1 is too old)\n```\n\n**✅ Solution:**\n\n```java\npublic class RecentCounter {\n private final Deque requests = new ArrayDeque<>();\n\n public int ping(int t) {\n requests.addLast(t);\n while (requests.peekFirst() < t - 3000) {\n requests.pollFirst();\n }\n return requests.size();\n }\n}\n```\n\n### Exercise 4: Implement Queue Using Stacks\n\nImplement FIFO queue using only stack operations:\n\n```java\npublic class MyQueue {\n public void push(T x); // Add to back\n public T pop(); // Remove from front\n public T peek(); // Get front\n public boolean empty();\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class MyQueue {\n private final Deque inbox = new ArrayDeque<>();\n private final Deque outbox = new ArrayDeque<>();\n\n public void push(T x) {\n inbox.push(x);\n }\n\n public T pop() {\n if (outbox.isEmpty()) {\n while (!inbox.isEmpty()) {\n outbox.push(inbox.pop());\n }\n }\n return outbox.pop();\n }\n\n public T peek() {\n if (outbox.isEmpty()) {\n while (!inbox.isEmpty()) {\n outbox.push(inbox.pop());\n }\n }\n return outbox.peek();\n }\n\n public boolean empty() {\n return inbox.isEmpty() && outbox.isEmpty();\n }\n}\n// Amortized O(1) for all operations\n```\n\n### Exercise 5: Circular Buffer\n\nImplement a fixed-size circular buffer:\n\n```java\npublic class CircularBuffer {\n public CircularBuffer(int capacity);\n public void write(T item); // Overwrites oldest if full\n public T read(); // Returns null if empty\n public boolean isFull();\n public boolean isEmpty();\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class CircularBuffer {\n private final Object[] buffer;\n private int head = 0;\n private int tail = 0;\n private int size = 0;\n\n public CircularBuffer(int capacity) {\n buffer = new Object[capacity];\n }\n\n public void write(T item) {\n buffer[tail] = item;\n tail = (tail + 1) % buffer.length;\n\n if (size < buffer.length) {\n size++;\n } else {\n head = (head + 1) % buffer.length; // Overwrite oldest\n }\n }\n\n @SuppressWarnings(\"unchecked\")\n public T read() {\n if (size == 0) return null;\n\n T item = (T) buffer[head];\n buffer[head] = null;\n head = (head + 1) % buffer.length;\n size--;\n return item;\n }\n\n public boolean isFull() {\n return size == buffer.length;\n }\n\n public boolean isEmpty() {\n return size == 0;\n }\n}\n```\n\n---\n\n## 🎤 Senior-Level Interview Questions\n\n### Question 1: Stack vs ArrayDeque\n\n**Q: Why is ArrayDeque preferred over Stack for stack operations?**\n\n**A:**\n\n1. **No synchronization overhead**: Stack extends Vector, all methods synchronized\n2. **Better performance**: ArrayDeque is ~3-5x faster for push/pop\n3. **Consistent API**: Stack extends Vector, mixing stack and list semantics\n4. **Modern design**: ArrayDeque designed for Deque interface\n\n```java\n// Stack has problematic inheritance\nStack stack = new Stack<>();\nstack.add(0, 5); // List method - breaks stack semantics!\nstack.get(2); // Random access - also problematic\n\n// ArrayDeque enforces proper usage\nDeque deque = new ArrayDeque<>();\n// No get(index), no add(index, elem) - clean stack/queue API\n```\n\n### Question 2: ArrayDeque Null Restriction\n\n**Q: Why doesn't ArrayDeque allow null elements?**\n\n**A:**\n\n1. **Ambiguity with poll()**: poll() returns null for empty queue - can't distinguish stored null\n2. **Efficient empty slot detection**: Uses null to identify unused array slots\n3. **Design decision**: Cleaner API, prevents NPE bugs\n\n```java\n// If nulls were allowed:\ndeque.offer(null);\ndeque.offer(\"value\");\nString s = deque.poll(); // null - was it stored or is queue empty?\n```\n\n### Question 3: Circular Buffer Benefits\n\n**Q: Explain how ArrayDeque's circular buffer improves over a simple array.**\n\n**A:**\n\nSimple array approach:\n```java\n// Remove from front requires shifting all elements - O(n)\n[A, B, C, D, _] → remove A → [B, C, D, _, _]\n```\n\nCircular buffer approach:\n```java\n// Just move head pointer - O(1)\nhead=0: [A, B, C, D, _] → head=1: [_, B, C, D, _]\n\n// Wrap around\nhead=3, tail=1: [E, _, _, D, _] // D is first, E is second\n```\n\nBenefits:\n- O(1) add/remove at both ends\n- No shifting required\n- Minimal memory overhead\n- Excellent cache locality\n\n### Question 4: Queue vs Deque Interface\n\n**Q: When would you declare a variable as Queue vs Deque?**\n\n**A:**\n\n```java\n// Use Queue when you only need FIFO operations\nQueue taskQueue = new ArrayDeque<>();\n// Client can't use addFirst(), push(), etc.\n\n// Use Deque when you need double-ended access\nDeque workStealing = new ArrayDeque<>();\n// Can steal from either end\n\n// Use Deque when you need stack operations\nDeque undoStack = new ArrayDeque<>();\n// push(), pop(), peek()\n\n// Principle: Use most restrictive type that works\n// Prevents misuse and clarifies intent\n```\n\n### Question 5: BFS Queue Choice\n\n**Q: Why use ArrayDeque over LinkedList for BFS?**\n\n**A:**\n\n1. **Cache locality**: ArrayDeque stores elements contiguously\n2. **Memory efficiency**: ~8 bytes/element vs ~40 bytes for LinkedList nodes\n3. **No allocation per element**: LinkedList creates node object for each add\n4. **Faster operations**: No pointer traversal\n\n```java\n// Benchmark: BFS on graph with 1M nodes\n// ArrayDeque: ~200ms\n// LinkedList: ~600ms\n// 3x speedup from better memory access patterns\n```\n\n### Question 6: offer() vs add()\n\n**Q: When should you use offer() vs add() for queues?**\n\n**A:**\n\n```java\n// offer() - capacity-constrained queues\nBlockingQueue bounded = new ArrayBlockingQueue<>(100);\nif (!bounded.offer(task)) {\n handleQueueFull(task); // Graceful handling\n}\n\n// add() - unbounded queues or when full is an error\nQueue unbounded = new ArrayDeque<>();\nunbounded.add(task); // Always succeeds for ArrayDeque\n\n// Rule of thumb:\n// - Bounded queue → offer() (check return value)\n// - Unbounded queue → add() (always succeeds)\n// - Exception handling style → add() (throws on failure)\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### Queue Interface\n- Two operation styles: throwing (add/remove/element) vs special-value (offer/poll/peek)\n- Use offer/poll for normal empty/full handling\n- Use add/remove when empty/full is a bug\n\n### Deque Interface\n- Double-ended: addFirst/addLast, pollFirst/pollLast\n- Stack: push/pop/peek (all operate on head)\n- Queue: offer/poll (tail to head)\n\n### ArrayDeque\n- Circular buffer - O(1) operations at both ends\n- No null elements allowed\n- Better than Stack and usually better than LinkedList\n- Use for stack, queue, or deque operations\n\n### Best Practices\n- Never use Stack class - use ArrayDeque\n- Prefer ArrayDeque over LinkedList for queues\n- Use most restrictive interface type (Queue vs Deque)\n- Consider bounded queues for backpressure\n\n---\n\n## 🏁 Conclusion\n\nArrayDeque is the Swiss Army knife of Java's queue implementations. Understanding its circular buffer design explains why it outperforms alternatives and why it prohibits nulls. Whether you need a stack, queue, or double-ended queue, ArrayDeque should be your default choice.\n\nKey takeaways:\n1. **Never use Stack** - ArrayDeque is faster and cleaner\n2. **ArrayDeque's circular buffer** enables O(1) operations at both ends\n3. **No nulls allowed** - uses null for empty slot detection\n4. **Prefer ArrayDeque over LinkedList** for pure queue/stack usage\n5. **Interface choice matters** - Queue restricts API, Deque exposes all operations\n\nIn the next article, we'll explore PriorityQueue and heap-based data structures - essential for scheduling, top-K problems, and priority-based processing.\n\n---\n\n## 📅 Review Schedule\n\nTo solidify your understanding, review this material:\n- **Tomorrow**: Implement Exercise 4 (Queue using Stacks) from memory\n- **In 3 days**: Explain ArrayDeque circular buffer to a colleague\n- **In 1 week**: Review Stack class deprecation reasons\n- **In 2 weeks**: Practice sliding window problems using Deque\n\n---\n\n**Next in Series**: [Part 17: PriorityQueue & Heap Operations](/articles/java-collections-part-17-priorityqueue-heap)\n\n**Series Navigation**: [Part 0: How to Use This Series](/articles/java-collections-part-0-how-to-use-this-series) | [Full Index](/articles/java-collections-compendium)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:26.041233Z","createdAt","2026-06-10T07:19:26.041862Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",17,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Java","readingTime","seriesId",5,"seriesOrder",16,"author",{"_31":55,"_104":57,"_105":106,"_107":108,"_109":-5,"_110":-5,"_111":-5,"_112":-5,"_113":-5},"category",{"_31":62,"_73":59,"_35":92,"_76":102,"_103":-5},"tags",[79,80,81,82,83,84],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Java Collections Compendium: From Fundamentals to Production Mastery","java-collections-compendium","description","A comprehensive 30-part series covering everything about Java Collections Framework. From foundational concepts like generics and equals/hashCode contract, through deep dives into ArrayList, LinkedList, HashMap, TreeMap, ConcurrentHashMap, to modern features like immutable collections, Java 21 sequenced collections, streams & collectors, and production patterns with JPA, Jackson & Spring. Includes real production stories, mental models, exercises, and 50+ interview questions.","isActive",{"_31":99,"_73":100,"_35":101},{"_31":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":91,"_73":59,"_35":92},{"_31":88,"_73":89,"_35":90},{"_31":85,"_73":86,"_35":87},270,"Queue","queue",353,"Lifo","lifo",14,"java",352,"Fifo","fifo",268,"Deque","deque",267,"Arraydeque","arraydeque","Category for Java","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]