Stacks

November 19, 2025
#stack #data-structures #lifo #algorithms #interviewing

Table of Contents

Introduction

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of plates: you can only add or remove plates from the top. The last plate you place on the stack is the first one you’ll take off.

Stacks are fundamental in computer science and appear everywhere—from the call stack that tracks function calls in your program to undo/redo functionality in text editors. By the end of this tutorial, you’ll understand how stacks work, when to use them, and how to implement them efficiently.

If you’re new to time and space complexity, start with our guide to Big-O Notation. You may also want to review Arrays and Linked Lists to understand the underlying implementation options.

What is a stack?

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

  1. Push: Add an element to the top of the stack
  2. Pop: Remove and return the element from the top of the stack

Additionally, most stack implementations include: 3. Peek (or Top): View the top element without removing it 4. IsEmpty: Check if the stack is empty 5. Size: Get the number of elements in the stack

The key constraint: you can only access the most recently added element (the “top”).

Why use a stack?

Choose a stack when:

  1. You need LIFO (Last-In-First-Out) access to data
  2. You’re tracking state that needs to be reversed or unwound (e.g., undo operations, backtracking)
  3. You need to evaluate expressions or parse syntax (e.g., matching parentheses, expression evaluation)
  4. You’re implementing recursive algorithms iteratively
  5. You need to traverse trees or graphs using depth-first search (DFS)

Avoid a stack when:

  • You need random access to elements (use an array instead)
  • You need First-In-First-Out (FIFO) access (use a queue instead)
  • You need to search through all elements frequently

Real-world applications

Stacks are used in many practical scenarios:

  • Function call stack: Programming languages use a stack to track function calls and local variables
  • Browser history: The back button uses a stack to navigate previous pages
  • Undo/Redo: Text editors and graphics programs use stacks to track changes
  • Expression evaluation: Calculators use stacks to evaluate mathematical expressions
  • Syntax parsing: Compilers use stacks to parse code and match brackets/parentheses
  • Backtracking algorithms: Maze solving, puzzle solving, and game AI use stacks

Core operations and complexity

All primary stack operations are extremely efficient:

  • Push: O(1) — add element to top
  • Pop: O(1) — remove and return top element
  • Peek/Top: O(1) — view top element without removing
  • IsEmpty: O(1) — check if stack is empty
  • Size: O(1) — get number of elements
  • Space: O(n) — where n is the number of elements in the stack

Stack implementation

Stacks can be implemented using either arrays or linked lists. Array-based implementations are simpler and have better cache locality, while linked list implementations never need resizing.

Array-based stack

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.items.length - 1];
  }

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

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

  clear() {
    this.items = [];
  }
}

// Example usage
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek());    // 30
console.log(stack.pop());     // 30
console.log(stack.pop());     // 20
console.log(stack.size());    // 1
console.log(stack.isEmpty()); // false

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

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

    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]

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

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

    def clear(self):
        self.items = []

# Example usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.peek())      # 30
print(stack.pop())       # 30
print(stack.pop())       # 20
print(stack.size())      # 1
print(stack.is_empty())  # False

import java.util.ArrayList;

public class Stack {
    private ArrayList<Integer> items;

    public Stack() {
        items = new ArrayList<>();
    }

    public void push(int element) {
        items.add(element);
    }

    public Integer pop() {
        if (isEmpty()) {
            return null;
        }
        return items.remove(items.size() - 1);
    }

    public Integer peek() {
        if (isEmpty()) {
            return null;
        }
        return items.get(items.size() - 1);
    }

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

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

    public void clear() {
        items.clear();
    }

    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.peek());    // 30
        System.out.println(stack.pop());     // 30
        System.out.println(stack.pop());     // 20
        System.out.println(stack.size());    // 1
        System.out.println(stack.isEmpty()); // false
    }
}

Linked list-based stack

For an alternative implementation using linked lists, we can use a singly linked list where we push and pop from the head:

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedStack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(element) {
    this.top = new Node(element, this.top);
    this.length++;
  }

  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.top.value;
    this.top = this.top.next;
    this.length--;
    return value;
  }

  peek() {
    return this.isEmpty() ? undefined : this.top.value;
  }

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

  size() {
    return this.length;
  }
}

// Example usage
const stack = new LinkedStack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop());  // 20

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedStack:
    def __init__(self):
        self.top = None
        self.length = 0

    def push(self, element):
        self.top = Node(element, self.top)
        self.length += 1

    def pop(self):
        if self.is_empty():
            return None
        value = self.top.value
        self.top = self.top.next
        self.length -= 1
        return value

    def peek(self):
        return None if self.is_empty() else self.top.value

    def is_empty(self):
        return self.length == 0

    def size(self):
        return self.length

# Example usage
stack = LinkedStack()
stack.push(10)
stack.push(20)
print(stack.peek())  # 20
print(stack.pop())   # 20

class Node {
    int value;
    Node next;
    Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

public class LinkedStack {
    private Node top;
    private int length;

    public LinkedStack() {
        this.top = null;
        this.length = 0;
    }

    public void push(int element) {
        top = new Node(element, top);
        length++;
    }

    public Integer pop() {
        if (isEmpty()) {
            return null;
        }
        int value = top.value;
        top = top.next;
        length--;
        return value;
    }

    public Integer peek() {
        return isEmpty() ? null : top.value;
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public int size() {
        return length;
    }

    public static void main(String[] args) {
        LinkedStack stack = new LinkedStack();
        stack.push(10);
        stack.push(20);
        System.out.println(stack.peek()); // 20
        System.out.println(stack.pop());  // 20
    }
}

Common stack problems

1. Balanced parentheses

Check if a string of parentheses, brackets, and braces is balanced:

function isBalanced(str) {
  const stack = [];
  const pairs = { '(': ')', '[': ']', '{': '}' };

  for (let char of str) {
    if (char in pairs) {
      // Opening bracket
      stack.push(char);
    } else if (Object.values(pairs).includes(char)) {
      // Closing bracket
      if (stack.length === 0) return false;
      const last = stack.pop();
      if (pairs[last] !== char) return false;
    }
  }

  return stack.length === 0;
}

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

def is_balanced(s):
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}

    for char in s:
        if char in pairs:
            # Opening bracket
            stack.append(char)
        elif char in pairs.values():
            # Closing bracket
            if not stack:
                return False
            last = stack.pop()
            if pairs[last] != char:
                return False

    return len(stack) == 0

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

import java.util.HashMap;
import java.util.Stack;

public class BalancedParens {
    public static boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> pairs = new HashMap<>();
        pairs.put('(', ')');
        pairs.put('[', ']');
        pairs.put('{', '}');

        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) {
                // Opening bracket
                stack.push(c);
            } else if (pairs.containsValue(c)) {
                // Closing bracket
                if (stack.isEmpty()) return false;
                char last = stack.pop();
                if (pairs.get(last) != c) return false;
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("({[]})"));  // true
        System.out.println(isBalanced("([)]"));    // false
        System.out.println(isBalanced("((()"));    // false
    }
}

2. Reverse a string

Stacks naturally reverse the order of elements:

function reverseString(str) {
  const stack = [];
  for (let char of str) {
    stack.push(char);
  }

  let reversed = '';
  while (stack.length > 0) {
    reversed += stack.pop();
  }
  return reversed;
}

console.log(reverseString("hello")); // "olleh"

def reverse_string(s):
    stack = []
    for char in s:
        stack.append(char)

    reversed_str = ''
    while stack:
        reversed_str += stack.pop()
    return reversed_str

print(reverse_string("hello"))  # "olleh"

import java.util.Stack;

public class ReverseString {
    public static String reverse(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            stack.push(c);
        }

        StringBuilder reversed = new StringBuilder();
        while (!stack.isEmpty()) {
            reversed.append(stack.pop());
        }
        return reversed.toString();
    }

    public static void main(String[] args) {
        System.out.println(reverse("hello")); // "olleh"
    }
}

3. Evaluate postfix expression

Evaluate expressions in Reverse Polish Notation (e.g., “2 3 + 4 *” = 20):

function evaluatePostfix(expr) {
  const stack = [];
  const tokens = expr.split(' ');

  for (let token of tokens) {
    if (!isNaN(token)) {
      stack.push(Number(token));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(Math.floor(a / b)); break;
      }
    }
  }

  return stack.pop();
}

console.log(evaluatePostfix("2 3 + 4 *")); // 20
console.log(evaluatePostfix("5 1 2 + 4 * + 3 -")); // 14

def evaluate_postfix(expr):
    stack = []
    tokens = expr.split()

    for token in tokens:
        if token.lstrip('-').isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(int(a / b))

    return stack.pop()

print(evaluate_postfix("2 3 + 4 *"))  # 20
print(evaluate_postfix("5 1 2 + 4 * + 3 -"))  # 14

import java.util.Stack;

public class PostfixEvaluator {
    public static int evaluate(String expr) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expr.split(" ");

        for (String token : tokens) {
            if (token.matches("-?\\d+")) {
                stack.push(Integer.parseInt(token));
            } else {
                int b = stack.pop();
                int a = stack.pop();
                switch (token) {
                    case "+": stack.push(a + b); break;
                    case "-": stack.push(a - b); break;
                    case "*": stack.push(a * b); break;
                    case "/": stack.push(a / b); break;
                }
            }
        }

        return stack.pop();
    }

    public static void main(String[] args) {
        System.out.println(evaluate("2 3 + 4 *")); // 20
        System.out.println(evaluate("5 1 2 + 4 * + 3 -")); // 14
    }
}

Stack variations and extensions

  • Min/Max Stack: Augmented stack that tracks minimum or maximum element in O(1) time
  • Two-stack queue: Implement a queue using two stacks
  • Fixed-size stack: Stack with a maximum capacity (useful for memory-constrained systems)
  • Thread-safe stack: Synchronized stack for concurrent programming

Common pitfalls

  • Stack overflow: Pushing too many elements can exhaust memory (especially with fixed-size implementations)
  • Underflow: Popping from an empty stack should be handled gracefully
  • Memory leaks: In languages with manual memory management, ensure popped nodes are freed
  • Not checking isEmpty: Always verify the stack isn’t empty before calling pop() or peek()

When to prefer other data structures

  • Need FIFO access → Use a queue
  • Need random access by index → Use an array
  • Need to search all elements → Use a hash table or sorted array with binary search
  • Need sorted data → Use a binary search tree or heap

Practice problems

  1. Implement a min-stack that supports push, pop, peek, and getMin (return minimum element) all in O(1) time
  2. Implement a queue using two stacks
  3. Use a stack to implement depth-first search (DFS) on a graph or tree
  4. Write a function to simplify a Unix file path (e.g., “/a/./b/../../c/” → “/c”)
  5. Design a browser back/forward button system using stacks
  6. Evaluate infix expressions (e.g., “2 + 3 * 4”) by converting to postfix first
  7. Implement an undo/redo system for a text editor using two stacks

Complexity summary

All core stack operations are extremely efficient:

  • Time complexity:
    • Push: O(1)
    • Pop: O(1)
    • Peek: O(1)
    • IsEmpty: O(1)
    • Size: O(1)
  • Space complexity: O(n) where n is the number of elements

This constant-time performance for all operations makes stacks one of the most efficient data structures for LIFO access patterns.

Thanks for visiting
We are actively updating content to this site. Thanks for visiting! Please bookmark this page and visit again soon.
Sponsor