☕ Java
Deque
Deque (pronounced 'deck') stands for double-ended queue — a linear collection that supports element insertion and removal at both ends. It is a richer abstraction than Queue, which only supports access at one end, and a safer alternative to the legacy Stack class for LIFO usage. The Deque interface extends Queue and provides methods for operating on both the head and the tail, giving it the capabilities of both a stack and a queue simultaneously. Understanding Deque means understanding its dual-ended operations, its relationship to Queue and Stack, how it is used as a stack (LIFO), as a queue (FIFO), or as a sliding-window structure, and why it is the recommended replacement for both the legacy Stack class and LinkedList in queue roles.
The Deque Interface — Double-Ended Operations
The Deque interface provides twelve methods for operating on both ends of the deque. Each end (head/front and tail/rear) has three operations (insert, remove, examine), and each operation has two forms (throws exception vs returns special value), giving the 2 × 3 × 2 = 12 method matrix. This is the natural extension of Queue's six methods to both ends.
The naming convention distinguishes head (front) operations from tail (rear) operations. Methods operating on the first element use names with "First" suffix: addFirst(), offerFirst(), removeFirst(), pollFirst(), getFirst(), peekFirst(). Methods operating on the last element use "Last" suffix: addLast(), offerLast(), removeLast(), pollLast(), getLast(), peekLast(). The standard Queue methods (offer/poll/peek) are mapped to the tail for insertion and the head for removal, preserving FIFO semantics.
The Deque interface also explicitly provides push() and pop() methods for stack semantics, where elements are pushed onto and popped from the front (head). This makes Deque both a stack and a queue in the same interface, and it is why the Java documentation recommends using Deque implementations (primarily ArrayDeque) rather than the legacy Stack class for stack-based algorithms.
The legacy Stack class has several problems: it extends Vector (which is a synchronised ArrayList), so every operation acquires a lock even in single-threaded code; it inherits Vector's random-access methods (get(i), set(i)) which are semantically inappropriate for a stack abstraction; and it is a concrete class that cannot be easily replaced. ArrayDeque as a Deque is faster, cleaner, and more correctly scoped.
Java
// ── The 12 Deque methods ─────────────────────────────────────────────
//
// Throws exception Returns special value
// ─────────────────────────────────────────────────────────────
// Insert first addFirst(e) offerFirst(e)
// Insert last addLast(e) offerLast(e)
// Remove first removeFirst() pollFirst() → null if empty
// Remove last removeLast() pollLast() → null if empty
// Examine first getFirst() peekFirst() → null if empty
// Examine last getLast() peekLast() → null if empty
//
// Queue methods map to:
// offer(e) → offerLast(e) (insert at tail)
// poll() → pollFirst() (remove from head = FIFO)
// peek() → peekFirst() (examine head)
//
// Stack methods map to:
// push(e) → addFirst(e) (push onto front)
// pop() → removeFirst() (pop from front = LIFO)
// peek() → peekFirst() (examine top of stack)
Deque<String> deque = new ArrayDeque<>();
// ── Operating on both ends ────────────────────────────────────────────
deque.addLast("middle"); // [middle]
deque.addFirst("front"); // [front, middle]
deque.addLast("back"); // [front, middle, back]
System.out.println(deque.peekFirst()); // "front"
System.out.println(deque.peekLast()); // "back"
deque.removeFirst(); // removes "front" → [middle, back]
deque.removeLast(); // removes "back" → [middle]
System.out.println(deque.peekFirst()); // "middle"
// ── Deque as FIFO Queue ───────────────────────────────────────────────
Deque<String> fifoQueue = new ArrayDeque<>();
fifoQueue.offer("first"); // addLast internally
fifoQueue.offer("second");
fifoQueue.offer("third");
System.out.println(fifoQueue.poll()); // "first" — FIFO
// ── Deque as LIFO Stack ───────────────────────────────────────────────
Deque<String> stack = new ArrayDeque<>();
stack.push("bottom"); // addFirst internally
stack.push("middle");
stack.push("top");
System.out.println(stack.pop()); // "top" — LIFO
// ── WRONG: legacy Stack ───────────────────────────────────────────────
Stack<String> badStack = new Stack<>(); // extends Vector → synchronized overhead
// Inherits Vector's get(int), set(int), add(int, E) — semantically wrong for stack
badStack.push("element"); // slower than ArrayDeque
// CORRECT: ArrayDeque as stack ────────────────────────────────────────
Deque<String> goodStack = new ArrayDeque<>();
goodStack.push("element"); // ~3x faster, no lock overheadDeque as Stack — LIFO Algorithms
A stack is one of the most fundamental data structures in computer science — a LIFO collection used for expression evaluation, backtracking algorithms, depth-first search, parsing, undo/redo systems, and call frame simulation. The Deque interface provides push() (addFirst) and pop() (removeFirst) for natural stack semantics, and peek() (peekFirst) for examining the top without removal.
The canonical use of a stack in algorithms is maintaining state during recursive traversal without actual recursion. Any recursive algorithm can be converted to an iterative one using an explicit stack to simulate the call stack. The iterative DFS traversal is the most common example: push the start node, then loop — pop a node, process it, push its unvisited neighbours. The stack ensures nodes are processed in depth-first order (each branch fully explored before the next).
Expression evaluation uses two stacks: one for operators and one for operands. The shunting-yard algorithm processes an infix expression and uses a stack to ensure operator precedence is respected during conversion to postfix or during direct evaluation. Bracket matching uses a single stack: push opening brackets, and when a closing bracket is encountered, check that the stack's top matches.
The monotonic stack pattern maintains a stack in which elements are ordered monotonically (either all increasing or all decreasing from bottom to top). This pattern solves the "next greater element," "largest rectangle in histogram," and "daily temperatures" problems in O(n) time. The key insight is that elements are popped when a larger (or smaller) element is found, and each element is pushed and popped at most once.
Java
// ── DFS using explicit stack ──────────────────────────────────────────
public List<Integer> dfs(Map<Integer, List<Integer>> graph,
int start) {
List<Integer> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited.add(node)) continue; // already visited
result.add(node);
// Push neighbours in reverse order for natural left-to-right DFS
List<Integer> neighbours = graph.getOrDefault(node, List.of());
for (int i = neighbours.size() - 1; i >= 0; i--) {
if (!visited.contains(neighbours.get(i))) {
stack.push(neighbours.get(i));
}
}
}
return result;
}
// ── Bracket matching ──────────────────────────────────────────────────
public boolean isBalanced(String expression) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : expression.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
// ── Monotonic stack — next greater element ────────────────────────────
public int[] nextGreaterElement(int[] nums) {
int[] result = new int[nums.length];
Deque<Integer> stack = new ArrayDeque<>(); // stores indices
Arrays.fill(result, -1);
for (int i = 0; i < nums.length; i++) {
// While stack non-empty AND current element > element at stack top
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i]; // nums[i] is next greater for idx
}
stack.push(i); // push current index
}
// Remaining indices in stack have no next greater → result stays -1
return result;
}
// Example: [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1]
// ── Undo/redo system using two stacks ────────────────────────────────
Deque<Command> undoStack = new ArrayDeque<>();
Deque<Command> redoStack = new ArrayDeque<>();
public void execute(Command cmd) {
cmd.execute();
undoStack.push(cmd);
redoStack.clear(); // clear redo stack when new action performed
}
public void undo() {
if (!undoStack.isEmpty()) {
Command cmd = undoStack.pop();
cmd.undo();
redoStack.push(cmd);
}
}
public void redo() {
if (!redoStack.isEmpty()) {
Command cmd = redoStack.pop();
cmd.execute();
undoStack.push(cmd);
}
}Deque as Sliding Window and Monotonic Deque
The sliding window maximum/minimum problem requires knowing the maximum (or minimum) element within a moving window of size k as the window slides across an array. A naive approach checks all k elements per position — O(nk) total. A monotonic deque solves this in O(n) total time.
The sliding window maximum uses a deque that stores array indices and maintains a decreasing order of values from front to back. When a new element is added to the window, all elements smaller than it are removed from the back (they can never be the maximum while the new, larger element is in the window). When an element leaves the window (its index falls out of range), if it is at the front of the deque, it is removed from the front. The front of the deque always holds the index of the maximum element in the current window.
This monotonic deque pattern is the key to O(n) sliding window algorithms. It generalises: for sliding window minimum, maintain an increasing deque; for any sliding window aggregate that is monotone, adapt the comparison accordingly. The insight is that elements that can never be the answer while a better element exists in the window are aggressively pruned, keeping the deque small.
Deques also appear naturally in BFS with priority variations and in algorithms that need to process elements both in forward and backward direction — palindrome checking over a sequence, two-pointer techniques where either end can advance, and cycle detection in sequences.
Java
// ── Sliding window maximum — O(n) with monotonic deque ───────────────
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0 || k == 0) return new int[0];
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // stores INDICES
for (int i = 0; i < nums.length; i++) {
// Remove indices that have left the window from the FRONT
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// Remove indices whose values are SMALLER than current from the BACK
// (they can never be the window maximum while nums[i] is in the window)
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i); // add current index
// Window is fully formed from index k-1 onward
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
// nums=[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]
// Each element pushed and popped at most once → O(n)
// ── Deque for two-ended processing ───────────────────────────────────
// Check if a sequence can form a palindrome by pairing from both ends
public boolean canFormPalindrome(int[] sequence) {
Deque<Integer> deque = new ArrayDeque<>();
for (int val : sequence) deque.offerLast(val);
while (deque.size() > 1) {
int front = deque.pollFirst();
int back = deque.pollLast();
if (front != back) return false;
}
return true; // 0 or 1 elements remaining — palindrome
}
// ── Deque in level-order tree traversal by level ─────────────────────
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size(); // number of nodes at current level
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}Related Topics in Collections Framework
Collections Overview
The Java Collections Framework (JCF) is a unified architecture for representing and manipulating groups of objects. It provides a set of interfaces that define the operations a collection must support, a set of abstract classes that provide partial implementations, and a set of concrete implementations optimised for different use cases. Every Java developer uses collections daily — lists for sequences, sets for uniqueness, maps for key-value pairs, and queues for ordering — and choosing the right implementation for the right use case is one of the most fundamental practical skills in Java.
Iterable
Iterable<E> is the root interface of the Java Collections hierarchy. Any class that implements Iterable can be used in a for-each loop. It declares a single abstract method: iterator(), which returns an Iterator<E> that the for-each loop uses to traverse the elements. Implementing Iterable is all that is required to make a custom data structure work with Java's enhanced for loop, the Stream API, and any method that accepts an Iterable.
Collection Interface
Collection<E> is the root interface of the main collection hierarchy, extending Iterable<E>. It defines the common operations that all collection types must support: adding elements, removing elements, checking containment, querying size, clearing, converting to an array, and bulk operations. List, Set, and Queue all extend Collection. Map does not extend Collection because a map operates on key-value pairs rather than individual elements.
ArrayList
ArrayList is a resizable-array implementation of the List interface. It is the most commonly used collection in Java, providing dynamic sizing on top of a standard array. Elements are stored in contiguous memory, enabling O(1) random access by index. When the internal array is full, ArrayList automatically allocates a larger array and copies all elements. ArrayList is not thread-safe and preserves insertion order, allowing duplicates.