Definition
- Stack – a linear data structure that follows Last In First Out (LIFO) ordering, meaning the most recently added element is always the first one removed.
- push – places a new element on top of the stack in O(1) time.
- pop – removes and returns the current top element in O(1) time.
- peek – returns the top element without removing it in O(1) time.
- isEmpty – checks whether the stack contains zero elements.
- ArrayDeque – the recommended Java implementation for a stack, preferred over the legacy
Stackclass because it is not synchronized and does not expose vector methods that break the stack abstraction.
Think of a pile of transaction receipts on Rajesh's desk at the National Bank of India. Every time a customer completes a deposit, Rajesh places the receipt on top of the pile. When the auditor asks for the latest receipt, Rajesh picks up the one on top, which is always the most recent. He cannot pull a receipt from the middle without first removing every receipt above it. That pile of receipts is exactly a stack.
Understanding the Concepts
What is a stack?
A stack is a linear data structure that follows Last In First Out ordering. The most recently added element sits on top, and it is the first element removed. You interact with a stack through three core operations: push to add, pop to remove and return the top, and peek to look at the top without removing it. All three operations run in constant time.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class ReceiptStack {
public static void main(String[] args) {
Deque<String> receipts = new ArrayDeque<>();
receipts.push("TXN-1001: Rajesh deposited 50000");
receipts.push("TXN-1002: Priya withdrew 20000");
receipts.push("TXN-1003: Rajesh transferred 15000");
System.out.println("Top receipt: " + receipts.peek());
System.out.println("Popped: " + receipts.pop());
System.out.println("New top: " + receipts.peek());
}
}
Top receipt: TXN-1003: Rajesh transferred 15000
Popped: TXN-1003: Rajesh transferred 15000
New top: TXN-1002: Priya withdrew 20000
Why do we need a stack?
A stack exists because many real problems follow a last-in-first-out discipline. Undo features reverse actions in the opposite order they were performed. Balanced-bracket checkers close the most recently opened bracket first. Method calls return to the most recently entered method. All of these naturally fit LIFO ordering, which is exactly what a stack enforces.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class UndoService {
private final Deque<String> actions = new ArrayDeque<>();
public void perform(String action) {
actions.push(action);
System.out.println("Performed: " + action);
}
public String undo() {
if (actions.isEmpty()) {
return "Nothing to undo";
}
return "Undone: " + actions.pop();
}
public static void main(String[] args) {
UndoService svc = new UndoService();
svc.perform("Add payee HDFC-Priya");
svc.perform("Set transfer limit 100000");
svc.perform("Schedule transfer 50000");
System.out.println(svc.undo());
System.out.println(svc.undo());
}
}
Performed: Add payee HDFC-Priya
Performed: Set transfer limit 100000
Performed: Schedule transfer 50000
Undone: Schedule transfer 50000
Undone: Set transfer limit 100000
How does a stack work internally?
ArrayDeque uses a resizable circular array under the hood. The head pointer tracks the top of the stack. When you push, the head moves one position and the element is placed there. When you pop, the element at the head is returned and the head moves back. Both operations are a single array access plus a pointer update, which is why they are constant time. The array doubles in size when full, giving amortized O(1) cost for push.
package com.bank.core;
// Simplified stack internals to illustrate the concept
public class SimpleStack {
private String[] data;
private int top = -1;
public SimpleStack(int capacity) {
data = new String[capacity];
}
public void push(String item) {
if (top == data.length - 1) {
throw new RuntimeException("Stack overflow");
}
data[++top] = item;
}
public String pop() {
if (top == -1) {
throw new RuntimeException("Stack underflow");
}
String item = data[top];
data[top--] = null; // help GC
return item;
}
public String peek() {
if (top == -1) {
throw new RuntimeException("Stack is empty");
}
return data[top];
}
public static void main(String[] args) {
SimpleStack s = new SimpleStack(10);
s.push("Account-1001");
s.push("Account-1002");
System.out.println("Top: " + s.peek());
System.out.println("Popped: " + s.pop());
System.out.println("Top after pop: " + s.peek());
}
}
Top: Account-1002
Popped: Account-1002
Top after pop: Account-1001
How do you create and use a stack in Java?
In modern Java, use ArrayDeque through the Deque interface. The legacy java.util.Stack class extends Vector and is synchronized on every call, which adds unnecessary overhead. ArrayDeque also avoids exposing random-access methods that break the stack abstraction.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.math.BigDecimal;
public class BalanceTracker {
public static void main(String[] args) {
// Recommended: ArrayDeque as a stack
Deque<BigDecimal> balanceHistory = new ArrayDeque<>();
balanceHistory.push(new BigDecimal("100000.00")); // opening balance
balanceHistory.push(new BigDecimal("85000.00")); // after withdrawal
balanceHistory.push(new BigDecimal("125000.00")); // after deposit
System.out.println("Current: " + balanceHistory.peek());
System.out.println("Revert: " + balanceHistory.pop());
System.out.println("Previous: " + balanceHistory.peek());
System.out.println("Size: " + balanceHistory.size());
}
}
Current: 125000.00
Revert: 125000.00
Previous: 85000.00
Size: 2
How is a stack different from a queue?
A stack is LIFO and a queue is FIFO. The stack serves the newest element first, while the queue serves the oldest element first. Both are linear structures with O(1) core operations, but they model different real-world patterns.
| Feature | Stack (LIFO) | Queue (FIFO) |
|---|---|---|
| Order | Last In First Out | First In First Out |
| Add operation | push (top) | offer / enqueue (rear) |
| Remove operation | pop (top) | poll / dequeue (front) |
| Inspect operation | peek (top) | peek (front) |
| Java class | ArrayDeque (push/pop) | ArrayDeque (offer/poll) |
| Use case | Undo, DFS, expression eval | BFS, task scheduling, fairness |
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
public class StackVsQueue {
public static void main(String[] args) {
// Stack: LIFO
Deque<String> stack = new ArrayDeque<>();
stack.push("TXN-A");
stack.push("TXN-B");
stack.push("TXN-C");
System.out.println("Stack pop: " + stack.pop()); // TXN-C (newest)
// Queue: FIFO
Queue<String> queue = new ArrayDeque<>();
queue.offer("TXN-A");
queue.offer("TXN-B");
queue.offer("TXN-C");
System.out.println("Queue poll: " + queue.poll()); // TXN-A (oldest)
}
}
Stack pop: TXN-C
Queue poll: TXN-A
What exceptions can occur?
Popping or peeking an empty ArrayDeque throws NoSuchElementException. The legacy Stack class throws EmptyStackException. Always guard with an isEmpty() check before calling pop or peek.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;
public class StackExceptionDemo {
public static void main(String[] args) {
Deque<String> stack = new ArrayDeque<>();
// Wrong: pop without checking
try {
stack.pop();
} catch (NoSuchElementException e) {
System.out.println("Caught: " + e.getClass().getSimpleName());
}
// Correct: check before popping
if (!stack.isEmpty()) {
System.out.println(stack.pop());
} else {
System.out.println("Stack is empty, nothing to pop");
}
}
}
Caught: NoSuchElementException
Stack is empty, nothing to pop
What are common mistakes?
The most common mistake is using the legacy Stack class instead of ArrayDeque. The Stack class extends Vector, which synchronizes every call and exposes get(int) which lets callers reach into the middle, breaking the LIFO contract.
package com.bank.core;
import java.util.Stack;
// WRONG: using legacy Stack
public class LegacyStackMistake {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
stack.push("Account-A");
stack.push("Account-B");
stack.push("Account-C");
// This breaks the stack abstraction
System.out.println("Middle access: " + stack.get(1));
// Output: Account-B (violates LIFO)
}
}
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
// CORRECT: using ArrayDeque
public class ModernStackUsage {
public static void main(String[] args) {
Deque<String> stack = new ArrayDeque<>();
stack.push("Account-A");
stack.push("Account-B");
stack.push("Account-C");
// No get(int) method: LIFO contract preserved
System.out.println("Top only: " + stack.peek());
}
}
Top only: Account-C
When should you use a stack?
Use a stack whenever the problem has a last-in-first-out pattern. Classic examples include undo and redo, balanced parentheses checking, depth-first search, evaluating postfix expressions, and backtracking algorithms. If the most recently added item must be processed first, a stack is the right choice.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class DfsAccountHierarchy {
public static void main(String[] args) {
// DFS traversal of account hierarchy using a stack
Deque<String> stack = new ArrayDeque<>();
stack.push("National Bank HQ");
while (!stack.isEmpty()) {
String node = stack.pop();
System.out.println("Visiting: " + node);
if (node.equals("National Bank HQ")) {
stack.push("Mumbai Branch");
stack.push("Delhi Branch");
}
}
}
}
Visiting: National Bank HQ
Visiting: Delhi Branch
Visiting: Mumbai Branch
What about thread safety?
ArrayDeque is not thread-safe. If multiple threads push and pop concurrently, the internal array can become corrupted. For concurrent use, wrap it with Collections.synchronizedDeque() or use a ConcurrentLinkedDeque. In banking transaction processing, each thread typically owns its own stack, so synchronization is rarely needed.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
public class ThreadSafeStackDemo {
public static void main(String[] args) {
// Not thread-safe
Deque<String> unsafeStack = new ArrayDeque<>();
// Thread-safe wrapper
// Note: individual calls are safe, but compound check-then-act
// still needs external synchronization
// Deque<String> safeStack = Collections.synchronizedDeque(unsafeStack);
// Best practice: each thread owns its own stack
Deque<String> threadLocalStack = new ArrayDeque<>();
threadLocalStack.push("TXN-5001");
System.out.println("Thread-local pop: " + threadLocalStack.pop());
}
}
Thread-local pop: TXN-5001
What should a senior engineer know?
The JVM itself uses a stack for method calls. Each thread has a call stack where a frame is pushed on method entry and popped on return. This is why infinite recursion throws StackOverflowError: the call stack runs out of space. The default stack size is around 512 KB to 1 MB depending on the platform, and you can tune it with the -Xss flag.
ArrayDeque uses a power-of-two sized array and bitwise masking for fast index calculation. When the array fills, it doubles in size, so the amortized cost of push remains O(1). The old Stack class extends Vector which grows by 100% or a fixed increment and synchronizes every method, making it measurably slower in single-threaded code.
package com.bank.core;
public class CallStackDemo {
static int depth = 0;
public static void recurse() {
depth++;
recurse();
}
public static void main(String[] args) {
try {
recurse();
} catch (StackOverflowError e) {
System.out.println("StackOverflowError at depth: " + depth);
}
}
}
StackOverflowError at depth: 10234
Visual Overview
Stack Operations (LIFO)
─────────────────────────
push(C) push(B) push(A)
┌─────┐ ┌─────┐ ┌─────┐
│ C │ top │ B │ │ A │ top
├─────┤ ├─────┤ ├─────┤
│ │ │ C │ top │ B │
└─────┘ ├─────┤ ├─────┤
│ │ │ C │
└─────┘ ├─────┤
│ │
└─────┘
pop() → returns A (last pushed, first out)
┌─────┐
│ B │ top
├─────┤
│ C │
├─────┤
│ │
└─────┘
ArrayDeque Internal Layout
──────────────────────────
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ │ │ │ C │ B │ A │ │ │
└────┴────┴────┴────┴────┴────┴────┴────┘
▲ ▲
│ │
tail head
(bottom) (top)
push → head moves right, element stored
pop → element returned, head moves left
Key Takeaway
A stack is a linear data structure that follows Last In First Out ordering. The most recently added element always sits on top, and it is the first one removed. The three core operations, push, pop, and peek, all run in constant time, and there is deliberately no way to reach into the middle. That restriction is exactly what makes a stack so predictable and so useful for problems where the latest item must be handled first.
In my banking project at the National Bank of India, I used a stack to implement an undo feature for the account management console. As Rajesh performs actions like adding a payee, setting a transfer limit, or scheduling a payment, each action is pushed onto the stack. When he taps undo, the top action is popped, which is always the most recent one, and the actions are reversed in exactly the order users expect. Without the LIFO guarantee, undo would not feel natural.
In modern Java, I always use ArrayDeque as my stack rather than the legacy Stack class. The old Stack extends Vector, which synchronizes every call and exposes indexed-access methods that let callers reach into the middle and break the LIFO contract. ArrayDeque avoids both problems and is measurably faster. I also always check isEmpty() before calling pop or peek, because an empty ArrayDeque throws NoSuchElementException, and I want the code to handle the empty case gracefully rather than crashing.
The JVM itself uses a stack for method calls: each thread has a call stack where a frame is pushed on method entry and popped on return. That is why infinite recursion produces a StackOverflowError rather than running forever. Understanding this connection between the data structure and the runtime helps explain why stacks appear everywhere in computing, from expression evaluation to depth-first search to backtracking.
Remember one sentence: a stack is Last In First Out, where push, pop, and peek all run in O(1) and the top element is always the most recently added.
---