DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Stack Implementation

What This Page Covers

The previous page covered individual operations. This page builds complete, production-quality stack classes from the ground up — two backend implementations and one advanced design pattern.

Implementation 1: Fixed-Size Array Stack
  Underlying structure: fixed-capacity array
  Teaches:  topIndex tracking, overflow detection
  Use when: capacity is known in advance

Implementation 2: Dynamic Array Stack
  Underlying structure: resizable array
  Teaches:  automatic resizing, amortized cost
  Use when: general-purpose, unknown capacity

Implementation 3: Linked List Stack
  Underlying structure: singly linked list
  Teaches:  pointer-based push/pop, no capacity limit
  Use when: guaranteed O(1) per operation, no amortized

Advanced Pattern: Min Stack
  Extends any stack to support getMin() in O(1)
  Teaches:  auxiliary stack technique
  Use when: interview problem requiring O(1) minimum access

Implementation 1: Fixed-Size Array Stack

A fixed-size stack pre-allocates an array of known capacity. The topIndex pointer tracks where the top element lives. Push increments topIndex; pop decrements it.

Fixed array stack internals:

  capacity = 5
  topIndex = -1  (empty state)

  After push(10): arr = [10, _, _, _, _]  topIndex = 0
  After push(20): arr = [10, 20, _, _, _] topIndex = 1
  After push(30): arr = [10, 20, 30, _, _] topIndex = 2
  peek():  return arr[topIndex] = arr[2] = 30
  pop():   return arr[topIndex]; topIndex--  → returns 30, topIndex = 1
  isEmpty: topIndex == -1
  isFull:  topIndex == capacity - 1

Java

public class FixedArrayStack<T> {

    private Object[] data;    // Underlying fixed array
    private int topIndex;     // Index of the current top element (-1 = empty)
    private int capacity;

    @SuppressWarnings("unchecked")
    public FixedArrayStack(int capacity) {
        this.capacity = capacity;
        this.data     = new Object[capacity];
        this.topIndex = -1;   // Empty stack — nothing at index 0 yet
    }

    // PUSH — O(1)
    public void push(T value) {
        if (isFull()) {
            throw new StackOverflowError("Stack is full (capacity: " + capacity + ")");
        }
        data[++topIndex] = value;   // Increment first, then store
    }

    // POP — O(1)
    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            throw new java.util.EmptyStackException();
        }
        T value             = (T) data[topIndex];
        data[topIndex]      = null;   // Help garbage collection — clear the slot
        topIndex--;
        return value;
    }

    // PEEK — O(1)
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new java.util.EmptyStackException();
        }
        return (T) data[topIndex];
    }

    public boolean isEmpty() { return topIndex == -1; }
    public boolean isFull()  { return topIndex == capacity - 1; }
    public int     size()    { return topIndex + 1; }
    public int     capacity(){ return capacity; }

    @Override
    public String toString() {
        if (isEmpty()) return "Stack: [] (empty)";
        StringBuilder sb = new StringBuilder("Stack (top→bottom): [");
        for (int i = topIndex; i >= 0; i--) {
            sb.append(data[i]);
            if (i > 0) sb.append(", ");
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        FixedArrayStack<Integer> stack = new FixedArrayStack<>(5);

        stack.push(10); stack.push(20); stack.push(30);
        System.out.println(stack);                              // [30, 20, 10]
        System.out.println("Peek:     " + stack.peek());       // 30
        System.out.println("Size:     " + stack.size());       // 3
        System.out.println("Capacity: " + stack.capacity());   // 5
        System.out.println("isFull:   " + stack.isFull());     // false
        System.out.println("Pop:      " + stack.pop());        // 30
        System.out.println(stack);                              // [20, 10]

        // Fill to capacity
        stack.push(40); stack.push(50); stack.push(60);
        System.out.println("isFull: " + stack.isFull());       // true

        // Overflow attempt
        try {
            stack.push(99);
        } catch (StackOverflowError e) {
            System.out.println("Overflow: " + e.getMessage());
        }
    }
}

Output:
Stack (top→bottom): [30, 20, 10]
Peek:     30
Size:     3
Capacity: 5
isFull:   false
Pop:      30
Stack (top→bottom): [20, 10]
isFull:   true
Overflow: Stack is full (capacity: 5)

Dry Run: Fixed Array Stack — topIndex Tracking

capacity=5, data=[_, _, _, _, _], topIndex=-1

push(10): topIndex = -1+1 = 0  → data[0]=10  → [10, _, _, _, _]
push(20): topIndex = 0+1  = 1  → data[1]=20  → [10, 20, _, _, _]
push(30): topIndex = 1+1  = 2  → data[2]=30  → [10, 20, 30, _, _]

peek():
  return data[topIndex] = data[2] = 30   ← topIndex unchanged

pop():
  value = data[2] = 30
  data[2] = null               ← clear the slot
  topIndex = 2-1 = 1
  return 30
  data = [10, 20, null, _, _], topIndex=1

isEmpty():  topIndex == -1 ?  1 == -1 → false
isFull():   topIndex == 4 ?   1 == 4  → false
size():     topIndex + 1  =   1 + 1   = 2

Implementation 2: Dynamic Array Stack

A dynamic array stack grows automatically when full — identical to how ArrayList and Python list work internally. The resize doubles the capacity and copies all elements.

Java

public class DynamicArrayStack<T> {

    private Object[] data;
    private int      topIndex;
    private int      capacity;

    private static final int INITIAL_CAPACITY = 4;

    @SuppressWarnings("unchecked")
    public DynamicArrayStack() {
        capacity = INITIAL_CAPACITY;
        data     = new Object[capacity];
        topIndex = -1;
    }

    // PUSH — O(1) amortized (may trigger resize)
    public void push(T value) {
        if (topIndex == capacity - 1) {
            resize();
        }
        data[++topIndex] = value;
    }

    // Resize: double the capacity and copy all elements — O(n)
    @SuppressWarnings("unchecked")
    private void resize() {
        int      newCapacity = capacity * 2;
        Object[] newData     = new Object[newCapacity];

        for (int i = 0; i <= topIndex; i++) {
            newData[i] = data[i];
        }

        data     = newData;
        capacity = newCapacity;
        System.out.println("  [Resize] capacity: " + (newCapacity / 2)
                           + " → " + newCapacity);
    }

    // POP — O(1)
    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) throw new java.util.EmptyStackException();
        T value        = (T) data[topIndex];
        data[topIndex] = null;
        topIndex--;
        return value;
    }

    // PEEK — O(1)
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) throw new java.util.EmptyStackException();
        return (T) data[topIndex];
    }

    public boolean isEmpty()  { return topIndex == -1; }
    public int     size()     { return topIndex + 1; }
    public int     capacity() { return capacity; }

    public static void main(String[] args) {
        DynamicArrayStack<Integer> stack = new DynamicArrayStack<>();

        System.out.println("Initial capacity: " + stack.capacity()); // 4

        for (int i = 1; i <= 9; i++) {
            stack.push(i * 10);
            System.out.printf("  Pushed %2d | size=%d | capacity=%d%n",
                               i * 10, stack.size(), stack.capacity());
        }
    }
}

Output:
Initial capacity: 4
  Pushed 10 | size=1 | capacity=4
  Pushed 20 | size=2 | capacity=4
  Pushed 30 | size=3 | capacity=4
  Pushed 40 | size=4 | capacity=4
  [Resize] capacity: 4 → 8
  Pushed 50 | size=5 | capacity=8
  Pushed 60 | size=6 | capacity=8
  Pushed 70 | size=7 | capacity=8
  Pushed 80 | size=8 | capacity=8
  [Resize] capacity: 8 → 16
  Pushed 90 | size=9 | capacity=16

Resize Analysis — Why Amortized O(1)

Resize occurs at: 4, 8, 16, 32, ... elements (doubling)
Elements copied at each resize: 4, 8, 16, 32, ...

For 9 pushes (as in the output above):
  4 copies at resize 1 (cap 4→8)
  8 copies at resize 2 (cap 8→16)
  Total extra copies: 4 + 8 = 12

For n pushes total:
  Extra copies = 1 + 2 + 4 + ... + n/2  (geometric series) ≈ n
  Total work = n pushes + n copies = O(n)
  Amortized per push = O(n) / n = O(1)

Each resize is O(n) but resizes happen so infrequently
that the cost is effectively invisible across n operations.

Implementation 3: Linked List Stack

A linked list stack uses a singly linked list. The head is the top — push prepends, pop removes the head.

Java

public class LinkedListStack<T> {

    private static class Node<T> {
        T       data;
        Node<T> next;
        Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> head;   // top of stack
    private int     size;

    public LinkedListStack() {
        head = null;
        size = 0;
    }

    // PUSH — prepend to front — O(1), always
    public void push(T value) {
        head = new Node<>(value, head);  // new node → old head
        size++;
    }

    // POP — remove front node — O(1)
    public T pop() {
        if (isEmpty()) throw new java.util.EmptyStackException();
        T value = head.data;
        head    = head.next;
        size--;
        return value;
    }

    // PEEK — read front without removing — O(1)
    public T peek() {
        if (isEmpty()) throw new java.util.EmptyStackException();
        return head.data;
    }

    public boolean isEmpty() { return head == null; }
    public int     size()    { return size; }

    // CLEAR — O(1) GC handles the rest
    public void clear() { head = null; size = 0; }

    @Override
    public String toString() {
        if (isEmpty()) return "Stack: [] (empty)";
        StringBuilder sb   = new StringBuilder("Stack (top→bottom): [");
        Node<T>       curr = head;
        while (curr != null) {
            sb.append(curr.data);
            if (curr.next != null) sb.append(", ");
            curr = curr.next;
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        LinkedListStack<String> stack = new LinkedListStack<>();

        stack.push("A"); stack.push("B"); stack.push("C");
        System.out.println(stack);                       // [C, B, A]
        System.out.println("Peek: " + stack.peek());    // C
        System.out.println("Pop:  " + stack.pop());     // C
        System.out.println("Pop:  " + stack.pop());     // B
        System.out.println(stack);                       // [A]
        System.out.println("Size: " + stack.size());    // 1
        stack.clear();
        System.out.println("After clear: " + stack);   // [] (empty)
    }
}

Output:
Stack (top→bottom): [C, B, A]
Peek: C
Pop:  C
Pop:  B
Stack (top→bottom): [A]
After clear: Stack: [] (empty)

Advanced Pattern: Min Stack — O(1) getMin()

Problem: Design a stack that supports push, pop, peek, and getMin() in O(1) time and O(1) extra space per operation.

Insight: Maintain an auxiliary minStack that tracks the current minimum at every level of the main stack. When pushing onto the main stack, also push the current minimum (the smaller of the new value and the previous minimum) onto the min stack. When popping from the main stack, also pop from the min stack.

Push sequence: 5, 3, 7, 2, 8

Main stack:   5  3  7  2  8   ← top
Min stack:    5  3  3  2  2   ← tracks min AT THAT LEVEL

getMin() = top of minStack = 2 (always O(1))

Pop 8: main=[5,3,7,2], min=[5,3,3,2]  getMin()=2
Pop 2: main=[5,3,7],   min=[5,3,3]    getMin()=3
Pop 7: main=[5,3],     min=[5,3]      getMin()=3
Pop 3: main=[5],       min=[5]        getMin()=5

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class MinStack {

    private Deque<Integer> mainStack;
    private Deque<Integer> minStack;   // Auxiliary: tracks min at each level

    public MinStack() {
        mainStack = new ArrayDeque<>();
        minStack  = new ArrayDeque<>();
    }

    // PUSH — push to both stacks — O(1)
    public void push(int value) {
        mainStack.push(value);
        // Push the new minimum: smaller of value or current min
        if (minStack.isEmpty()) {
            minStack.push(value);
        } else {
            minStack.push(Math.min(value, minStack.peek()));
        }
    }

    // POP — pop from both stacks — O(1)
    public int pop() {
        if (mainStack.isEmpty()) throw new java.util.EmptyStackException();
        minStack.pop();               // Keep in sync with main stack
        return mainStack.pop();
    }

    // PEEK — top of main stack — O(1)
    public int peek() {
        if (mainStack.isEmpty()) throw new java.util.EmptyStackException();
        return mainStack.peek();
    }

    // GETMIN — top of min stack — O(1)
    public int getMin() {
        if (minStack.isEmpty()) throw new java.util.EmptyStackException();
        return minStack.peek();
    }

    public boolean isEmpty() { return mainStack.isEmpty(); }
    public int     size()    { return mainStack.size(); }

    public static void main(String[] args) {
        MinStack ms = new MinStack();

        ms.push(5);
        System.out.println("Push 5 → min=" + ms.getMin()); // 5

        ms.push(3);
        System.out.println("Push 3 → min=" + ms.getMin()); // 3

        ms.push(7);
        System.out.println("Push 7 → min=" + ms.getMin()); // 3

        ms.push(2);
        System.out.println("Push 2 → min=" + ms.getMin()); // 2

        ms.push(8);
        System.out.println("Push 8 → min=" + ms.getMin()); // 2

        System.out.println("Pop: " + ms.pop() + " → min=" + ms.getMin()); // pop 8, min=2
        System.out.println("Pop: " + ms.pop() + " → min=" + ms.getMin()); // pop 2, min=3
        System.out.println("Pop: " + ms.pop() + " → min=" + ms.getMin()); // pop 7, min=3
        System.out.println("Pop: " + ms.pop() + " → min=" + ms.getMin()); // pop 3, min=5
    }
}

Output:
Push 5 → min=5
Push 3 → min=3
Push 7 → min=3
Push 2 → min=2
Push 8 → min=2
Pop: 8 → min=2
Pop: 2 → min=3
Pop: 7 → min=3
Pop: 3 → min=5

Min Stack Dry Run

Operations: push(5), push(3), push(7), push(2), push(8)

After each push:
  push(5): main=[5],       mins=[5]        getMin()=5
  push(3): main=[5,3],     mins=[5,3]      getMin()=3  (3 < 5)
  push(7): main=[5,3,7],   mins=[5,3,3]    getMin()=3  (7 > 3, keep 3)
  push(2): main=[5,3,7,2], mins=[5,3,3,2]  getMin()=2  (2 < 3)
  push(8): main=[5,3,7,2,8],mins=[5,3,3,2,2] getMin()=2 (8 > 2, keep 2)

After pop():
  pop: remove 8 from main, remove 2 from mins
  main=[5,3,7,2], mins=[5,3,3,2]   getMin()=2

After pop():
  pop: remove 2 from main, remove 2 from mins
  main=[5,3,7],   mins=[5,3,3]     getMin()=3

Key insight: mins[i] always stores "what is the minimum of all
  elements from the bottom up to level i?"
  When we pop level i, that minimum is no longer valid,
  so we pop it from minStack too — restoring the previous level's min.

Implementation Comparison

Property	Fixed Array	Dynamic Array	Linked List
Push	O(1) — guaranteed	O(1) amortized	O(1) — guaranteed
Pop	O(1)	O(1)	O(1)
Peek	O(1)	O(1)	O(1)
Memory per element	Value only	Value only	Value + pointer (~8 bytes)
Max capacity	Fixed at creation	Unlimited (auto-resize)	Unlimited (per-node alloc)
Memory layout	Contiguous	Contiguous	Scattered
Cache performance	Excellent	Excellent	Poor
Overflow risk	Yes — if capacity exceeded	Never	Never
Best for	Known capacity, max performance	General use	Guaranteed O(1), no resizing

Common Mistakes in Implementation

Forgetting to null out the slot on pop in array stack. After popping, the old slot still holds a reference to the object. In Java, set data[topIndex+1] = null after decrementing topIndex. Without this, the object cannot be garbage collected even though it is "logically" gone — a memory leak for long-running stacks.

Using ++topIndex vs topIndex++ in array push. data[++topIndex] = value increments first, then writes — correct. data[topIndex++] = value writes at the old index, then increments — writes one slot too early if topIndex started at -1 (empty state). The increment-then-write pattern ++topIndex is correct for 0-indexed arrays with -1 as the empty sentinel.

Not protecting topIndex in concurrent environments. In multithreaded code, topIndex++ is not atomic — a race condition between two threads can corrupt the index. Use synchronized methods in Java, threading.Lock in Python, std::mutex in C++, or accept that single-threaded stack implementations are not thread-safe.

In Min Stack — not popping from minStack on every pop. The main stack and min stack must always be the same size. If you forget to pop minStack when popping mainStack, getMin() will return a stale minimum from a previous state. Every main pop must be paired with a min pop.

Interview Questions

Q: What is the difference between a fixed-size and dynamic-size stack implementation?

A fixed-size stack pre-allocates a specific number of slots and throws StackOverflowError if capacity is exceeded. It guarantees O(1) push with no amortization — every push is exactly O(1). A dynamic stack resizes when full, copying all elements to a new larger array. Individual pushes that trigger resize are O(n), but the amortized cost across n pushes is O(1). Dynamic stacks never overflow (barring system memory limits). Fixed stacks are faster and simpler when capacity is known in advance.

Q: How does the Min Stack pattern extend to Max Stack or Median Stack?

For Max Stack: maintain an auxiliary maxStack instead — push max(value, maxStack.peek()) on each push. For Median Stack, the problem is significantly harder — it requires two heaps (a max-heap for the lower half and a min-heap for the upper half), rebalancing on every push and pop. The O(1) min/max pattern using auxiliary stacks only works because min and max are single-value properties that follow the stack's LIFO structure.

Q: Why does the Linked List Stack use the head as the top?

Because pushing to the head is O(1) — create a new node, point it to the current head, update head. Pushing to the tail would require traversing the entire list to find the tail — O(n). By making the head the top, both push and pop are always O(1) with no traversal. This is the standard design for all linked-list-backed stacks.

Quick Quiz

Question 1: In the fixed array implementation, what is topIndex when the stack is empty?

›A) 0 — points to the first slot
›B) -1 — no valid element exists
›C) capacity - 1 — at the top
›D) null — no index

Answer: B) -1. The empty sentinel is -1 because array indices start at 0. When the stack is empty, there is no valid top element. The first push sets data[++topIndex] = data[0], making topIndex = 0 the single element.

Question 2: For the Min Stack pattern, after pushing [5, 3, 7, 2], what does the auxiliary minStack contain?

›A) [5, 3, 7, 2]
›B) [2, 2, 2, 2]
›C) [5, 3, 3, 2]
›D) [5, 3, 7, 2] reversed

Answer: C) [5, 3, 3, 2]. Each position stores the minimum of all elements from the bottom up to that level. Level 0: min(5) = 5. Level 1: min(5,3) = 3. Level 2: min(3,7) = 3. Level 3: min(3,2) = 2. This ensures getMin() is always O(1).

Question 3: Why must you null out array slots after pop in a Java array stack?

›A) To reset the array for reuse
›B) To prevent memory leaks — orphaned references keep objects from being GC'd
›C) To prevent reading stale values with peek
›D) Arrays require null values at the boundary

Answer: B) Memory leak prevention. The array still holds a reference to the popped object even though topIndex no longer includes it. The JVM garbage collector cannot free the object as long as the reference exists. Setting data[topIndex + 1] = null removes the reference so GC can reclaim the memory.

Question 4: In the dynamic array implementation, resize is triggered when topIndex == capacity - 1. What happens next?

›A) The push fails with StackOverflowError
›B) A new array of double the capacity is allocated, all elements are copied, then the new element is pushed
›C) Only the new element is added without copying
›D) The capacity grows by 1 to fit exactly the new element

Answer: B) Double, copy, push. The resize method allocates a new array of capacity * 2, copies all existing elements from index 0 to topIndex, updates data and capacity, then the push proceeds normally. This doubling strategy gives O(1) amortized push because the total copy work across all resizes is O(n) for n pushes.

Summary

Three complete stack implementations each with distinct tradeoffs:

Fixed Array Stack:

›topIndex = -1 for empty, topIndex = capacity - 1 for full
›data[++topIndex] = value on push, data[topIndex--] on pop
›isFull() check before push, isEmpty() check before pop/peek
›Fastest — zero overhead when below capacity

Dynamic Array Stack:

›Same as fixed, but resize doubles capacity and copies on overflow
›O(1) amortized push — occasional O(n) resize absorbed across n pushes
›Geometric series proof: total copies ≈ n, amortized per push = O(1)
›General-purpose — no capacity limit

Linked List Stack:

›head node is the top; push prepends, pop removes head
›Always O(1) — no amortized, no resize, no overflow
›Pointer overhead per node; scattered memory hurts cache

Min Stack Pattern:

›Two stacks: mainStack for data, minStack for running minimum
›Each push: push value to main, push min(value, minStack.top()) to minStack
›Each pop: pop both stacks in sync
›getMin() = minStack.peek() — always O(1)
›Main stack and min stack are always the same size — mandatory invariant

In the next topic, you will explore Stack Patterns — the core interview algorithms: balanced parentheses, evaluate postfix expressions, next greater element, and the monotonic stack.

←

PreviousStack Operations

NextStack Collection Frameworks

→