Stack Data Structure: Complete Guide with Code Examples

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle — the last element added is the first one removed, like a stack of plates. Stacks appear in function call management, undo/redo systems, expression parsing, and dozens of interview problems.

They are one of the most fundamental data structures, and understanding them deeply unlocks problems involving balanced parentheses, browser history, and depth-first search.

Quick reference

What is a stack?

A stack is a collection of elements with two primary operations:

• Push — add an element to the top.
• Pop — remove the element from the top.

The key constraint: you can only access the top element. This LIFO discipline is what gives the stack its power.

Stack visualization (top = right):

Initial: []
Push 1:  [1]
Push 2:  [1, 2]
Push 3:  [1, 2, 3]   ← top
Pop:     [1, 2]      → returns 3
Pop:     [1]         → returns 2
Peek:    [1]         → returns 1, stack unchanged

LIFO vs FIFO

Stack implementations

Python

Python's built-in list works as a stack out of the box.

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

    def push(self, item):
        self._data.append(item)          # O(1) amortized

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()          # O(1)

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._data[-1]            # O(1)

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

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

    def __repr__(self):
        return f"Stack({self._data})"


# Usage
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.peek())   # 3
print(s.pop())    # 3
print(s.pop())    # 2
print(s.size())   # 1

For thread-safe or deque-based stacks, use collections.deque:

from collections import deque

stack = deque()
stack.append(1)     # push
stack.append(2)
stack.append(3)
top = stack[-1]     # peek → 3
val = stack.pop()   # pop  → 3

JavaScript

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

  push(item) {
    this._data.push(item);        // O(1) amortized
  }

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

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

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

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

  toString() {
    return `Stack([${this._data.join(", ")}])`;
  }
}

// Usage
const s = new Stack();
s.push("a");
s.push("b");
s.push("c");
console.log(s.peek());   // "c"
console.log(s.pop());    // "c"
console.log(s.size());   // 2

Java

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

public class Stack<T> {
    private final Deque<T> data = new ArrayDeque<>();

    public void push(T item) {
        data.push(item);              // O(1)
    }

    public T pop() {
        if (isEmpty()) throw new EmptyStackException();
        return data.pop();            // O(1)
    }

    public T peek() {
        if (isEmpty()) throw new EmptyStackException();
        return data.peek();           // O(1)
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    public int size() {
        return data.size();
    }
}

Note: Prefer Deque<T> (ArrayDeque) over java.util.Stack, which extends Vector and is synchronized (unnecessary overhead).

Go

package main

import "fmt"

type Stack[T any] struct {
    data []T
}

func (s *Stack[T]) Push(item T) {
    s.data = append(s.data, item)
}

func (s *Stack[T]) Pop() (T, bool) {
    if len(s.data) == 0 {
        var zero T
        return zero, false
    }
    top := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return top, true
}

func (s *Stack[T]) Peek() (T, bool) {
    if len(s.data) == 0 {
        var zero T
        return zero, false
    }
    return s.data[len(s.data)-1], true
}

func (s *Stack[T]) IsEmpty() bool { return len(s.data) == 0 }
func (s *Stack[T]) Size() int     { return len(s.data) }

func main() {
    s := &Stack[int]{}
    s.Push(1)
    s.Push(2)
    s.Push(3)
    if v, ok := s.Peek(); ok {
        fmt.Println(v) // 3
    }
    if v, ok := s.Pop(); ok {
        fmt.Println(v) // 3
    }
    fmt.Println(s.Size()) // 2
}

Array-based vs linked-list-based

For most purposes, the array-based implementation wins on cache performance and simplicity.

The call stack

Every programming language uses a call stack internally to manage function calls:

main() calls factorial(3)
  factorial(3) calls factorial(2)
    factorial(2) calls factorial(1)
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
main() continues

Each function call pushes a stack frame (local variables, return address). Each return pops the frame. When recursion is too deep, the call stack overflows — hence "stack overflow."

This is why recursion and explicit stacks are interchangeable: every recursive algorithm can be rewritten with an explicit stack.

Classic interview problems

1. Valid parentheses

Given a string of ()[]{}, determine if it is valid (every opener has a matching closer in correct order).

def is_valid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0

print(is_valid("()[]{}"))   # True
print(is_valid("([)]"))     # False
print(is_valid("{[]}"))     # True

Time: O(n) | Space: O(n)

2. Min stack (O(1) getMin)

Design a stack that supports push, pop, peek, and getMin in O(1).

class MinStack:
    def __init__(self):
        self._stack = []
        self._min_stack = []  # tracks current minimum

    def push(self, val: int):
        self._stack.append(val)
        min_val = min(val, self._min_stack[-1] if self._min_stack else val)
        self._min_stack.append(min_val)

    def pop(self):
        self._stack.pop()
        self._min_stack.pop()

    def top(self):
        return self._stack[-1]

    def getMin(self):
        return self._min_stack[-1]   # O(1)

ms = MinStack()
ms.push(3)
ms.push(5)
ms.push(1)
print(ms.getMin())  # 1
ms.pop()
print(ms.getMin())  # 3

3. Evaluate Reverse Polish Notation

Given tokens like ["2", "1", "+", "3", "*"], evaluate the RPN expression.

def eval_rpn(tokens: list[str]) -> int:
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),  # truncate toward zero
    }
    for t in tokens:
        if t in ops:
            b, a = stack.pop(), stack.pop()
            stack.append(ops[t](a, b))
        else:
            stack.append(int(t))
    return stack[0]

print(eval_rpn(["2", "1", "+", "3", "*"]))  # 9  → (2+1)*3
print(eval_rpn(["4", "13", "5", "/", "+"]))  # 6  → 4+(13/5)

Time: O(n) | Space: O(n)

4. Daily temperatures (next greater element)

Given daily temperatures, return how many days until a warmer day for each position.

def daily_temperatures(temps: list[int]) -> list[int]:
    result = [0] * len(temps)
    stack = []  # stores indices

    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)

    return result

print(daily_temperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

Pattern: Monotonic stack (decreasing). Pops when a larger element is found.

Time: O(n) | Space: O(n)

5. Largest rectangle in histogram

def largest_rectangle(heights: list[int]) -> int:
    stack = []  # monotonic increasing stack of indices
    max_area = 0
    heights = heights + [0]  # sentinel

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx
        stack.append((start, h))

    return max_area

print(largest_rectangle([2, 1, 5, 6, 2, 3]))  # 10

Time: O(n) | Space: O(n)

6. Decode string

"3[a2[c]]" → "accaccacc"

def decode_string(s: str) -> str:
    stack = []
    current = ""
    k = 0

    for ch in s:
        if ch.isdigit():
            k = k * 10 + int(ch)
        elif ch == '[':
            stack.append((current, k))
            current, k = "", 0
        elif ch == ']':
            prev_str, repeat = stack.pop()
            current = prev_str + current * repeat
        else:
            current += ch

    return current

print(decode_string("3[a2[c]]"))   # "accaccacc"
print(decode_string("2[abc]3[cd]")) # "abcabccdcdcd"

7. DFS with explicit stack

Replace recursion with an explicit stack for depth-first search on a graph:

def dfs_iterative(graph: dict, start: str) -> list[str]:
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph[node]):  # reversed for left-to-right order
            if neighbor not in visited:
                stack.append(neighbor)

    return order

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [], "E": [], "F": []
}
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'E', 'C', 'F']

Monotonic stack pattern

A monotonic stack maintains elements in strictly increasing or decreasing order. It solves "next greater/smaller element" problems in O(n) instead of O(n²).

Monotonic decreasing stack (for "next greater element"):

Iterate left to right. For each element:
  While stack not empty AND top < current element:
    Pop top → its "next greater" is current element
  Push current element

Common problems solved with monotonic stack:

Stack vs queue vs deque

When to use a stack

When NOT to use a stack

Common mistakes

Stack vs related structures

Frequently asked questions

Q: Is Python's list a stack?
Yes. list.append() is push and list.pop() is pop — both O(1) amortized. For performance-critical code prefer collections.deque which guarantees O(1) appends and pops.

Q: Why not use java.util.Stack?
It extends Vector, which synchronizes every method. Use ArrayDeque as a Deque — it's faster and the Java docs explicitly recommend it over Stack.

Q: How does a call stack differ from a data structure stack?
A call stack is a specific use of the stack data structure by the language runtime. It stores stack frames (local variables, return addresses). A data structure stack is a programmable container you implement yourself.

Q: Stack vs recursion — which should I use?
They are equivalent in power. Recursion is cleaner when the depth is bounded. An explicit stack avoids stack overflow for deep problems (e.g., DFS on a large graph) and is useful when you need fine-grained control.

Q: What is a monotonic stack and when is it useful?
A monotonic stack maintains elements in sorted order (increasing or decreasing) by popping elements that violate the property. It solves "next greater/smaller element" family of problems in O(n) — a major improvement over O(n²) nested loops.

Q: What is the maximum stack size?
In Python the default recursion limit is 1000 (adjustable via sys.setrecursionlimit). In Java, the JVM stack size is typically 256–1024 KB per thread (configurable via -Xss). An explicit stack on the heap is only limited by available memory.