☕ 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
LinkedHashMap
LinkedHashMap extends HashMap and maintains a doubly-linked list running through all its entries, preserving the order in which entries were inserted. Iteration over a LinkedHashMap always returns entries in insertion order. Optionally, it can be constructed in access-order mode where entries are ordered by most-recently accessed, making it the perfect foundation for implementing a Least Recently Used (LRU) cache. LinkedHashMap has slightly higher memory overhead than HashMap due to the extra linked list pointers.
TreeMap
TreeMap is a Red-Black tree implementation of the NavigableMap interface. It stores key-value pairs in sorted order — either the natural ordering of keys (requiring them to implement Comparable) or a custom Comparator provided at construction. All basic operations (get, put, remove, containsKey) are O(log n). TreeMap provides rich navigation operations: finding the closest key, extracting sub-maps, and headMap/tailMap views.
Hashtable
Hashtable is a legacy hash table implementation that predates the Collections Framework. Like Vector for lists, Hashtable was Java's original hash map from Java 1.0. It is thread-safe because all its methods are synchronised, but it does not permit null keys or null values. Hashtable has been retrofitted to implement the Map interface but should never be used in new code — HashMap is the non-concurrent replacement and ConcurrentHashMap is the concurrent replacement.
ConcurrentHashMap
ConcurrentHashMap is a thread-safe, high-performance hash map optimised for concurrent access. Unlike Hashtable and synchronised HashMap (which use a single lock), ConcurrentHashMap uses a more sophisticated concurrency mechanism — in Java 8+, it uses CAS (compare-and-swap) operations and per-bucket synchronisation — allowing multiple threads to read and write to different parts of the map simultaneously without blocking each other. It does not permit null keys or null values.