Stack Data Structure: LIFO, Operations and Patterns

A stack is a pile: you add items on top and take them off the top, so the last item put on is the first one back. That rule is last in, first out, or LIFO. It sounds like a limitation, but it is exactly the order a whole family of problems needs: the bracket opened most recently must be closed first, the function called most recently must return first, and undo takes back the newest edit.

Why last in, first out

Is a string of brackets such as {[()]}([)] correctly nested? Counting is not enough: ([)] has one of each, yet the pairs cross. Deleting adjacent matching pairs until none are left works, but a deeply nested string loses one pair per O(n) sweep — around 5 × 10⁹ steps for n = 100,000. The insight is that a closer may only match the most recent opener not yet matched, and "most recent first" is a stack.

The same shape appears whenever work is nested or interrupted: an inner expression before the outer one, a call before its caller, the newest edit before older ones.

How a stack is stored

The usual implementation is a dynamic array plus a count, with the bottom at index 0 and the top in the last used slot. Push, pop and peek each touch that one slot, which is why they are O(1).

1. The usual stack is an array plus a count, size. The bottom is index 0 and the top is the last used slot, data[size − 1]; the slots past size are free.
2. push 4 writes data[0] = 4 and adds one to size. No other slot is touched.
3. push 7 writes data[1] = 7, one past the old top, and size becomes 2. Nothing below moves, which is why push is O(1).
4. push 2 writes data[2] = 2, one past the old top, and size becomes 3. Nothing below moves, which is why push is O(1).
5. pop subtracts one from size and returns data[2] = 2. The 2 is still in memory, but it is past size, so it no longer counts; the next push simply writes over it.
6. push 9 writes into data[2], over the stale value the pop left there. Still one write and one increment, whatever the size: O(1).
7. peek reads data[size − 1] = 9 and changes nothing. Push, pop and peek each touch one slot at the end, the one place an array can change cheaply.

When the array is full, it is replaced by one a constant factor larger and everything is copied across. That push costs O(n), but the copies are rare enough that a push is O(1) amortised: constant on average over any sequence.

A stack can also be a linked list whose head is the top: O(1) in the worst case, but every push allocates a node, so the array is usually faster.

The operations and their cost

Push, pop, peek and the size check are all O(1); searching for a value is O(n). A stack offers nothing else on purpose.

In C++, pop() returns nothing, so read top() first. In Java, use ArrayDeque: the old java.util.Stack takes a lock on every call and lets code index into the middle. In Python never use pop(0), which shifts every element, and in JavaScript remember that pop() on an empty array quietly returns undefined.

The call stack

You have used a stack in every program you have written. Each function call pushes a stack frame holding its arguments, local variables and the place to return to; each return pops it.

1. main is running and calls fact(3). A call pushes a stack frame holding the function's arguments, its local variables and where to return to.
2. fact(3) gets its own frame on top of main's. main waits underneath, its work unfinished, until this call returns.
3. fact(3) cannot finish until it knows fact(2), so it calls it: one more frame on top, with its own n = 2.
4. fact(1) is pushed on top. It is the base case, so it can return without calling anything: the top frame is the first to finish.
5. fact(1) returns 1 and its frame is popped. fact(2) is on top again, exactly where it left off, and can now finish: 2 × 1 = 2.
6. fact(2) returns 2 and its frame is popped. fact(3) is on top again, exactly where it left off, and can now finish: 3 × 2 = 6.
7. fact(3) returns 6 to main, the last frame popped before main itself. The newest call always finished first: last in, first out, which is why too deep a recursion overflows this stack.

The call stack has a fixed size, so recursion 100,000 levels deep can overflow it (Python stops at about 1,000). Any recursive algorithm can push and pop its own stack in heap memory instead — see Recursion and Depth-First Search.

Matching brackets: valid parentheses

Valid Parentheses is the stack's signature problem. Read the string left to right with a stack of openers still waiting for a partner:

• An opener is pushed.
• A closer must match the opener on top. An empty stack or a different opener means invalid; otherwise pop.
• At the end the stack must be empty; anything left was never closed.

1. A closing bracket must close the most recent opener that is still open: last in, first out, which is exactly a stack. Read the string left to right, push every opener, and on a closer check that the top of the stack is its partner.
2. '{' at index 0 is an opener, so it is pushed. It waits on the stack until its partner arrives with nothing still open above it.
3. '[' at index 1 is an opener, so it is pushed on top of '{'. Whatever is on top must be closed first, so '[' now has to be closed before '{' can be.
4. '(' at index 2 is an opener, so it is pushed on top of '['. Whatever is on top must be closed first, so '(' now has to be closed before '[' can be.
5. ')' at index 3 needs '(', and the top of the stack is '(', so they match and '(' is popped. '[' is on top again, the next opener waiting to be closed.
6. ']' at index 4 needs '[', and the top of the stack is '[', so they match and '[' is popped. '{' is on top again, the next opener waiting to be closed.
7. '}' at index 5 needs '{', and the top of the stack is '{', so they match and '{' is popped. The stack is empty, so "{[()]}" is balanced on its own.
8. '(' at index 6 is an opener, so it is pushed. It waits on the stack until its partner arrives with nothing still open above it.
9. '[' at index 7 is an opener, so it is pushed on top of '('. Whatever is on top must be closed first, so '[' now has to be closed before '(' can be.
10. ')' at index 8 needs '(', but the top is '[': the pairs cross, so the string is invalid and the scan stops. Counting brackets would miss this. One pass, each character pushed and popped at most once: O(n) time and O(n) space.

Why the top is the only candidate

If ) arrives while [ is on top, could it close a ( deeper down? No: the [ was opened inside that ( and must close first. So the invariant is: after each character, the stack holds exactly the unmatched openers, oldest at the bottom. Every push or pop keeps it, and the string is valid exactly when the stack ends empty with no closer rejected. Each character is pushed and popped at most once: O(n) time and space.

The code

The program checks five strings: two valid, one with crossing pairs, one with an opener never closed and one with a closer that has nothing to close.

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

// The opener a closing bracket must match, or 0 if c is not a closer.
char openerFor(char c) {
    if (c == ')') return '(';
    if (c == ']') return '[';
    if (c == '}') return '{';
    return 0;
}

bool isValid(const string& s) {
    stack<char> openers;  // openers still waiting for their partner
    for (char c : s) {
        char need = openerFor(c);
        if (need == 0) {
            openers.push(c);  // an opener: wait on the stack
        } else {
            if (openers.empty() || openers.top() != need) return false;  // nothing to close, or pairs cross
            openers.pop();    // matched the most recent opener
        }
    }
    return openers.empty();  // anything left was never closed
}

int main() {
    vector<string> tests = {"()[]{}", "{[()]}", "{[()]}([)]", "(()", "())"};
    for (const string& s : tests) {
        cout << s << " -> " << (isValid(s) ? "valid" : "invalid") << "\n";
    }
    return 0;
}

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

public class Main {
    // The opener a closing bracket must match, or 0 if c is not a closer.
    static char openerFor(char c) {
        if (c == ')') return '(';
        if (c == ']') return '[';
        if (c == '}') return '{';
        return 0;
    }

    static boolean isValid(String s) {
        Deque<Character> openers = new ArrayDeque<>();  // openers still waiting for their partner
        for (char c : s.toCharArray()) {
            char need = openerFor(c);
            if (need == 0) {
                openers.push(c);  // an opener: wait on the stack
            } else {
                if (openers.isEmpty() || openers.peek() != need) return false;  // nothing to close, or pairs cross
                openers.pop();    // matched the most recent opener
            }
        }
        return openers.isEmpty();  // anything left was never closed
    }

    public static void main(String[] args) {
        String[] tests = {"()[]{}", "{[()]}", "{[()]}([)]", "(()", "())"};
        for (String s : tests) {
            System.out.println(s + " -> " + (isValid(s) ? "valid" : "invalid"));
        }
    }
}

OPENER_FOR = {")": "(", "]": "[", "}": "{"}  # the opener each closer must match


def is_valid(s):
    openers = []  # openers still waiting for their partner
    for c in s:
        need = OPENER_FOR.get(c)
        if need is None:
            openers.append(c)  # an opener: wait on the stack
        else:
            if not openers or openers[-1] != need:
                return False   # nothing to close, or the pairs cross
            openers.pop()      # matched the most recent opener
    return not openers         # anything left was never closed


tests = ["()[]{}", "{[()]}", "{[()]}([)]", "(()", "())"]
for s in tests:
    print(f"{s} -> {'valid' if is_valid(s) else 'invalid'}")

const OPENER_FOR = { ")": "(", "]": "[", "}": "{" }; // the opener each closer must match

function isValid(s) {
  const openers = []; // openers still waiting for their partner
  for (const c of s) {
    const need = OPENER_FOR[c];
    if (need === undefined) {
      openers.push(c); // an opener: wait on the stack
    } else {
      if (openers.length === 0 || openers[openers.length - 1] !== need) return false; // nothing to close, or pairs cross
      openers.pop(); // matched the most recent opener
    }
  }
  return openers.length === 0; // anything left was never closed
}

const tests = ["()[]{}", "{[()]}", "{[()]}([)]", "(()", "())"];
for (const s of tests) {
  console.log(`${s} -> ${isValid(s) ? "valid" : "invalid"}`);
}

()[]{} -> valid
{[()]} -> valid
{[()]}([)] -> invalid
(() -> invalid
()) -> invalid

Evaluating postfix expressions

In postfix notation, or reverse Polish notation (RPN), the operator comes after its operands: 2 1 + 3 * is (2 + 1) × 3. It needs no brackets and no precedence, because the order of the tokens is the order of the work. A number is pushed; an operator pops two values and pushes the result; the one value left is the answer.

1. Postfix puts each operator after its operands, so the order of the tokens is the order of the work and no brackets are needed. Read left to right with a stack of values.
2. 4 is a number, so it is pushed. Numbers wait on the stack until an operator needs them.
3. 13 is a number: push it. The top of the stack is always the most recent value not yet used.
4. 5 is a number: push it. The top of the stack is always the most recent value not yet used.
5. '/' applies to the two most recent unused values, the top two. The first pop is the right operand b = 5, the second the left operand a = 13 — backwards for '-' and '/', which is the classic bug.
6. 13 / 5 = 2, truncated towards zero, is pushed back: the sub-expression "13 5 /" has collapsed into one value, and the rest of the expression treats it like any number.
7. '+' applies to the two most recent unused values, the top two. The first pop is the right operand b = 2, the second the left operand a = 4 — backwards for '-' and '/', which is the classic bug.
8. 4 + 2 = 6 is pushed, the tokens are used up, and the one value left is the answer, 6. Each token is pushed or popped a constant number of times: O(n).

The code

The third expression divides 6 by −132, which catches Python and JavaScript: Evaluate Reverse Polish Notation truncates towards zero, giving 0 and a final answer of 22, but Python's // floors to −1 and JavaScript's / gives a fraction. So Python uses int(a / b) and JavaScript Math.trunc; C++ and Java already truncate.

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

int evalRPN(const string& expr) {
    vector<int> stack;
    istringstream in(expr);
    string tok;
    while (in >> tok) {
        if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
            int b = stack.back(); stack.pop_back();  // the right operand is on top
            int a = stack.back(); stack.pop_back();
            if (tok == "+") stack.push_back(a + b);
            else if (tok == "-") stack.push_back(a - b);
            else if (tok == "*") stack.push_back(a * b);
            else stack.push_back(a / b);  // C++ integer division truncates towards zero
        } else {
            stack.push_back(stoi(tok));   // a number, possibly negative such as -11
        }
    }
    return stack.back();
}

int main() {
    vector<string> tests = {"2 1 + 3 *", "4 13 5 / +", "10 6 9 3 + -11 * / * 17 + 5 +"};
    for (const string& expr : tests) cout << expr << " = " << evalRPN(expr) << "\n";
    return 0;
}

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

public class Main {
    static int evalRPN(String expr) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String tok : expr.split(" ")) {
            if (tok.equals("+") || tok.equals("-") || tok.equals("*") || tok.equals("/")) {
                int b = stack.pop();  // the right operand is on top
                int a = stack.pop();
                if (tok.equals("+")) stack.push(a + b);
                else if (tok.equals("-")) stack.push(a - b);
                else if (tok.equals("*")) stack.push(a * b);
                else stack.push(a / b);  // Java integer division truncates towards zero
            } else {
                stack.push(Integer.parseInt(tok));  // a number, possibly negative such as -11
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tests = {"2 1 + 3 *", "4 13 5 / +", "10 6 9 3 + -11 * / * 17 + 5 +"};
        for (String expr : tests) System.out.println(expr + " = " + evalRPN(expr));
    }
}

def eval_rpn(expr):
    stack = []
    for tok in expr.split():
        if tok in ("+", "-", "*", "/"):
            b = stack.pop()  # the right operand is on top
            a = stack.pop()
            if tok == "+":
                stack.append(a + b)
            elif tok == "-":
                stack.append(a - b)
            elif tok == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))  # truncate towards zero; a // b would floor
        else:
            stack.append(int(tok))  # a number, possibly negative such as -11
    return stack.pop()


tests = ["2 1 + 3 *", "4 13 5 / +", "10 6 9 3 + -11 * / * 17 + 5 +"]
for expr in tests:
    print(f"{expr} = {eval_rpn(expr)}")

function evalRPN(expr) {
  const stack = [];
  for (const tok of expr.split(" ")) {
    if (tok === "+" || tok === "-" || tok === "*" || tok === "/") {
      const b = stack.pop(); // the right operand is on top
      const a = stack.pop();
      if (tok === "+") stack.push(a + b);
      else if (tok === "-") stack.push(a - b);
      else if (tok === "*") stack.push(a * b);
      else stack.push(Math.trunc(a / b)); // truncate towards zero, as the problem asks
    } else {
      stack.push(Number(tok)); // a number, possibly negative such as -11
    }
  }
  return stack.pop();
}

const tests = ["2 1 + 3 *", "4 13 5 / +", "10 6 9 3 + -11 * / * 17 + 5 +"];
for (const expr of tests) console.log(`${expr} = ${evalRPN(expr)}`);

2 1 + 3 * = 9
4 13 5 / + = 6
10 6 9 3 + -11 * / * 17 + 5 + = 22

Turning infix into postfix is itself a stack algorithm, Dijkstra's shunting-yard: practise it on Infix to Postfix. Basic Calculator II evaluates infix directly by pushing terms and folding × and / into the top.

A stack that knows its minimum

Build a stack with push, pop, top and getMin, all O(1). Scanning for the minimum is O(n), and one variable for "the minimum" fails as soon as the minimum is popped. Instead, let every entry remember the minimum of itself and everything below it.

1. push 5 on an empty stack: the minimum of one value is the value, so the entry is (5, 5).
2. push 3: smaller than the 5 recorded below, so this entry's minimum is 3. getMin just reads the top entry: O(1), no scan.
3. push 7: the minimum of 7 and the 3 recorded below is 3, so the entry is (7, 3).
4. push 3: the minimum of 3 and the 3 recorded below is 3, so the entry is (3, 3). A repeated minimum gets its own entry, so popping one copy cannot lose the other.
5. push 1: smaller than the 3 recorded below, so this entry's minimum is 1. getMin just reads the top entry: O(1), no scan.
6. pop removes (1, 1). Nothing is recomputed: the entry now on top recorded the minimum of everything still on the stack when it was pushed, and nothing below it has changed since. getMin is 3.
7. pop removes 3; getMin is 3, read from the new top.
8. pop removes 7; getMin is 3, read from the new top.
9. pop removes 3; getMin is 5, read from the new top. Every operation touched only the top entry: O(1) each, at the price of storing a second number per entry.

It works because a stack only changes at the top: while an entry is on the stack nothing below it can change, so the minimum it recorded stays true until it is popped. A space-saving variant keeps a second stack of minimums, pushing when a value is less than or equal to its top — the "or equal" keeps duplicates.

The code

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Each entry stores its value and the minimum of itself and everything below it.
class MinStack {
    vector<pair<int, int>> entries;  // (value, minimum so far)
public:
    void push(int x) {
        int m = entries.empty() ? x : min(x, entries.back().second);
        entries.push_back({x, m});
    }
    void pop() { entries.pop_back(); }
    int top() const { return entries.back().first; }
    int getMin() const { return entries.back().second; }  // O(1): already recorded
};

int main() {
    MinStack s;
    for (int x : {5, 3, 7, 3, 1}) {
        s.push(x);
        cout << "push " << x << " -> min " << s.getMin() << "\n";
    }
    for (int i = 0; i < 4; i++) {
        int x = s.top();
        s.pop();
        cout << "pop " << x << " -> min " << s.getMin() << "\n";
    }
    return 0;
}

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

public class Main {
    // Each entry stores its value and the minimum of itself and everything below it.
    static class MinStack {
        private final Deque<int[]> entries = new ArrayDeque<>();  // {value, minimum so far}

        void push(int x) {
            int m = entries.isEmpty() ? x : Math.min(x, entries.peek()[1]);
            entries.push(new int[] {x, m});
        }
        void pop() { entries.pop(); }
        int top() { return entries.peek()[0]; }
        int getMin() { return entries.peek()[1]; }  // O(1): already recorded
    }

    public static void main(String[] args) {
        MinStack s = new MinStack();
        for (int x : new int[] {5, 3, 7, 3, 1}) {
            s.push(x);
            System.out.println("push " + x + " -> min " + s.getMin());
        }
        for (int i = 0; i < 4; i++) {
            int x = s.top();
            s.pop();
            System.out.println("pop " + x + " -> min " + s.getMin());
        }
    }
}

class MinStack:
    """Each entry stores its value and the minimum of itself and everything below it."""

    def __init__(self):
        self.entries = []  # (value, minimum so far)

    def push(self, x):
        m = x if not self.entries else min(x, self.entries[-1][1])
        self.entries.append((x, m))

    def pop(self):
        self.entries.pop()

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

    def get_min(self):
        return self.entries[-1][1]  # O(1): already recorded


s = MinStack()
for x in [5, 3, 7, 3, 1]:
    s.push(x)
    print(f"push {x} -> min {s.get_min()}")
for _ in range(4):
    x = s.top()
    s.pop()
    print(f"pop {x} -> min {s.get_min()}")

// Each entry stores its value and the minimum of itself and everything below it.
class MinStack {
  constructor() {
    this.entries = []; // [value, minimum so far]
  }
  push(x) {
    const m = this.entries.length === 0 ? x : Math.min(x, this.entries[this.entries.length - 1][1]);
    this.entries.push([x, m]);
  }
  pop() {
    this.entries.pop();
  }
  top() {
    return this.entries[this.entries.length - 1][0];
  }
  getMin() {
    return this.entries[this.entries.length - 1][1]; // O(1): already recorded
  }
}

const s = new MinStack();
for (const x of [5, 3, 7, 3, 1]) {
  s.push(x);
  console.log(`push ${x} -> min ${s.getMin()}`);
}
for (let i = 0; i < 4; i++) {
  const x = s.top();
  s.pop();
  console.log(`pop ${x} -> min ${s.getMin()}`);
}

push 5 -> min 5
push 3 -> min 3
push 7 -> min 3
push 3 -> min 3
push 1 -> min 1
pop 1 -> min 3
pop 3 -> min 3
pop 7 -> min 3
pop 3 -> min 5

Undo, backspace and other stack shapes

• Undo and redo: undo pops the newest action; redo is a second stack. Browser back and forward work the same way.
• Backspace: typing pushes and backspace pops, as in Backspace String Compare.
• Cancelling neighbours: a letter equal to the top cancels it in Remove All Adjacent Duplicates In String; Asteroid Collision is the same with a fight.
• Paths and nested state: Simplify Path pops on .., and Decode String pushes its state at [.

When the question is "the next greater or previous smaller element", the stack is kept sorted and becomes the monotonic stack.

Time and space complexity

Behind every O(n) row: each element is pushed at most once and popped at most once, so there are at most 2n stack operations in all.

How to recognise a stack problem

• Nesting: brackets, tags, expressions such as 3[a2[c]], directories.
• The most recent item decides: the last unmatched opener, the previous score, the newest edit.
• Cancelling or collapsing neighbours: removals that bring older items back together.
• Expressions to evaluate or convert.
• Undo, back, or recursion you need to make iterative.

Common mistakes

• Popping or peeking an empty stack: a closer with nothing to close must return "invalid", not crash.
• Forgetting the final check: ((( never fails on the way through; the stack must end empty.
• Popping operands in the wrong order: the first pop is the right operand.
• Floor division in Python: -7 // 2 is −4, not −3.
• Using java.util.Stack: use ArrayDeque through Deque.
• Losing duplicates in a min stack: push on <=, not just <.

Practice in this order

1. Valid Parentheses: the walkthrough above.
2. Baseball Game: a stack as a record you add to and cancel from.
3. Remove All Adjacent Duplicates In String: cancel the top when the new item matches it.
4. Backspace String Compare: typing and backspace as push and pop.
5. Evaluate Reverse Polish Notation: the second program, with its division rule.
6. Simplify Path: a stack of directory names, popped on ...
7. Asteroid Collision: a new item may destroy several before it settles.
8. Decode String: push the state at [, rebuild it at ].

The stack problem list has every stack problem in the catalogue. Next in this stage is the stack's mirror image, the queue, and after it the monotonic stack.