Linear
Stack Fundamentals
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle — the most recently added element is always the first one removed. Every push and pop operates on the same end (the "top"), making both operations O(1). Stacks power function call management, undo systems, expression parsing, and depth-first search.
01
Section One · Foundation
What is Stack?
A stack restricts all insertions and deletions to one end — the top. You can only add an element on top (push) or remove the element currently on top (pop). There is no way to access or modify elements in the middle without first removing everything above them. This constraint is what makes stacks powerful: they naturally track the most recent context — the last function call, the last opened bracket, the last undo-able action.
A stack can be backed by either an array or a linked list:
Array-Backed
Dynamic Array
Uses an ArrayList or resizable array under the hood. The top is the last index. Push and pop simply increment/decrement a pointer.
- Cache-friendly — contiguous memory
- O(1) amortized push (resize rare)
- Java
ArrayDeque, Pythonlist
Linked-List-Backed
Node Chain
Uses a singly linked list where the head is the top. Push and pop are addFirst/removeFirst — always O(1), no resize ever.
- True O(1) worst-case push/pop
- No wasted capacity
- Extra pointer overhead per element
Analogy: A stack of plates in a cafeteria. You can only take the plate on top, and when you add a clean plate, it goes on top of the pile. You never pull a plate from the middle — that would collapse everything. The last plate placed is always the first one taken.
Key Characteristics
All operations happen at the top
▶
Push, pop, peek are all O(1)
LIFO ordering preserved
▶
Most recent element always accessible first
No random access to middle elements
▶
Must pop everything above to reach deeper items
Function calls use a call stack
▶
Recursion, backtracking, DFS built on stacks
Parentheses / brackets nest like a stack
▶
Expression validation & parsing use stacks
02
Section Two · Operations
Core Operations
Push
Adds a new element to the top of the stack, increasing its size by one.
Pseudocode
function push(stack, value):
if stack.size == stack.capacity:
resize(stack) // array-backed: double capacity
stack.top += 1
stack[stack.top] = value // O(1) — place at top
Push is O(1) amortized with arrays, O(1) worst-case with linked lists. Array-backed stacks occasionally need to resize (copy all elements to a larger array), but because capacity doubles each time, the amortized cost per push across n operations is still O(1). Linked-list-backed stacks never resize at all.
Pop
Removes and returns the element at the top of the stack, decreasing its size by one.
Pseudocode
function pop(stack):
if stack.isEmpty():
throw "StackUnderflow" // nothing to remove
value = stack[stack.top] // grab top element
stack.top -= 1 // shrink stack — O(1) return value
Always check isEmpty() before popping. Popping from an empty stack is the most common stack-related runtime error. In Java,
ArrayDeque.pop() throws NoSuchElementException; in Python, list.pop() throws IndexError. Guard every pop with an emptiness check.Peek (Top)
Returns the element at the top of the stack without removing it — a read-only view of the most recent element.
Pseudocode
function peek(stack):
if stack.isEmpty():
throw "StackEmpty" return stack[stack.top] // O(1) — no mutation
Peek is essential for look-ahead logic. When solving problems like valid parentheses or monotonic stack, you frequently need to check the top element before deciding whether to push or pop. Peek avoids destructive reads — you see the top without losing it.
Monotonic Stack Pattern
Maintains a stack where elements are always in sorted order (increasing or decreasing), enabling O(n) solutions to "next greater/smaller element" problems.
Pseudocode — Next Greater Element
function nextGreater(arr):
result = new Array(arr.length, -1)
stack = [] // stores indices for i = 0 to arr.length - 1:
while stack is not empty and arr[i] > arr[stack.top]:
idx = stack.pop()
result[idx] = arr[i] // arr[i] is the next greater
stack.push(i)
return result // O(n) — each element pushed/popped once
Every element is pushed and popped at most once. Although there is a while loop inside the for loop, the total number of pop operations across the entire run is at most n — so the overall complexity is O(n), not O(n²). This is the key insight behind monotonic stack problems.
Common Mistake: Using Java's
Stack class. It extends Vector (synchronized, slow) and allows random access via get(i), breaking the stack abstraction. Always use ArrayDeque instead — it's faster and enforces proper LIFO semantics with push(), pop(), and peek().
03
Section Three · Visuals
Diagrams & Memory Layout
Stack Structure — Array vs Linked List
Two backing implementations — same LIFO behaviour
Push & Pop Walkthrough
Push 40, then pop — stack grows and shrinks at the top
Monotonic Stack — Next Greater Element
Processing array [2, 1, 4, 3] — stack tracks unresolved elements
04
Section Four · Code
Java Quick Reference
The most common stack operations using Java's ArrayDeque — the recommended stack implementation (avoid the legacy Stack class).
Java — ArrayDeque as Stack
import java.util.*;
Deque<Integer> stack = new ArrayDeque<>();
// O(1) — push onto top
stack.push(10); // [10]
stack.push(20); // [20, 10]
stack.push(30); // [30, 20, 10] // O(1) — peek at top without removing int top = stack.peek(); // 30 // O(1) — pop from top int val = stack.pop(); // 30 → stack is [20, 10] // O(1) — check emptiness boolean empty = stack.isEmpty(); // false // O(1) — size int sz = stack.size(); // 2
Stack — Full Implementation
Java — ArrayStack<T> from scratch
public class ArrayStack<T> {
private Object[] data;
private int top = -1;
public ArrayStack(int cap) { data = new Object[cap]; }
public ArrayStack() { this(16); }
public void push(T val) { // O(1) amortized if (top == data.length - 1)
data = java.util.Arrays.copyOf(data, data.length * 2);
data[++top] = val;
}
public T pop() { // O(1) if (top == -1) throw new java.util.EmptyStackException();
T val = (T) data[top];
data[top--] = null;
return val;
}
public T peek() { // O(1) if (top == -1) throw new java.util.EmptyStackException();
return (T) data[top];
}
public boolean isEmpty() { return top == -1; }
public int size() { return top + 1; }
public static void main(String[] args) {
ArrayStack<Integer> s = new ArrayStack<>();
s.push(10); s.push(20); s.push(30);
System.out.println(s.peek()); // 30 System.out.println(s.pop()); // 30 System.out.println(s.size()); // 2
}
}
Python — list as stack & manual class
# ─── 1. Built-in list as stack ────────────────────────────────
stack = []
stack.append(10) # push — O(1) amortized
stack.append(20)
stack.append(30)
top = stack[-1] # peek — O(1)
val = stack.pop() # pop — O(1) → 30 # ─── 2. Manual Stack class ──────────────────────────────────── class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty(): raise IndexError("pop from empty stack")
return self._data.pop()
def peek(self):
if self.is_empty(): raise IndexError("peek from empty stack")
return self._data[-1]
def is_empty(self): return len(self._data) == 0 def __len__(self): return len(self._data)
# ─── 3. Monotonic stack — next greater element ─────────────── def next_greater(arr):
result = [-1] * len(arr)
stack = []
for i, val in enumerate(arr):
while stack and arr[stack[-1]] < val:
result[stack.pop()] = val
stack.append(i)
return result
JavaScript — Stack class (ES6)
class Stack {
constructor() { this.data = []; }
push(val) { this.data.push(val); }
pop() {
if (this.isEmpty()) throw new Error('Stack underflow');
return this.data.pop();
}
peek() {
if (this.isEmpty()) throw new Error('Stack empty');
return this.data[this.data.length - 1];
}
isEmpty() { return this.data.length === 0; }
get size() { return this.data.length; }
}
// Monotonic stack — next greater element function nextGreater(arr) {
const result = new Array(arr.length).fill(-1);
const stack = [];
for (let i = 0; i < arr.length; i++) {
while (stack.length && arr[stack[stack.length - 1]] < arr[i])
result[stack.pop()] = arr[i];
stack.push(i);
}
return result;
}
C# — Built-in Stack<T> & monotonic pattern
using System;
using System.Collections.Generic;
var stack = new Stack<int>();
stack.Push(10); stack.Push(20); stack.Push(30);
int top = stack.Peek(); // 30 — O(1) int val = stack.Pop(); // 30 — O(1) bool empty = stack.Count == 0; // false // Monotonic stack — next greater element static int[] NextGreater(int[] arr) {
var result = new int[arr.Length];
Array.Fill(result, -1);
var s = new Stack<int>();
for (int i = 0; i < arr.Length; i++) {
while (s.Count > 0 && arr[s.Peek()] < arr[i])
result[s.Pop()] = arr[i];
s.Push(i);
}
return result;
}
05
Section Five · Complexity
Time & Space Complexity
| Operation | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Push | O(1) | O(1) amortized | O(n) on resize | O(1) |
| Pop | O(1) | O(1) | O(1) | O(1) |
| Peek | O(1) | O(1) | O(1) | O(1) |
| Search (contains) | O(1) | O(n) | O(n) | O(1) |
Why these complexities? Push, pop, and peek all operate exclusively on the top element — a single pointer increment, decrement, or read. No traversal is needed. The only exception is array resize on push, which copies all n elements to a new array — but because capacity doubles each time, this happens so rarely that the amortized cost is still O(1). Searching requires scanning the entire stack since there is no index-based access.
Space Complexity Note
A stack of n elements uses O(n) space. Array-backed stacks may over-allocate by up to 2× capacity, while linked-list-backed stacks use exactly n nodes plus one pointer per node. Auxiliary space for push, pop, and peek is O(1). Note that recursion implicitly uses the call stack — every recursive call adds a frame, so a recursive algorithm processing n elements uses O(n) stack space even if you don't explicitly create a stack object.
06
Section Six · Decision Guide
When to Use Stack
Use This When
- You need LIFO ordering — undo/redo systems, backtracking, DFS traversal, and expression evaluation all require processing the most recent item first.
- Matching nested structures — parentheses validation, HTML tag matching, and recursive descent parsing rely on stacks to track open/close pairs.
- Tracking "most recent" state — monotonic stack problems, browser back-button history, and function call frames all fit the stack model naturally.
Avoid When
- You need FIFO ordering — if the first item added should be processed first (e.g. task scheduling, BFS), use a Queue instead.
- Random access is required — stacks don't support
get(i); if you need to access elements by index, use an array or deque.
Comparison vs Alternatives
| Structure | Access | Insert | Delete | Best For |
|---|---|---|---|---|
| Stack ← this one | O(1) top only | O(1) push | O(1) pop | LIFO processing, DFS, undo, parsing |
| Queue | O(1) front only | O(1) enqueue | O(1) dequeue | FIFO processing, BFS, scheduling |
| Deque | O(1) both ends | O(1) either end | O(1) either end | Sliding window, both LIFO & FIFO |
07
Section Seven · Interview Practice
LeetCode Problems
Stack interview problems almost always involve one of three patterns: matching pairs (bracket validation, nested structures), monotonic stack (next greater/smaller element, histogram areas), or simulation (evaluate expressions, decode strings). Recognising "LIFO" or "most recent" in the problem statement is the key clue.
- Easy Valid Parentheses — Push every open bracket; on a close bracket, check the top matches — classic stack matching in O(n).
- Easy Min Stack — Maintain a parallel stack that tracks the current minimum — O(1) getMin by peeking the auxiliary stack.
- Medium Evaluate Reverse Polish Notation — Push operands; on an operator, pop two, compute, push the result — direct stack simulation.
- Medium Daily Temperatures — Monotonic decreasing stack of indices; when a warmer day appears, pop and record the gap — O(n).
- Hard Largest Rectangle in Histogram — Monotonic increasing stack of bar indices; on a shorter bar, pop and calculate area using the previous index as left boundary — O(n).
Interview Pattern: When a problem involves "next greater element", "matching brackets", "decode nested strings", or any scenario where you process the most recent item first, immediately think Stack. If you see "next greater/smaller", reach for a monotonic stack — it turns an O(n²) brute force into O(n).