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 Basics

What Is a Stack?

A stack is a linear data structure that follows one strict rule: the last element added is the first element removed. This rule is called LIFO — Last In, First Out.

Think of a stack of plates in a cafeteria. You add plates to the top and take plates from the top. You cannot add or remove a plate from the middle or bottom without disturbing every plate above it. The plate placed last is the first one picked up.

Stack of integers — operations always happen at the TOP:

PUSH 10:         PUSH 20:         PUSH 30:         POP:
  ┌────┐           ┌────┐           ┌────┐           ┌────┐
  │ 10 │ ← TOP     │ 20 │ ← TOP     │ 30 │ ← TOP     │ 20 │ ← TOP
  └────┘           │ 10 │           │ 20 │           │ 10 │
                   └────┘           │ 10 │           └────┘
                                    └────┘

  Push adds to top.    Pop removes from top.    30 went in last, came out first.

No matter how many elements are in the stack, you can only ever interact with the top element directly.

The Three Core Operations

Every stack supports exactly three fundamental operations:

PUSH(value)
  Add a value to the top of the stack.
  Time: O(1)

POP()
  Remove and return the top value.
  Throws an error (or returns null) if the stack is empty.
  Time: O(1)

PEEK() / TOP()
  Read the top value without removing it.
  Throws an error (or returns null) if the stack is empty.
  Time: O(1)

Supporting operations:
  isEmpty()   → true if the stack has no elements
  size()      → number of elements currently in the stack

All three core operations are O(1) — they only touch the top element, never traverse the stack. This is the defining performance characteristic of a stack.

Java

import java.util.Stack;

public class StackBasics {

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

        // PUSH — add to top
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Stack after 3 pushes: " + stack); // [10, 20, 30]
        System.out.println("Size: " + stack.size());           // 3

        // PEEK — read top without removing
        System.out.println("Peek: " + stack.peek());           // 30

        // POP — remove and return top
        System.out.println("Pop:  " + stack.pop());            // 30
        System.out.println("Pop:  " + stack.pop());            // 20

        System.out.println("Stack after 2 pops: " + stack);   // [10]
        System.out.println("isEmpty: " + stack.isEmpty());     // false

        stack.pop();
        System.out.println("isEmpty after last pop: " + stack.isEmpty()); // true
    }
}

Output:
Stack after 3 pushes: [10, 20, 30]
Size: 3
Peek: 30
Pop:  30
Pop:  20
Stack after 2 pops: [10]
isEmpty: false
isEmpty after last pop: true

LIFO in Action — Dry Run

The LIFO property is best understood by tracing a sequence of pushes and pops:

Operations:  PUSH(1), PUSH(2), PUSH(3), POP, PUSH(4), POP, POP, POP

State after each operation:
  PUSH(1): top → [1]
  PUSH(2): top → [2, 1]
  PUSH(3): top → [3, 2, 1]
  POP     → returns 3,  top → [2, 1]
  PUSH(4): top → [4, 2, 1]
  POP     → returns 4,  top → [2, 1]
  POP     → returns 2,  top → [1]
  POP     → returns 1,  top → []  (empty)

Order of returned values: 3, 4, 2, 1
The last pushed element always comes out first.

Notice that 4 was pushed after 2 and came out before 2. Pushes and pops interleave arbitrarily — the LIFO rule holds at every step, not just at the end.

Key Vocabulary

Top
  The position at which all operations happen.
  The most recently pushed element that has not yet been popped.

Push
  Add an element to the top of the stack.
  The stack grows upward from the top.

Pop
  Remove and return the top element.
  The stack shrinks by one.

Peek / Top
  Read the top element without removing it.
  Does not change the stack's state.

Overflow
  Attempting to push onto a stack that has reached maximum capacity.
  (Relevant for fixed-size array-backed stacks only.)

Underflow
  Attempting to pop or peek from an empty stack.
  Causes an exception or error in all languages.

Call Stack
  The stack the runtime uses to track function calls.
  Each function call is pushed; returning from a function pops it.

Why Stacks Exist — What Problem They Solve

Stacks model situations where you need to undo or backtrack — processing in reverse order of arrival.

Problem: Process things in reverse order of when they arrived.

Example: Undo in a text editor
  You type: A, B, C
  Undo sequence: C undone first, then B, then A
  → LIFO: last action undone first

Example: Browser history
  You visit: Google → YouTube → Reddit
  Back button: Reddit first, then YouTube, then Google
  → LIFO: last visited page is first to go back to

Example: Function call stack
  main() calls foo(), foo() calls bar()
  Return order: bar() returns first, then foo(), then main()
  → LIFO: last called function returns first

Example: Expression evaluation
  Parse "3 + (4 * 2)"
  Process inner parentheses before outer → last opened = first processed
  → LIFO: last opened bracket is first closed

Every time you see "process in reverse order" or "undo the most recent action," a stack is the natural tool.

Stack vs Queue — The Fundamental Distinction

Stack and queue are the two foundational linear data structures. They differ in exactly one way: the ordering rule.

STACK (LIFO — Last In, First Out):
  Add at top, remove from top.
  Think: stack of plates, undo history, call stack.

  Push order:   1 → 2 → 3
  Pop order:    3 → 2 → 1   (reversed)

QUEUE (FIFO — First In, First Out):
  Add at back, remove from front.
  Think: checkout line, printer queue, BFS traversal.

  Enqueue order: 1 → 2 → 3
  Dequeue order: 1 → 2 → 3  (same order)

Same input, different output:

  Input sequence: A B C D
  Stack output:   D C B A   (reversed — last in first out)
  Queue output:   A B C D   (preserved — first in first out)

The ordering rule determines which tool to use.

How Stacks Are Implemented

A stack is an abstraction. The underlying storage can be either an array or a linked list.

Array-backed stack:
  ┌────┬────┬────┬────┬────┐
  │ 10 │ 20 │ 30 │    │    │
  └────┴────┴────┴────┴────┘
    0    1    2   (top=2)  ← top pointer tracks the current top index

  Push: place at index top+1, increment top   → O(1)
  Pop:  read index top, decrement top         → O(1)
  Peek: read index top                        → O(1)
  Pros: cache-friendly, no pointer overhead
  Cons: fixed capacity unless dynamic array is used

Linked-list-backed stack:
  head → [30] → [20] → [10] → null
          ↑ top

  Push: create new node, point to current head, update head → O(1)
  Pop:  read head.data, move head to head.next             → O(1)
  Peek: read head.data                                     → O(1)
  Pros: no capacity limit
  Cons: extra memory per node (pointer overhead)

In interviews, you almost never implement the storage manually — you use the built-in stack or a list/array directly. The implementation details matter for understanding performance trade-offs.

Where Stacks Appear in Real Systems

Function Call Stack
  Every function call pushes a stack frame (local variables, return address).
  Every return pops the frame.
  A "stack overflow" error means the call stack exceeded its memory limit
  (too many recursive calls without returning).

Expression Parsing
  Infix → postfix conversion uses a stack for operators.
  Evaluating postfix expressions uses a stack for operands.
  Balanced parentheses checking uses a stack for open brackets.

Undo / Redo Systems
  Text editors, image editors, IDEs — all push each action onto an undo stack.
  Ctrl+Z pops and reverses the last action.
  A separate redo stack holds undone actions.

Browser Navigation
  Back button = pop from history stack.
  Navigate to new page = push onto history stack.
  Forward button = pop from forward stack.

Depth-First Search (DFS)
  Graph traversal — push unvisited neighbors, pop to visit next.
  The call stack itself acts as the stack in recursive DFS.

Monotonic Stack
  A specialized variant where elements are kept in sorted order.
  Used to find next greater element, largest rectangle in histogram,
  and daily temperatures problems.

Stack in Each Language

Language	Class / Type	Import / Notes
Java	`Deque<E>` with `ArrayDeque`	Use `ArrayDeque` (faster than `Stack<E>`)
Java (legacy)	`Stack<E>`	`java.util.Stack` — avoid; use `Deque` instead
Python	`list`	Built-in; `append()` = push, `pop()` = pop
C++	`std::stack<T>`	`#include <stack>`
JavaScript	`Array`	Built-in; `push()` = push, `pop()` = pop

Java recommendation:
  The Stack class is a legacy class extending Vector (thread-synchronized).
  For single-threaded use, prefer:
    Deque<Integer> stack = new ArrayDeque<>();
  It has the same push/pop/peek interface and is 2-3x faster.

When to Use a Stack

Use a stack when:
  ✓ You need to process items in reverse order of arrival
  ✓ You need to "undo" or "backtrack" — most recent first
  ✓ You need to match pairs (brackets, tags, parentheses)
  ✓ You are performing depth-first traversal (iterative DFS)
  ✓ You need to track "pending" work at each nesting level
  ✓ The problem involves nested structures (expressions, HTML, directories)

Do NOT use a stack when:
  ✗ You need to access elements by index (use array)
  ✗ You need to process in arrival order (use queue)
  ✗ You need the minimum or maximum efficiently (use heap)
  ✗ You need to search by key (use hash map)

Interview recognition signals:
  "matching brackets / parentheses"  → stack
  "next greater element"             → monotonic stack
  "evaluate expression"              → stack
  "implement undo"                   → stack
  "DFS without recursion"            → explicit stack
  "valid parentheses"                → stack
  "largest rectangle"                → monotonic stack

Interview Questions

Q: What is LIFO and how does it define stack behavior?

LIFO stands for Last In, First Out. The element most recently added (the last one pushed) is the first one removed (the first one popped). Every push places a new element on top of all previous elements, and every pop removes only the top element. The middle and bottom of the stack are completely inaccessible unless all elements above are removed first.

Q: What is the time complexity of push, pop, and peek on a stack?

All three are O(1) — constant time regardless of how many elements are in the stack. Push places an element at the top, pop removes from the top, and peek reads the top. None of these operations search or traverse the stack. This O(1) guarantee holds for both array-backed and linked-list-backed implementations.

Q: What is a stack overflow?

In the context of the call stack: a stack overflow occurs when the program makes so many nested function calls that the call stack runs out of allocated memory. The most common cause is infinite recursion — a function calls itself with no base case, pushing stack frames forever until memory is exhausted. In the context of a custom fixed-capacity stack: attempting to push onto a full stack.

Q: Why should you use ArrayDeque instead of Stack in Java?

Java's Stack class extends Vector, which is synchronized (thread-safe). The synchronization overhead makes every operation slower in single-threaded environments, which is the vast majority of algorithm and interview code. ArrayDeque provides the same push/pop/peek interface without synchronization overhead and is 2-3x faster in practice. The Java documentation itself recommends ArrayDeque over Stack for stack use cases.

FAQs

Is Python's list a real stack?

Yes — Python's list supports O(1) append() (push) and O(1) pop() (pop from end) and O(1) list[-1] (peek). These three operations are all you need for a stack. The list implementation is array-backed with dynamic resizing, giving amortized O(1) push and true O(1) pop and peek. Python does not have a dedicated Stack class because list already does the job perfectly.

Can you peek at elements below the top?

No — not without violating the stack abstraction. The only accessible element is the top. If you need to access elements below the top, the structure you need is not a stack. In practice, problems that require "peek at the second element" typically work by popping the top, peeking the new top, then pushing the first element back — or by using two stacks.

What happens when you pop from an empty stack?

Java's Stack.pop() throws EmptyStackException. Java's Deque.pop() throws NoSuchElementException. Deque.poll() returns null instead of throwing. Python's list.pop() raises IndexError. C++'s stack::pop() causes undefined behavior (no exception — always check empty() first). JavaScript's Array.pop() returns undefined. Always check isEmpty() before popping to avoid runtime errors.

Is a stack the same as a call stack?

The call stack is a specific application of the stack data structure — it is the stack the runtime uses to track active function calls and their local variables. Every function call pushes a stack frame, and every return pops one. The "stack" in stack overflow error refers specifically to this call stack running out of memory. The general stack data structure you implement or use in algorithms is the same concept applied to your own data.

Quick Quiz

Question 1: You push 1, 2, 3, 4 onto a stack. Then pop twice. What is the top of the stack?

›A) 1
›B) 2
›C) 3
›D) 4

Answer: B) 2. After pushing 1, 2, 3, 4, the stack is [1, 2, 3, 4] with 4 on top. First pop removes 4. Second pop removes 3. The stack is now [1, 2] with 2 on top.

Question 2: Which problem is most naturally solved with a stack?

›A) Finding the shortest path in a graph
›B) Printing a linked list in forward order
›C) Checking if parentheses in an expression are balanced
›D) Finding the minimum element in an array

Answer: C) Checking if parentheses are balanced. Balanced parentheses is a classic stack problem — push every opening bracket, pop when a closing bracket is encountered and check for a match. The LIFO property ensures the most recently opened bracket is matched first, which is exactly how nesting works.

Question 3: What is the time complexity of all three core stack operations (push, pop, peek)?

›A) O(1) for push, O(n) for pop and peek
›B) O(n) for all three
›C) O(1) for all three
›D) O(log n) for all three

Answer: C) O(1) for all three. Push, pop, and peek always operate on the top element only. No traversal or searching is needed. The number of elements in the stack does not affect the time to access the top.

Question 4: What distinguishes a stack from a queue?

›A) Stacks hold integers; queues hold any type
›B) Stacks follow LIFO (last in, first out); queues follow FIFO (first in, first out)
›C) Stacks are faster than queues for all operations
›D) Stacks can hold more elements than queues

Answer: B) LIFO vs FIFO. This is the single defining difference. Both are linear data structures with O(1) add and remove. The stack removes in reverse insertion order; the queue removes in the same order as insertion. This difference determines which problems each structure is suited for.

Summary

A stack is a Last In, First Out data structure. All operations — push, pop, and peek — happen at the top. Nothing below the top is directly accessible.

The key ideas to carry forward:

›LIFO — last element pushed is the first element popped
›Three operations — push O(1), pop O(1), peek O(1) — always constant time
›Top is the only accessible position — no index access, no searching
›Stack overflow — call stack exhausted (infinite recursion); stack underflow — pop/peek on empty stack
›Array-backed (Java ArrayDeque, Python list, JS Array) — cache-friendly, dynamic sizing
›Linked-list-backed — no capacity limit, pointer overhead per node
›Java — use Deque<E> with ArrayDeque (not the legacy Stack<E> class)
›Recognition signals — balanced brackets, undo/backtrack, nested structure processing, DFS without recursion, next-greater-element problems

In the next topic, you will explore Stack Implementation — building a stack from scratch using both array and linked list backends, and implementing the complete API with proper edge case handling.

←

PreviousPractice Problems

NextStack Operations

→