Stacks — Complete DSA Stack Theory

Learning Progress. Work top to bottom: theory → operations → the interactive visualizer → patterns → cheat sheet → interview prep. Pin the visualizer (button top-right of the panel) to keep it on screen while you read.

Theory & Fundamentals

What is a Stack?

A Stack is a linear data structure that follows LIFO (Last In, First Out): the last element pushed is the first popped. Think of a stack of plates — you add and remove from the top only.

All the main operations touch just one end (the top), so push, pop, and peek are all O(1).

Core operations

// LIFO — one end only
push(x) // add x on top — O(1)
pop() // remove top — O(1)
peek() // read top — O(1)
empty() // is it empty? — O(1)

Why Stacks? Anytime you need to reverse order or remember "where you were", a stack fits: function call frames, undo/redo, expression evaluation, backtracking, DFS, and the browser back button.

Types & Implementations

▭

Array-based

Backed by a dynamic array; top is an index. Fast, cache-friendly, may resize.

Use: default choice, std::stack over vector/deque.

🔗

Linked-list based

Push/pop at the head of a singly linked list. No resizing, extra pointer per node.

Use: unknown size, no reallocation cost.

⛰

Min / Max Stack

Augmented with an auxiliary stack tracking the running min/max in O(1).

Use: "get minimum in O(1)" interview problems.

Terminology

Top

The most recently pushed element; the only one directly accessible.

Push

Add an element on top of the stack. O(1).

Pop

Remove and return the top element. O(1).

Peek / Top

Read the top element without removing it.

Overflow

Pushing onto a full fixed-capacity stack.

Underflow

Popping from an empty stack — always guard against it.

Complexity Summary

Push

O(1)

Add to top, amortized for dynamic array.

Pop

O(1)

Remove from top.

Peek

O(1)

Read the top element.

O(n)

Must pop through to find an element.

Space

O(n)

n elements stored.

Min/Max Stack

O(1)

With an auxiliary stack.

Advantages & Disadvantages

Advantages

All core operations are O(1).
Simple, predictable LIFO semantics.
Perfect for reversal, backtracking, and recursion simulation.
Minimal memory overhead (array-based).

Disadvantages

No random access — only the top is reachable.
Searching requires popping (destroys order).
Fixed-capacity variants can overflow.
Not suitable for FIFO or middle access needs.

C++ STL Implementation

stack_stl.cpp · std::stack & manual stack

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    st.push(10);       // [10]
    st.push(20);       // [10,20]
    st.push(30);       // [10,20,30] top=30
    cout << st.top() << "\n"; // 30 — peek O(1)
    st.pop();            // removes 30
    cout << st.size() << " " << st.empty();
    return 0;
}

applications.cpp · Balanced parens & NGE

// Valid parentheses — O(n)
bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c=='('||c=='['||c=='{') st.push(c);
        else {
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if ((c==')'&&t!='(')||(c==']'&&t!='[')||(c=='}'&&t!='{')) return false;
        }
    }
    return st.empty();
}

// Next Greater Element — monotonic stack O(n)
vector<int> nge(vector<int>& a) {
    stack<int> st; vector<int> res(a.size(), -1);
    for (int i=0; i<a.size(); i++) {
        while (!st.empty() && a[st.top()] < a[i]) { res[st.top()]=a[i]; st.pop(); }
        st.push(i);
    }
    return res;
}

Interactive Stack Visualization

Element Top Pushing Popping Peek/Target

Idle

Current operation details

Operation

—

Top element

—

Operations

Steps

taken

Pushes

added

Pops

removed

Size

elements

Step — of —

Select a scenario above, or use the manual controls, then press Play.

Manual controls — build your own operation

Stack (bottom→top): Value:

✓ Done

Speed

Step-by-step operation log

Step	Top	Action	Stack State	Ops
Run a scenario to populate the log.

Key Patterns

Monotonic stack. Keep the stack increasing or decreasing to answer next-greater/smaller, largest rectangle in histogram, stock span, and trapping rain water — each element pushed and popped once, O(n) total.

Two stacks = a queue. Push onto "in"; when you need to dequeue and "out" is empty, pour everything from "in" into "out" (reversing order). Amortized O(1) per operation.

Cheat Sheet

Operation	Time	Space	Notes
Push	O(1)	O(1)	Amortized for dynamic array
Pop	O(1)	O(1)	Guard against underflow
Peek	O(1)	O(1)	Read top only
Search	O(n)	O(1)	Destroys order unless copied
Min/Max in O(1)	O(1)	O(n)	Auxiliary min/max stack
Monotonic stack	O(n)	O(n)	Each element pushed/popped once

Learning Roadmap

Stack Basics

push/pop/peek, LIFO intuition, array vs linked-list backing, overflow/underflow.

~2 hours

Classic Applications

Balanced parentheses, reverse a string, evaluate postfix, infix→postfix.

~3 hours

Monotonic Stack

Next greater/smaller, largest rectangle, stock span, trapping rain water.

~4 hours

Advanced

Min stack, two-stack queue, backtracking & DFS simulation, expression trees.

~3 hours

Interview Preparation

Valid Parentheses

Push openers, pop and match on closers. Empty stack at the end means balanced.

Matching

Min Stack

Auxiliary stack storing the running minimum, pushed/popped in lockstep. O(1) getMin.

Augmented

Largest Rectangle in Histogram

Monotonic increasing stack of indices; pop to compute area with width = i - stack.top() - 1.

Monotonic

Evaluate Reverse Polish Notation

Push numbers, on operator pop two and push the result. Single pass O(n).

Evaluation

Practice Problems

EasyValid ParenthesesMatching

EasyMin StackAugmented

EasyImplement Queue using StacksTwo Stacks

MediumDaily TemperaturesMonotonic

MediumEvaluate RPNEvaluation

MediumAsteroid CollisionSimulation

HardLargest Rectangle in HistogramMonotonic

HardTrapping Rain WaterMonotonic

Key Takeaways

📚LIFO: last in, first out. One end (the top) does all the work, so push/pop/peek are O(1).

🧮Expressions & matching: parentheses, postfix evaluation, and infix conversion are textbook stack jobs.

📈Monotonic stack: the highest-value pattern — next greater/smaller, histograms, rain water, all O(n).

🔁Recursion = stack: the call stack IS a stack. Any recursion can be rewritten iteratively with an explicit stack.