Code Templates

Standardize your approach to stack-based problems with these production-grade templates. For a deep dive into the theory, check out the Stack Concept Guide.

The Main Template: Standard Stack

While most languages provide a built-in stack (like Python’s list or Java’s Stack), implementing one from scratch is a common interview requirement to demonstrate your understanding of memory and pointers.

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

    // Add element to the top
    push(element) {
        this.items.push(element);
    }

    // Remove and return the top element
    pop() {
        if (this.isEmpty()) return null;
        return this.items.pop();
    }

    // View the top element
    peek() {
        if (this.isEmpty()) return null;
        return this.items[this.items.length - 1];
    }

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

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

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

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

    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)

import java.util.ArrayList;

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

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

    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();
    }

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

#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<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();
    }

    size_t size() const {
        return items.size();
    }
};

type Stack []interface{}

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

func (s *Stack) Pop() interface{} {
    if s.IsEmpty() {
        return nil
    }
    res := (*s)[len(*s)-1]
    *s = (*s)[:len(*s)-1]
    return res
}

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

  def pop
    @items.pop
  end

  def peek
    @items.last
  end

  def empty?
    @items.empty?
  end

  def size
    @items.length
  end
end

Logic Breakdown

The fundamental lifecycle of a stack operation can be visualized as a LIFO state machine:

  graph LR
    A[Start] --> B{Operation?}
    B -->|Push| C[Add to Top]
    B -->|Pop| D{Is Empty?}
    D -->|Yes| E[Error/Null]
    D -->|No| F[Remove Top]
    C --> G[New State]
    F --> G

Key Components

Pointer/Index: In array-based stacks, the “top” is implicitly the last index. In linked lists, it is the head node.
Underflow Protection: Always check isEmpty() before a pop or peek to prevent runtime crashes.
Expansion: Most modern languages handle dynamic array resizing automatically (amortized
O(1)
), so we rarely need to worry about “Stack Overflow” in manual implementations unless memory is strictly capped.

Variation 1: Monotonic Stack (Next Greater Element)

The Monotonic Stack is the most frequent application of stacks in advanced interviews. It maintains elements in a specific order (increasing or decreasing) to solve range-based problems in linear time.

function nextGreaterElement(nums) {
    const stack = [];
    const res = new Array(nums.length).fill(-1);

    for (let i = 0; i < nums.length; i++) {
        // While current is greater than the element at the index on top of stack
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            const index = stack.pop();
            res[index] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

def next_greater_element(nums):
    stack = []
    res = [-1] * len(nums)

    for i in range(len(nums)):
        # Maintain a decreasing stack
        while stack and nums[i] > nums[stack[-1]]:
            index = stack.pop()
            res[index] = nums[i]
        stack.append(i)

    return res

import java.util.Stack;
import java.util.Arrays;

public int[] nextGreaterElement(int[] nums) {
    int[] res = new int[nums.length];
    Arrays.fill(res, -1);
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

#include <vector>
#include <stack>

std::vector<int> nextGreaterElement(std::vector<int>& nums) {
    std::vector<int> res(nums.size(), -1);
    std::stack<int> s;

    for (int i = 0; i < nums.size(); ++i) {
        while (!s.empty() && nums[i] > nums[s.top()]) {
            res[s.top()] = nums[i];
            s.pop();
        }
        s.push(i);
    }
    return res;
}

func nextGreaterElement(nums []int) []int {
    res := make([]int, len(nums))
    for i := range res {
        res[i] = -1
    }
    stack := []int{} // stores indices

    for i, num := range nums {
        for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = num
        }
        stack = append(stack, i)
    }
    return res
}

def next_greater_element(nums)
  res = Array.new(nums.length, -1)
  stack = [] # stores indices

  nums.each_with_index do |num, i|
    while !stack.empty? && num > nums[stack.last]
      idx = stack.pop
      res[idx] = num
    end
    stack.push(i)
  end
  res
end

Variation 2: Min Stack (O(1) Min Access)

This template allows you to retrieve the minimum element in the stack in constant time by using an auxiliary stack.

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

    push(val) {
        this.stack.push(val);
        // Push to minStack if empty or val is new minimum
        if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }

    pop() {
        const val = this.stack.pop();
        if (val === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
        return val;
    }

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

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

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

    def pop(self):
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

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

import java.util.Stack;

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 getMin() {
        return minStack.peek();
    }
}

#include <stack>

class MinStack {
private:
    std::stack<int> s;
    std::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 getMin() {
        return min_s.top();
    }
};

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

func Constructor() MinStack {
    return MinStack{}
}

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

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

func (s *MinStack) GetMin() int {
    return s.minStack[len(s.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 get_min
    @min_stack.last
  end
end

Practice

Now that you have the blueprints, apply them to real-world scenarios in the Practice Problems section.