Definition
- push(e) adds to the head of the deque (top of the stack) in O(1) amortized
- pop() removes from the head in O(1); throws
NoSuchElementExceptionif empty - peek() reads the head without removing in O(1); returns null if empty
- Stack's problems: synchronized every method (slow), extends Vector (exposes get/set/add by index), legacy API (search returns 1-based position)
- The Java Javadoc explicitly states: "This class is likely to be faster than Stack when used as a stack"
Stack (legacy) is like an old safe with a heavy lock that opens and closes for every single operation – even when only one person uses it. Worse, the safe has a side window that lets you grab items from any position, which is not how a stack should work. ArrayDeque is a modern spring-loaded tray: put on top (push), take from top (pop), look at the top (peek). No lock, no side access, proper LIFO behavior.
Understanding the Concepts
How does ArrayDeque work as a stack?
ArrayDeque implements the Deque interface, which includes push(e), pop(), and peek() – the standard stack operations. These map to the head of the deque:
push(e)callsaddFirst(e)– adds to the head.pop()callsremoveFirst()– removes from the head.peek()callspeekFirst()– reads the head without removing.
This gives LIFO behavior: the last element pushed is the first one popped.
package com.bank.service;
import java.util.*;
public class StackOperationsDemo {
public static void main(String[] args) {
// CORRECT: ArrayDeque as stack
Deque<String> undoStack = new ArrayDeque<>();
undoStack.push("1: Created account SAV2001");
undoStack.push("2: Deposited Rs.50000");
undoStack.push("3: Set up auto-pay for EMI");
undoStack.push("4: Changed address");
System.out.println("Top of stack: " + undoStack.peek());
System.out.println("Stack size: " + undoStack.size());
System.out.println("\nUndoing actions:");
while (!undoStack.isEmpty()) {
System.out.println(" Undo: " + undoStack.pop());
}
}
}
Top of stack: 4: Changed address
Stack size: 4
Undoing actions:
Undo: 4: Changed address
Undo: 3: Set up auto-pay for EMI
Undo: 2: Deposited Rs.50000
Undo: 1: Created account SAV2001
Why is Stack a bad design?
Stack was added in Java 1.0 before the Collections Framework. It extends Vector, which creates three problems:
- Unnecessary synchronization. Every method is synchronized. Single-threaded code pays 15-30% overhead for lock acquisition.
- Leaky abstraction. Stack inherits
get(index),set(index),add(index, e), andremove(index)from Vector. These allow random access that violates the LIFO contract. - Legacy API.
Stack.search(Object)returns a 1-based position from the top, which is inconsistent with the 0-based indexing used everywhere else in Java.
package com.bank.demo;
import java.util.*;
public class StackDesignFlawsDemo {
public static void main(String[] args) {
// Stack: inherits Vector's random access
Stack<String> stack = new Stack<>();
stack.push("Bottom");
stack.push("Middle");
stack.push("Top");
// These should NOT be possible on a stack:
String bottom = stack.get(0); // "Bottom" – not LIFO!
stack.add(1, "Injected"); // insert at middle – not LIFO!
stack.set(0, "Modified Bottom"); // random set – not LIFO!
System.out.println("Stack internals exposed: " + stack);
// search() returns 1-based position (non-standard)
int pos = stack.search("Top"); // 1 (top of stack)
System.out.println("search(Top) = " + pos);
// ArrayDeque: proper stack API only
Deque<String> modern = new ArrayDeque<>();
modern.push("Bottom");
modern.push("Top");
// modern.get(0); // compile error – no get() method!
// Only push(), pop(), peek() – proper LIFO
}
}
Stack internals exposed: [Modified Bottom, Injected, Middle, Top]
search(Top) = 1
What is the performance difference?
package com.bank.demo;
import java.util.*;
public class StackPerformanceDemo {
public static void main(String[] args) {
int iterations = 5_000_000;
// Stack: synchronized push/pop
Stack<Integer> stack = new Stack<>();
long start = System.nanoTime();
for (int i = 0; i < iterations; i++) {
stack.push(i);
}
for (int i = 0; i < iterations; i++) {
stack.pop();
}
long stackTime = System.nanoTime() - start;
// ArrayDeque: no synchronization
Deque<Integer> deque = new ArrayDeque<>();
start = System.nanoTime();
for (int i = 0; i < iterations; i++) {
deque.push(i);
}
for (int i = 0; i < iterations; i++) {
deque.pop();
}
long dequeTime = System.nanoTime() - start;
System.out.printf("Stack: %d ms%n", stackTime / 1_000_000);
System.out.printf("ArrayDeque: %d ms%n", dequeTime / 1_000_000);
System.out.printf("ArrayDeque is %.1fx faster%n", (double) stackTime / dequeTime);
}
}
Stack: 245 ms
ArrayDeque: 95 ms
ArrayDeque is 2.6x faster
What are common mistakes?
Mistake: Declaring the type as Stack instead of Deque
// WRONG – uses legacy Stack class
Stack<String> stack = new Stack<>();
// CORRECT – uses ArrayDeque with Deque interface
Deque<String> stack = new ArrayDeque<>();
What should a senior engineer know?
- Stack is NOT deprecated. Despite being legacy, Stack has not been formally deprecated in the JDK. The Javadoc recommends ArrayDeque but Stack remains for backward compatibility.
- Thread-safe stack. If you need a concurrent stack, use ConcurrentLinkedDeque with push/pop, not Stack. Stack's coarse synchronization creates bottlenecks.
- Recursion to iteration. Converting recursive algorithms to iterative ones using an explicit stack is a common interview pattern. Always use ArrayDeque for this.
What are common interview follow-up questions?
- "Why should you not use Stack?" – Extends Vector (synchronized), exposes random access.
- "What is the Deque method equivalent of Stack.push()?" – addFirst(e).
- "Can ArrayDeque store null?" – No.
- "Name a scenario where you need an explicit stack." – DFS traversal, expression evaluation, undo/redo.
Visual Overview
Stack vs ArrayDeque Stack (legacy): ┌─────────────────────────────────┐ │ push(e) → synchronized add │ │ pop() → synchronized remove │ │ peek() → synchronized read │ │ get(i) → random access! │ ← violates LIFO │ search()→ 1-based position │ ← non-standard └─────────────────────────────────┘ ArrayDeque (modern): ┌─────────────────────────────────┐ │ push(e) → addFirst (no lock) │ │ pop() → removeFirst (no lock)│ │ peek() → peekFirst (no lock) │ │ No get(i), no random access │ ← proper LIFO └─────────────────────────────────┘
Key Takeaway
ArrayDeque is the modern replacement for the legacy Stack class. It provides the same push, pop, and peek operations for LIFO behavior, but without the synchronization overhead and without the leaky abstraction of random access.
Stack extends Vector, which means every operation acquires a monitor lock even when only one thread uses the stack. Worse, Stack inherits Vector's get, set, and add-by-index methods, which break the fundamental contract of a stack: only the top element should be accessible.
In the National Bank of India's account management system, Rajesh uses Deque for the undo feature. When Rajesh changes an account's address, the old address is pushed onto the stack. Undoing the change pops the stack and restores the previous value. ArrayDeque handles this 2-3x faster than Stack with half the memory.
Remember one sentence: always use Deque for stack behavior – never the Stack class.
---