Stacks in Data Structures | DSAMaster

What is a Stack?

A Stack is a linear data structure that follows the LIFO principle — Last In, First Out. Think of a physical stack of plates: you always place a new plate on top, and you always take the top plate first. You can't access the middle or bottom without removing everything above.

Stack of Plates:
  
  [ Plate 3 ]   ← TOP (most recently added, first to be removed)
  [ Plate 2 ]
  [ Plate 1 ]   ← BOTTOM (first added, last to be removed)
  ─────────────

Stacks are surprisingly powerful. They appear in:

Your browser's Back button (URL history stack)
Your text editor's Ctrl+Z (undo stack)
The CPU's call stack (function call tracking)
Compilers (expression evaluation, syntax checking)
DFS graph traversal (using an explicit or implicit call stack)

Core Operations

Operation	Description	Time Complexity
`push(x)`	Add element x to the top	O(1)
`pop()`	Remove and return the top element	O(1)
`peek()` / `top()`	View the top element without removing	O(1)
`isEmpty()`	Check if the stack is empty	O(1)
`size()`	Return the number of elements	O(1)

Space Complexity: O(N) where N is the number of elements.

Stack Implementation from Scratch

Array-Based Stack

javascript
class Stack {
    constructor() {
        this.items = [];
    }

    push(element) {
        this.items.push(element);  // O(1) amortized
    }

    pop() {
        if (this.isEmpty()) throw new Error("Stack Underflow");
        return this.items.pop();   // O(1)
    }

    peek() {
        if (this.isEmpty()) throw new Error("Stack is empty");
        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

// Usage
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek());  // 30 — top without removing
console.log(stack.pop());   // 30 — removes and returns
console.log(stack.size());  // 2

Python:

python
class Stack:
    def __init__(self):
        self.items = []

    def push(self, element):
        self.items.append(element)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack Underflow")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

C++:

cpp
#include <iostream>
#include <stack>   // STL Stack
#include <stdexcept>

// Using STL
std::stack<int> st;
st.push(10);
st.push(20);
st.push(30);
std::cout << st.top() << "\n";  // 30
st.pop();
std::cout << st.top() << "\n";  // 20

Built-in Stack Usage (STL / Collections)

In interviews, use the built-in stack/list instead of implementing from scratch:

JavaScript: Arrays serve as stacks — arr.push() and arr.pop() are O(1). Python: Lists serve as stacks — list.append() and list.pop() are O(1). Java: Use Deque<Integer> stack = new ArrayDeque<>() — stack.push() and stack.pop(). C++: Use std::stack<int> from <stack> header.

Solved Problem 1: Valid Parentheses 🟢 Easy

Problem: Given a string s containing only characters (, ), {, }, [, ], determine if the input string is valid. An input string is valid if open brackets are closed by the same type of bracket in the correct order.

Examples:

"()"          → true
"()[]{}"      → true
"(]"          → false
"([)]"        → false
"{[]}"        → true

The Stack Insight: When we see an opening bracket, we push it. When we see a closing bracket, the top of the stack must be its matching opener. If it doesn't match, or the stack is empty when we expect an opener — return false.

Step-by-Step Dry Run for {[()]}:

s = { [ ( ) ] }
Stack: []

Process '{': opening → push → Stack: ['{']
Process '[': opening → push → Stack: ['{', '[']
Process '(': opening → push → Stack: ['{', '[', '(']
Process ')': closing ')' → top is '(' → match! pop → Stack: ['{', '[']
Process ']': closing ']' → top is '[' → match! pop → Stack: ['{']
Process '}': closing '}' → top is '{' → match! pop → Stack: []

Stack is empty → return true ✅

Dry Run for ([)]:

s = ( [ ) ]
Process '(': push → Stack: ['(']
Process '[': push → Stack: ['(', '[']
Process ')': closing ')' → top is '[' → NO MATCH! → return false ✅

JavaScript Solution:

javascript
function isValid(s) {
    const stack = [];
    const matchMap = { ')': '(', ']': '[', '}': '{' };

    for (const ch of s) {
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch);   // opening bracket → push
        } else {
            // closing bracket → must match the top
            if (stack.length === 0 || stack[stack.length - 1] !== matchMap[ch]) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.length === 0;  // stack must be empty at end
}

console.log(isValid("()[]{}"));  // true
console.log(isValid("([)]"));    // false
console.log(isValid("{[]}"));    // true

Python Solution:

python
def is_valid(s):
    stack = []
    match_map = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != match_map[ch]:
                return False
            stack.pop()

    return len(stack) == 0

Time: O(N) — single pass through the string
Space: O(N) — worst case all opening brackets
ThinkBuddy Hint: The key insight is that the stack always maintains a "waiting list" of openers that need their matching closer. A closer must always match the most recently seen unmatched opener.

Solved Problem 2: Next Greater Element 🟡 Medium

Problem: Given a circular array nums, find the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversal-order next in the array (going right, circularly). If it doesn't exist, return -1.

Example:

Input:  [1, 2, 1]
Output: [2, -1, 2]

Explanation:
- 1 at index 0 → next greater to its right = 2
- 2 at index 1 → no greater number exists → -1
- 1 at index 2 → going circularly, next greater = 2 (at index 0)

The Monotonic Stack Technique:

A monotonic stack is a stack where elements are maintained in a strictly increasing or decreasing order. For "next greater element" problems, we maintain a monotonic decreasing stack of indices.

Intuition: Think of people standing in a line.
Each person is looking RIGHT for someone TALLER.
The stack holds indices of people who haven't found 
their "next taller person" yet.

Algorithm:

Traverse the array twice (0 to 2n-1) using index % n to simulate circular behavior
Maintain a stack of indices whose "next greater" hasn't been found
For each element: pop all stack entries whose values are less than current element — current is their "next greater"

Dry-Run for [1, 2, 1] (circular, 2 passes):

result = [-1, -1, -1]   stack = []

i=0 (index 0, val=1): stack empty → push 0 → Stack: [0]
i=1 (index 1, val=2): 
  nums[stack.top()]=nums[0]=1 < 2 → pop 0, result[0]=2 → Stack: []
  stack empty → push 1 → Stack: [1]
i=2 (index 2, val=1): nums[1]=2 > 1 → push 2 → Stack: [1, 2]
i=3 (index 0, val=1): nums[2]=1 not < 1 → nums[1]=2 not < 1 → nothing
i=4 (index 1, val=2): nums[2]=1 < 2 → pop 2, result[2]=2 → Stack: [1]
  nums[1]=2 not < 2 → stop
i=5 (index 2, val=1): nothing

result = [2, -1, 2] ✅

JavaScript Solution:

javascript
function nextGreaterElements(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = [];  // stores indices, monotonic decreasing by value

    // Traverse twice to simulate circular array
    for (let i = 0; i < 2 * n; i++) {
        const curr = nums[i % n];

        // Pop all elements smaller than current — current is their NGE
        while (stack.length > 0 && nums[stack[stack.length - 1]] < curr) {
            const idx = stack.pop();
            result[idx] = curr;
        }

        // Only push indices in first pass
        if (i < n) stack.push(i);
    }

    return result;
}

console.log(nextGreaterElements([1, 2, 1]));     // [2, -1, 2]
console.log(nextGreaterElements([1, 2, 3, 4, 3])); // [2, 3, 4, -1, 4]

Python Solution:

python
def next_greater_elements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # monotonic decreasing stack of indices

    for i in range(2 * n):
        curr = nums[i % n]
        while stack and nums[stack[-1]] < curr:
            idx = stack.pop()
            result[idx] = curr
        if i < n:
            stack.append(i)

    return result

Time: O(N) — each element pushed and popped at most once
Space: O(N) — stack and result array
ThinkBuddy Hint: The monotonic stack is the key pattern for any "next greater/smaller element" problem. Maintaining decreasing order means that when you find a larger element, all the smaller ones waiting in the stack get their answer at once.

Solved Problem 3: Largest Rectangle in Histogram 🔴 Hard

Problem: Given an array heights representing the histogram's bar heights where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Example:

heights = [2, 1, 5, 6, 2, 3]

Histogram:
    █
  █ █
  █ █ █
  █ █ █
█ █ █ █ █
█ █ █ █ █ █

Answer: 10 (rectangle of height 5 spanning indices 2-3 → width 2, area = 5*2=10)

The Stack Insight: For each bar, the maximum rectangle that can be formed using it as the shortest bar extends:

left until we hit a bar shorter than it
right until we hit a bar shorter than it

We use a monotonic increasing stack to efficiently track left boundaries.

Algorithm (using sentinel values):

Add 0 at start and end of heights to handle edge cases easily.
Maintain a stack of indices in increasing height order.
When current height < heights[stack.top()]:
    Pop the top (it's the shortest bar in the rectangle)
    Width = current_index - stack.top() - 1
    Area = popped_height × width
    Track maximum area

Dry-Run for [2, 1, 5, 6, 2, 3]:

Extended heights: [0, 2, 1, 5, 6, 2, 3, 0]
indices:           0  1  2  3  4  5  6  7

stack=[0], process index 1 (h=2): 2>0 → push → stack=[0,1]
stack=[0,1], process index 2 (h=1): 
  1<2 → pop 1 (h=2), width=2-0-1=1, area=2×1=2 → max=2
  1>0 → push → stack=[0,2]
process index 3 (h=5): 5>1 → push → stack=[0,2,3]
process index 4 (h=6): 6>5 → push → stack=[0,2,3,4]
process index 5 (h=2):
  2<6 → pop 4 (h=6), width=5-3-1=1, area=6×1=6 → max=6
  2<5 → pop 3 (h=5), width=5-2-1=2, area=5×2=10 → max=10 ✅
  2>1 → push → stack=[0,2,5]
process index 6 (h=3): 3>2 → push → stack=[0,2,5,6]
process index 7 (h=0):
  0<3 → pop 6 (h=3), width=7-5-1=1, area=3×1=3
  0<2 → pop 5 (h=2), width=7-2-1=4, area=2×4=8
  0<1 → pop 2 (h=1), width=7-0-1=6, area=1×6=6
  stack=[0], 0 not > 0, stop

Maximum area = 10 ✅

JavaScript Solution:

javascript
function largestRectangleArea(heights) {
    const h = [0, ...heights, 0];  // sentinel 0s at both ends
    const stack = [0];             // monotonic increasing stack of indices
    let maxArea = 0;

    for (let i = 1; i < h.length; i++) {
        while (h[i] < h[stack[stack.length - 1]]) {
            const height = h[stack.pop()];
            const width = i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }

    return maxArea;
}

console.log(largestRectangleArea([2, 1, 5, 6, 2, 3]));  // 10
console.log(largestRectangleArea([2, 4]));               // 4
console.log(largestRectangleArea([1]));                  // 1

Python Solution:

python
def largest_rectangle_area(heights):
    h = [0] + heights + [0]
    stack = [0]
    max_area = 0

    for i in range(1, len(h)):
        while h[i] < h[stack[-1]]:
            height = h[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Time: O(N) — each bar pushed and popped exactly once
Space: O(N) — stack size
ThinkBuddy Hint: This is the canonical hard-level monotonic stack problem. The sentinel 0 values at both ends eliminate the need for special cases for the leftmost and rightmost bars. The stack always stores indices of bars in increasing height order, so when we pop a bar, we know exactly how wide the rectangle extends.

Bonus: Min Stack Design

Problem: Design a stack that supports push, pop, top, and getMin — all in O(1) time.

Approach: Use a second "min stack" that tracks the minimum at each stack level.

javascript
class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];  // parallel stack tracking current minimum
    }

    push(val) {
        this.stack.push(val);
        const currentMin = this.minStack.length === 0
            ? val
            : Math.min(val, this.minStack[this.minStack.length - 1]);
        this.minStack.push(currentMin);
    }

    pop() {
        this.stack.pop();
        this.minStack.pop();
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

const ms = new MinStack();
ms.push(-2);
ms.push(0);
ms.push(-3);
console.log(ms.getMin()); // -3
ms.pop();
console.log(ms.top());    // 0
console.log(ms.getMin()); // -2

Common Mistakes in Stack Problems

Not checking isEmpty() before pop/peek: Always check if the stack is empty before accessing the top, or use a sentinel value to avoid this edge case.
Pushing indices vs. values: For next greater element type problems, push indices (not values) so you can calculate widths and update the result array. Beginners often push values and then can't track positions.
Monotonic stack direction confusion: For "next greater element" use a decreasing stack (pop when current > top). For "largest rectangle" use an increasing stack (pop when current < top). Mix these up and you get wrong answers.
Forgetting the circular pass: For circular array problems like "Next Greater Element II", you must traverse 2N elements (or use modulo i % n) to handle the wrap-around.
Missing unprocessed elements at the end: After the main loop, the stack may still have elements. These didn't find their "next greater" → their result remains -1. Don't forget to handle remaining stack entries.

Real World Applications

Browser Back/Forward: Each tab maintains a navigation history stack. Pressing Back pops the current URL, pushing it onto the Forward stack.
Function Call Stack: When funcA() calls funcB(), the return address of funcA is pushed on the call stack. When funcB returns, the address is popped and execution resumes in funcA. Stack overflow happens when recursion is too deep.
Undo/Redo in Text Editors: Every action pushes onto the undo stack. Ctrl+Z pops from undo and pushes onto redo stack.
Compiler Syntax Checking: When parsing code, compilers use a stack to verify that all opened brackets, blocks ({}), and tags (<div></div>) are properly closed and nested.
Expression Evaluation: Calculators evaluate 3 + 4 × 2 using an operator stack to respect precedence rules (shunting-yard algorithm).

Frequently Asked Questions

Q: What is a monotonic stack and when do I use it?
A: A monotonic stack maintains elements in strictly increasing or decreasing order. You pop elements that violate the order. Use it for problems involving "next greater/smaller element", "span/range calculations", and histogram area problems. The key insight: when you pop an element because a new element violates the order, the new element is the answer for the popped element.

Q: What is the difference between a stack and a queue?
A: A Stack is LIFO (Last In, First Out) — operations happen at the same end (top). A Queue is FIFO (First In, First Out) — insertion at back, removal at front. Use a stack for DFS, undo/redo, bracket matching. Use a queue for BFS, task scheduling, level-order traversal.

Q: Can I implement a queue using two stacks?
A: Yes — this is a classic interview question. Use stack1 for push, stack2 for pop/peek. When stack2 is empty, transfer all elements from stack1 to stack2 (this reversal gives FIFO order). Each element moves at most twice, so amortized O(1) per operation.

Q: What is a call stack overflow?
A: Each function call pushes a stack frame onto the call stack. If recursion is too deep (thousands of calls) without a base case, the call stack fills up and the OS throws a "Stack Overflow" error. To prevent this, use iterative solutions with an explicit stack, or apply tail-call optimization (supported in some languages).

Q: How do I decide between a stack and a deque?
A: Use a stack when you only need LIFO access (one end). Use a deque (double-ended queue) when you need efficient O(1) insertion/deletion at both ends — for example, in the "Sliding Window Maximum" problem where you need to remove expired elements from the front and maintain a monotonic structure from the back.

Q: What is the space complexity of recursive DFS vs. iterative DFS?
A: Both are O(V) in the worst case (for a path-like graph of V nodes). Recursive DFS uses the call stack implicitly — this can cause stack overflow for very deep graphs (V > 10,000 in some environments). Iterative DFS with an explicit stack avoids this OS-level limitation.