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 Operations

Operations Overview

A stack exposes a small, well-defined set of operations. Every interview problem that uses a stack only calls these operations — understanding them precisely is the foundation.

Core operations (must know):
  push(value)   → add value to the top            O(1)
  pop()         → remove and return the top value  O(1)
  peek()        → read top value without removing  O(1)
  isEmpty()     → true if the stack has no elements O(1)

Supporting operations:
  size()        → number of elements in the stack  O(1)
  clear()       → remove all elements              O(n) or O(1)
  search(value) → distance from top to value       O(n)

All core operations are O(1). This is the defining property of a stack — no matter how many elements it holds, accessing the top is always one step.

Implementation 1: Array-Backed Stack

An array-backed stack uses a dynamic array (ArrayList, Python list, C++ vector, JavaScript Array) as the underlying storage. The top of the stack is always the last element of the array.

Array-backed stack state:

  Internal array: [10, 20, 30, ___ , ___]
                    0   1   2   3     4
                            ↑
                          topIndex = 2

  Push 40:  array[3] = 40, topIndex = 3
  Pop:      return array[3], topIndex = 2
  Peek:     return array[topIndex] = array[2] = 30

Java

import java.util.ArrayList;
import java.util.EmptyStackException;

public class ArrayStack<T> {

    private ArrayList<T> data;

    public ArrayStack() {
        data = new ArrayList<>();
    }

    // PUSH — add to top (end of array) — O(1) amortized
    public void push(T value) {
        data.add(value);
    }

    // POP — remove and return top — O(1)
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return data.remove(data.size() - 1);
    }

    // PEEK — read top without removing — O(1)
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return data.get(data.size() - 1);
    }

    // ISEMPTY — O(1)
    public boolean isEmpty() {
        return data.isEmpty();
    }

    // SIZE — O(1)
    public int size() {
        return data.size();
    }

    // CLEAR — remove all elements — O(1) (just drop the list reference)
    public void clear() {
        data.clear();
    }

    // SEARCH — distance of value from top (1-indexed) — O(n)
    // Returns -1 if not found
    public int search(T value) {
        for (int i = data.size() - 1; i >= 0; i--) {
            if (data.get(i).equals(value)) {
                return data.size() - i; // 1 = top, 2 = second from top, ...
            }
        }
        return -1;
    }

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

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

        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("Pop:    " + stack.pop());       // 30
        System.out.println("Pop:    " + stack.pop());       // 20
        System.out.println(stack);                           // [10]
        System.out.println("Search 10: " + stack.search(10)); // 1 (at top)
        System.out.println("isEmpty: " + stack.isEmpty()); // false
        stack.clear();
        System.out.println("After clear: " + stack.isEmpty()); // true
    }
}

Output:
Stack (top→bottom): [30, 20, 10]
Peek:   30
Size:   3
Pop:    30
Pop:    20
Stack (top→bottom): [10]
Search 10: 1
isEmpty: false
After clear isEmpty: true

Implementation 2: Linked-List-Backed Stack

A linked-list-backed stack uses a linked list as the underlying storage. The head of the list is the top of the stack. Push prepends a new node; pop removes the head node.

Linked-list stack state:

  head → [30] → [20] → [10] → null
          ↑ top

  Push 40:  new node(40) → [40] → [30] → [20] → [10] → null
                            head
  Pop:      remove head, return 40, head = node(30)
  Peek:     return head.data = 30

Java

import java.util.EmptyStackException;

public class LinkedStack<T> {

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

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

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

    // PUSH — prepend new node — O(1)
    public void push(T value) {
        Node<T> newNode = new Node<>(value);
        newNode.next    = head;
        head            = newNode;
        size++;
    }

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

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

    // ISEMPTY — O(1)
    public boolean isEmpty() { return head == null; }

    // SIZE — O(1)
    public int size() { return size; }

    // CLEAR — O(1) — just drop the head reference
    public void clear() { head = null; size = 0; }

    // SEARCH — O(n)
    public int search(T value) {
        Node<T> curr = head;
        int     dist = 1;
        while (curr != null) {
            if (curr.data.equals(value)) return dist;
            curr = curr.next;
            dist++;
        }
        return -1;
    }

    @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;
        }
        sb.append("]");
        return sb.toString();
    }

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

        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("Pop:    " + stack.pop());      // 30
        System.out.println("Pop:    " + stack.pop());      // 20
        System.out.println(stack);                          // [10]
        System.out.println("Search 10: " + stack.search(10)); // 1
    }
}

Output:
Stack (top→bottom): [30, 20, 10]
Peek:   30
Size:   3
Pop:    30
Pop:    20
Stack (top→bottom): [10]
Search 10: 1

Dry Run: Push and Pop Sequence

Trace every pointer and index change for the array-backed stack:

ArrayStack, internal data = []

push(10):
  data.add(10) → data = [10]
  top = data[size-1] = data[0] = 10

push(20):
  data.add(20) → data = [10, 20]
  top = data[1] = 20

push(30):
  data.add(30) → data = [10, 20, 30]
  top = data[2] = 30

peek():
  return data[size-1] = data[2] = 30   ← no change to data

pop():
  value = data.remove(data.size()-1) = data.remove(2) = 30
  data = [10, 20]
  return 30

pop():
  value = data.remove(1) = 20
  data = [10]
  return 20

isEmpty():
  data.size() == 0? → false

pop():
  value = data.remove(0) = 10
  data = []
  return 10

isEmpty():
  data.size() == 0? → true

Dry Run: Linked-List Stack Push and Pop

LinkedStack, head = null, size = 0

push(10):
  newNode(10).next = null (head)
  head = newNode(10)
  size = 1
  List: head → [10] → null

push(20):
  newNode(20).next = head = Node(10)
  head = newNode(20)
  size = 2
  List: head → [20] → [10] → null

push(30):
  newNode(30).next = head = Node(20)
  head = newNode(30)
  size = 3
  List: head → [30] → [20] → [10] → null

peek():
  return head.data = 30   ← head unchanged

pop():
  value = head.data = 30
  head  = head.next = Node(20)
  size  = 2
  return 30
  List: head → [20] → [10] → null

pop():
  value = head.data = 20
  head  = head.next = Node(10)
  size  = 1
  return 20
  List: head → [10] → null

Operation 1: Push — Deep Dive

Push is the only write operation that adds data. It always places the new element at the top — no searching, no shifting.

Array-backed:
  Append to end of dynamic array.
  If array is full → resize (double capacity), then append.
  Amortized O(1): occasional O(n) resize is absorbed over n pushes.

Linked-list-backed:
  Allocate a new node.
  Set newNode.next = head.
  Set head = newNode.
  Always O(1) — no resizing ever needed.

Edge case — pushing null:
  Java: null is a valid element — push(null) works.
  Python: None is valid — stack.append(None) works.
  C++: depends on type — pointers can be nullptr.
  JavaScript: null and undefined are valid values.

  If null means "empty" in your algorithm, track it separately
  rather than relying on stack.isEmpty().

Java

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

public class PushDemo {

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

        // Push sequence
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("After pushes: " + stack); // [30, 20, 10]

        // Push edge cases
        // stack.push(null); // NullPointerException for ArrayDeque — it disallows null
        // Use Integer or box type; ArrayDeque does not permit null elements

        // Capacity — ArrayDeque resizes automatically
        Deque<Integer> big = new ArrayDeque<>();
        for (int i = 0; i < 1000; i++) big.push(i);
        System.out.println("After 1000 pushes, size: " + big.size()); // 1000
    }
}

Operation 2: Pop — Deep Dive

Pop removes and returns the top element. The most critical edge case is popping from an empty stack — every production implementation must guard against this.

Approaches to empty stack:
  1. Throw an exception  — caller must check isEmpty() first
  2. Return null/None    — safe but loses type safety
  3. Return Optional     — Java Optional<T> pattern

Best practice for interviews:
  Always check isEmpty() before pop() in your code.
  State the assumption: "I'll assume the stack is non-empty here."
  or: "Let me add a guard for the empty case."

Java

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

public class PopDemo {

    // Safe pop — returns Optional to avoid null returns
    public static <T> Optional<T> safePop(Deque<T> stack) {
        if (stack.isEmpty()) return Optional.empty();
        return Optional.of(stack.pop());
    }

    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10); stack.push(20); stack.push(30);

        // Standard pop — throws on empty
        System.out.println("Pop: " + stack.pop());   // 30
        System.out.println("Pop: " + stack.pop());   // 20
        System.out.println("Pop: " + stack.pop());   // 10

        // Safe pop pattern
        Optional<Integer> result = safePop(stack);
        System.out.println("Safe pop empty: " + result.isPresent()); // false

        // poll() — returns null instead of throwing
        Deque<Integer> s2 = new ArrayDeque<>();
        s2.push(42);
        System.out.println("Poll: "  + s2.poll());  // 42
        System.out.println("Poll: "  + s2.poll());  // null (not exception)
    }
}

Output (Java):
Pop: 30
Pop: 20
Pop: 10
Safe pop empty: false
Poll: 42
Poll: null

Operation 3: Peek — Reading Without Consuming

Peek (also called top() in C++) reads the top element without removing it. It is O(1) and does not change the stack's state.

When to use peek vs pop:

  Use PEEK when:
    You need to know what the top is to decide what to do next,
    but you are not sure yet whether to remove it.

  Use POP when:
    You are done with the top element and want to process it.

Example — balanced parentheses:
  When you see ')', peek the stack to check what's on top.
  If it matches, THEN pop (consume the match).
  If it does not match, the expression is invalid.
  Peeking first avoids popping prematurely.

Java

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

public class PeekDemo {

    public static void main(String[] args) {
        Deque<Character> stack = new ArrayDeque<>();
        stack.push('(');
        stack.push('[');
        stack.push('{');

        System.out.println("Peek: " + stack.peek());   // {
        System.out.println("Size: " + stack.size());   // 3 — unchanged

        // Peek then decide
        char top = stack.peek();
        if (top == '{') {
            System.out.println("Top is opening brace — match it");
            stack.pop();
        }

        System.out.println("Peek after pop: " + stack.peek()); // [
        System.out.println("Size: " + stack.size());            // 2
    }
}

Array-Backed vs Linked-List-Backed — When to Choose

Array-backed stack:
  Memory:         Contiguous — good cache locality
  Overhead:       Zero per element (just the value)
  Resize:         Automatic doubling — O(n) occasionally, O(1) amortized
  Max capacity:   Limited by available heap memory
  Best for:       Most use cases — faster in practice due to cache

Linked-list-backed stack:
  Memory:         Scattered nodes — cache misses on every push/pop
  Overhead:       One pointer per node (~8 bytes on 64-bit systems)
  Resize:         Never resizes — each node allocated individually
  Max capacity:   Limited only by heap memory (no pre-allocation)
  Best for:       When you need guaranteed O(1) (no amortized),
                  or when stack and linked list structure must be shared

For interview problems:
  Use the built-in (Java Deque/ArrayDeque, Python list, C++ stack, JS array).
  Implementing from scratch is only asked when the problem specifically requires
  showing you understand the underlying mechanics.

Operation Complexity Summary

Operation	Array-Backed	Linked-List-Backed	Notes
push	O(1) amortized	O(1)	Array may resize occasionally
pop	O(1)	O(1)	Array just decrements size
peek	O(1)	O(1)	Read last/head element
isEmpty	O(1)	O(1)	Compare size to 0
size	O(1)	O(1)	Stored as a field
clear	O(1)*	O(n) C++, O(1) others	C++ must free each node
search	O(n)	O(n)	Linear scan from top

*O(1) for languages with GC — just drop the reference. O(n) in C++ to free each node.

Common Mistakes Beginners Make

Popping from an empty stack without checking. Always call isEmpty() before pop() or peek(). Java's ArrayDeque.pop() throws NoSuchElementException; C++'s stack::pop() causes undefined behavior; Python raises IndexError. Develop the habit of checking before every pop.

Using Stack<E> in Java. Java's legacy Stack<E> class extends Vector, which is synchronized. Every operation acquires a lock — unnecessary overhead in single-threaded code. Use Deque<E> with ArrayDeque<E> instead.

Forgetting that C++ stack::pop() does not return the value. In C++, pop() removes the top element without returning it. You must call top() first to read the value, then call pop() to remove it. Calling pop() and trying to use its return value (void) is a compile error.

Using pop(0) on a Python list as a stack operation. list.pop(0) removes from the front — it is O(n). A stack uses list.pop() (no argument) to remove from the end in O(1). Using index 0 accidentally turns your stack into a queue with O(n) dequeue cost.

Confusing peek and pop in logic flow. Peek reads the top without consuming it. Pop reads AND removes. In balanced-parentheses problems, peek to check the match, then pop to confirm the consumption. Calling pop when you meant peek can silently empty your stack.

Interview Questions

Q: What is the difference between peek() and pop() on a stack?

peek() reads the top element and leaves it in the stack — the stack's state is unchanged. pop() reads the top element AND removes it — the stack shrinks by one. Both are O(1). Use peek() when you need to inspect the top to make a decision but are not ready to commit to removing it. Use pop() when you have processed the top and are done with it.

Q: Why is ArrayDeque preferred over Stack for stack operations in Java?

Java's Stack extends Vector, which synchronizes every method with a lock. In single-threaded code (all algorithm problems), this is wasted overhead — every push and pop acquires and releases a lock even though no other thread is accessing the stack. ArrayDeque provides identical push/pop/peek semantics without synchronization, making it 2-3x faster in practice. The Java documentation explicitly recommends ArrayDeque over Stack.

Q: How do you implement a stack that returns the minimum element in O(1)?

Maintain two stacks: the main data stack and an auxiliary min-stack. On every push, push to the data stack. If the new value is ≤ the min-stack's current top (or if the min-stack is empty), also push to the min-stack. On every pop from the data stack, if the popped value equals the min-stack's top, also pop from the min-stack. getMin() returns the top of the min-stack — O(1). This is the "Min Stack" interview problem.

FAQs

Does Python's list behave exactly like a stack?

Yes, for the three core operations: append(x) is push O(1) amortized, pop() is pop O(1), and list[-1] is peek O(1). Python's list is array-backed with automatic resizing — the same implementation as Java's ArrayDeque. The difference is that list also supports O(n) operations like insert(0, x) and pop(0) that violate the stack abstraction — you can call them, but doing so makes the structure behave as something other than a pure stack.

Is the call stack the same as the stack data structure?

Yes — the call stack is a specific instance of the stack data structure managed by the language runtime. Each function call pushes a stack frame containing local variables, parameters, and the return address. Returning pops the frame. The LIFO property means the most recently called function is the first to return — which is exactly how nested function calls must behave. A "stack overflow" error means the call stack exceeded its memory limit, usually caused by infinite recursion.

Can a stack contain elements of different types?

In statically typed languages (Java, C++), a stack is typed — all elements must be the same declared type. Use generics (Stack<Object> in Java, stack<variant<...>> in C++) for mixed types, though this is rare. In Python and JavaScript, a single stack can hold any mix of types since the languages are dynamically typed. In algorithm problems, stacks are almost always homogeneous — all integers or all characters.

Quick Quiz

Question 1: You push A, B, C onto a stack. What is returned by two consecutive pops?

›A) A, B
›B) B, C
›C) C, B
›D) C, A

Answer: C) C, B. The stack is [A (bottom), B, C (top)]. First pop returns C (the top). Second pop returns B (the new top). LIFO — last in, first out.

Question 2: What does peek() return for a stack containing [10 (bottom), 20, 30 (top)]?

›A) 10
›B) 20
›C) 30
›D) The entire stack

Answer: C) 30. peek() always returns the top element without removing it. The top is 30 — the most recently pushed element that has not yet been popped.

Question 3: In C++, what is the correct way to read and remove the top element from std::stack<int> st?

›A) int val = st.pop();
›B) int val = st.top(); st.pop();
›C) int val = st.peek(); st.pop();
›D) int val = st.remove();

Answer: B) Read top(), then call pop(). C++'s stack::pop() returns void — it removes but does not return the value. You must call top() first to read the value, then pop() to remove it. Option A is a compile error. Option C — peek() does not exist in C++ (top() is the method name).

Question 4: What happens if you call pop() on an empty ArrayDeque in Java?

›A) Returns null
›B) Returns 0
›C) Throws NoSuchElementException
›D) Silently does nothing

Answer: C) Throws NoSuchElementException. Java's Deque.pop() throws NoSuchElementException on empty. The alternative is Deque.poll() which returns null instead of throwing. Always check isEmpty() before calling pop() if you are not certain the stack is non-empty.

Summary

Stack operations are simple but their edge cases — especially empty stack handling — are tested constantly in interviews.

The complete operation reference:

›push(value) — O(1) amortized (array) or O(1) (linked list) — always at the top
›pop() — O(1) — removes and returns top — throws/crashes if empty — always check isEmpty() first
›peek() — O(1) — reads top without removing — use to inspect before committing
›isEmpty() — O(1) — essential guard before every pop/peek
›size() — O(1) — stored as a field in all implementations
›clear() — O(1) GC-managed / O(n) C++ — drops all elements
›search(value) — O(n) — 1-indexed distance from top

Implementation choice: array-backed is faster in practice (cache-friendly, no pointer overhead) and is the right choice for almost all interview problems. Use the built-in Deque/ArrayDeque in Java, list in Python, stack in C++, and Array in JavaScript.

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

←

PreviousStack Basics

NextStack Implementation

→