Stack: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Stack Data Structure: Complete Guide with LIFO Examples

If you have not read the concept guide yet, start there for the LIFO intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. The main template is the stack container itself, and the variations cover the three shapes most interview problems take: bracket matching, expression evaluation, and tracking a running minimum. The monotonic stack, which answers next greater queries, has its own page because the ordering rules deserve the extra room.

Main Template: Stack Container

This is the base layer of every stack solution. Most languages ship a built-in stack and interviews accept it, but implementing the container once makes the interface and the empty checks automatic. The empty check matters more than push and pop, because reading from an empty stack is the most common stack bug.

Use this for Min Stack , which layers a second stack on top of this one.

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

    // The top is always the last index of the backing array,
    // so push is just an append at the end.
    push(item) {
        this.items.push(item);
    }

    // Guard the pop before touching the array. Reading from
    // an empty stack is the most common stack bug.
    pop() {
        if (this.isEmpty()) return null;
        return this.items.pop();
    }

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

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

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

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

    # Return None on an empty stack instead of raising,
    # so callers can treat an empty pop as a no-op.
    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

import java.util.ArrayList;

public class Stack<T> {
    private ArrayList<T> items = new ArrayList<>();

    public void push(T item) {
        items.add(item);
    }

    // Null signals "empty", which keeps the caller from
    // crashing on a pop that has nothing to remove.
    public T pop() {
        if (isEmpty()) return null;
        return items.remove(items.size() - 1);
    }

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

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

#include <vector>
#include <optional>

template <typename T>
class Stack {
private:
    std::vector<T> items;

public:
    void push(const T& item) {
        items.push_back(item);
    }

    // std::optional makes the empty case explicit. Popping
    // an empty std::vector would be undefined behavior.
    std::optional<T> pop() {
        if (isEmpty()) return std::nullopt;
        T top = items.back();
        items.pop_back();
        return top;
    }

    std::optional<T> peek() const {
        if (isEmpty()) return std::nullopt;
        return items.back();
    }

    bool isEmpty() const {
        return items.empty();
    }
};

type Stack []interface{}

func (s *Stack) Push(v interface{}) {
    *s = append(*s, v)
}

// A nil return means the stack was empty, so the caller
// can distinguish "no value" from an actual nil element.
func (s *Stack) Pop() interface{} {
    if s.IsEmpty() {
        return nil
    }
    top := (*s)[len(*s)-1]
    *s = (*s)[:len(*s)-1]
    return top
}

func (s *Stack) Peek() interface{} {
    if s.IsEmpty() {
        return nil
    }
    return (*s)[len(*s)-1]
}

func (s *Stack) IsEmpty() bool {
    return len(*s) == 0
}

class Stack
    def initialize
        @items = []
    end

    def push(item)
        @items.push(item)
    end

    # Ruby's Array#pop returns nil on an empty array,
    # which is a safe no-op for the empty case.
    def pop
        @items.pop
    end

    def peek
        @items.last
    end

    def empty?
        @items.empty?
    end
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

items (backing array): the stack itself. The top element is always the last index, which is what makes push and pop
O(1)
.
isEmpty() (the guard): the check that must run before every pop and peek. It is the one line that separates correct stack code from a crash on the first edge case.

Visual Mechanism

    graph LR
    A[Start] --> B{Operation?}
    B -->|Push| C[Append to the end]
    B -->|Pop or Peek| D{Is the stack empty?}
    D -->|Yes| E[Return null or raise]
    D -->|No| F[Touch the last element]
    C --> G[New state]
    F --> G

Critical Sections

The initialization is just an empty array. No sentinel is needed because the empty check covers the base case.

The pop guard is the critical section. Check emptiness before removing, not after. When a problem uses the language’s built-in stack directly, the same guard applies: peek or pop only after confirming the stack is not empty.

The peek and pop distinction matters inside algorithms. Peek leaves the stack unchanged, so the next iteration still sees the same top. Pop changes the state. Code that pops when it only needed to look will silently skip an element on the next pass. When a solution behaves oddly and an element disappears, check whether peek was the right call.

Variations

1. Bracket Matching

Every opener must be closed by its matching closer in reverse order, so push openers and validate against the top when a closer arrives. Runs in

O(N)

time and

O(N)

space.

Use this for Valid Parentheses .

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

    for (const c of s) {
        if (matches[c]) {
            // A closer must match the most recent unclosed
            // opener, which is the stack top.
            if (stack.pop() !== matches[c]) return false;
        } else {
            stack.push(c);
        }
    }

    // Openers left on the stack were never closed.
    return stack.length === 0;
}

def is_valid(s: str) -> bool:
    stack = []
    matches = {")": "(", "}": "{", "]": "["}

    for c in s:
        if c in matches:
            # The top of the stack is the most recent
            # unclosed opener. It must pair with c.
            if not stack or stack.pop() != matches[c]:
                return False
        else:
            stack.append(c)

    return not stack

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            // A closer with nothing on the stack is invalid,
            // and so is a closer that mismatches the top.
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if (c == ')' && open != '(') return false;
            if (c == '}' && open != '{') return false;
            if (c == ']' && open != '[') return false;
        }
    }

    return stack.isEmpty();
}

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 open = st.top();
            st.pop();
            if (c == ')' && open != '(') return false;
            if (c == '}' && open != '{') return false;
            if (c == ']' && open != '[') return false;
        }
    }

    return st.empty();
}

func isValid(s string) bool {
    stack := []rune{}
    matches := map[rune]rune{')': '(', '}': '{', ']': '['}

    for _, c := range s {
        if open, ok := matches[c]; ok {
            // Pop the most recent unclosed opener and
            // compare it with the closer at hand.
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, c)
        }
    }

    return len(stack) == 0
}

2. Expression Evaluation (Reverse Polish Notation)

An operator applies to the most recent operands, so push numbers and pop the top two when an operator arrives. Runs in

O(N)

time and

O(N)

space.

Use this for Evaluate Reverse Polish Notation .

function evalRPN(tokens) {
    const stack = [];
    const ops = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        // Integer division must truncate toward zero,
        // so Math.trunc beats Math.floor here.
        '/': (a, b) => Math.trunc(a / b)
    };

    for (const token of tokens) {
        if (ops[token]) {
            // The first pop is the right operand because
            // it sits above the left one on the stack.
            const b = stack.pop();
            const a = stack.pop();
            stack.push(ops[token](a, b));
        } else {
            stack.push(Number(token));
        }
    }

    return stack[0];
}

def eval_rpn(tokens: List[str]) -> int:
    stack = []

    for t in tokens:
        if t not in "+-*/":
            stack.append(int(t))
        else:
            # r is the top of the stack, so it is the right
            # operand. l was pushed earlier, so it is left.
            r, l = stack.pop(), stack.pop()
            if t == "+":
                stack.append(l + r)
            elif t == "-":
                stack.append(l - r)
            elif t == "*":
                stack.append(l * r)
            else:
                # int() truncates toward zero, which matches
                # the problem's division requirement.
                stack.append(int(l / r))

    return stack.pop()

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();

    for (String t : tokens) {
        if ("+-*/".contains(t)) {
            // First pop is the right operand, second is left.
            int r = stack.pop();
            int l = stack.pop();
            if (t.equals("+")) stack.push(l + r);
            else if (t.equals("-")) stack.push(l - r);
            else if (t.equals("*")) stack.push(l * r);
            // Java integer division truncates toward zero.
            else stack.push(l / r);
        } else {
            stack.push(Integer.parseInt(t));
        }
    }

    return stack.pop();
}

int evalRPN(vector<string>& tokens) {
    stack<int> st;

    for (string& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            // First pop is the right operand, second is left,
            // because the left operand was pushed earlier.
            int r = st.top(); st.pop();
            int l = st.top(); st.pop();
            if (t == "+") st.push(l + r);
            else if (t == "-") st.push(l - r);
            else if (t == "*") st.push(l * r);
            // C++ integer division truncates toward zero.
            else st.push(l / r);
        } else {
            st.push(stoi(t));
        }
    }

    return st.top();
}

import "strconv"

func evalRPN(tokens []string) int {
    stack := []int{}

    for _, t := range tokens {
        if val, err := strconv.Atoi(t); err == nil {
            stack = append(stack, val)
        } else {
            // The last element is the right operand because
            // it was pushed most recently.
            r := stack[len(stack)-1]
            l := stack[len(stack)-2]
            stack = stack[:len(stack)-2]

            var res int
            switch t {
            case "+":
                res = l + r
            case "-":
                res = l - r
            case "*":
                res = l * r
            case "/":
                res = l / r // Go truncates toward zero
            }
            stack = append(stack, res)
        }
    }

    return stack[0]
}

def eval_rpn(tokens)
    stack = []

    tokens.each do |t|
        case t
        when "+", "-", "*", "/"
            # First pop is the right operand, second is left.
            r = stack.pop
            l = stack.pop
            case t
            when "+" then stack.push(l + r)
            when "-" then stack.push(l - r)
            when "*" then stack.push(l * r)
            # fdiv then to_i truncates toward zero, where
            # Ruby's integer division would floor instead.
            when "/" then stack.push(l.fdiv(r).to_i)
            end
        else
            stack.push(t.to_i)
        end
    end

    stack.pop
end

3. Min Stack (Auxiliary Stack)

When the problem asks for a running property like the minimum alongside normal push and pop, keep a second stack that records only the values that change that property. Each operation stays

O(1)

Use this for Min Stack .

class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    push(val) {
        this.stack.push(val);
        // minStack only records new minimums, so its top is
        // always the minimum of the whole stack.
        if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }

    pop() {
        const val = this.stack.pop();
        // If the popped value was the current minimum, the
        // next entry down in minStack is the new minimum.
        if (val === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
    }

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

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

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        # Only release the minimum when the value being
        # removed actually was the minimum.
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

class MinStack {
private:
    stack<int> s;
    stack<int> min_s;

public:
    void push(int val) {
        s.push(val);
        if (min_s.empty() || val <= min_s.top()) {
            min_s.push(val);
        }
    }

    void pop() {
        if (s.top() == min_s.top()) {
            min_s.pop();
        }
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return min_s.top();
    }
};

type MinStack struct {
    stack    []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{}
}

func (this *MinStack) Push(val int) {
    this.stack = append(this.stack, val)
    if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {
        this.minStack = append(this.minStack, val)
    }
}

func (this *MinStack) Pop() {
    val := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    if val == this.minStack[len(this.minStack)-1] {
        this.minStack = this.minStack[:len(this.minStack)-1]
    }
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

class MinStack
    def initialize
        @stack = []
        @min_stack = []
    end

    def push(val)
        @stack.push(val)
        if @min_stack.empty? || val <= @min_stack.last
            @min_stack.push(val)
        end
    end

    def pop
        val = @stack.pop
        @min_stack.pop if val == @min_stack.last
    end

    def top
        @stack.last
    end

    def get_min
        @min_stack.last
    end
end

The monotonic stack variant, which answers next greater and next smaller queries, has full templates on the Monotonic Stack template page . The problems on the practice problems page that use it, Daily Temperatures, Largest Rectangle in Histogram, and Trapping Rain Water, are solved with that template.

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .