Complete DSA Series Part 7: Stack

FAANG Interview Prep

Your 12-step learning path • Currently on Step 7

Stack

LIFO, push/pop, expression evaluation, backtracking

You Are Here

Queue

FIFO, circular queue, deque, priority queue

Trees

Binary trees, traversals, expression trees, threaded trees

BST & Balanced Trees

Search, insert, delete, AVL, red-black, B-trees

Heaps, Sorting & Hashing

Min/max heaps, heapsort, hash tables, collision handling

Graphs, DP, Greedy & Backtracking

BFS, DFS, shortest paths, dynamic programming, optimization

Introduction to Stack

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. Stacks are fundamental in computer science, used in function calls, expression parsing, undo mechanisms, and many algorithms.

Stack data structure showing LIFO principle with push adding to top and pop removing from top — Stack LIFO Principle — elements are pushed onto and popped from the top, like a stack of plates

                            
                            Key Insight: The LIFO property makes stacks perfect for scenarios where you need to "backtrack" or process elements in reverse order of arrival. Function call stacks, browser history, and undo/redo are classic examples.
                        

Stack Operations

                            Core Stack Operations
                            
                                        Operation
                                        Description
                                        Time
                                    
                                        push(item)
                                        Add item to top
                                        \(O(1)\)
                                    
                                        pop()
                                        Remove and return top item
                                        \(O(1)\)
                                    
                                        peek()/top()
                                        Return top item without removing
                                        \(O(1)\)
                                    
                                        isEmpty()
                                        Check if stack is empty
                                        \(O(1)\)
                                    
                                        size()
                                        Return number of items
                                        \(O(1)\)

Operation	Description	Time
push(item)	Add item to top	\(O(1)\)
pop()	Remove and return top item	\(O(1)\)
peek()/top()	Return top item without removing	\(O(1)\)
isEmpty()	Check if stack is empty	\(O(1)\)
size()	Return number of items	\(O(1)\)

Stack Implementations

Array-Based Stack

The simplest stack implementation uses an array (or dynamic list in Python). A top variable tracks the index of the topmost element. Push increments top and places the element; pop returns the element at top and decrements. All operations are \(O(1)\) amortized. The array approach offers excellent cache locality (contiguous memory) but has a fixed capacity in static arrays. Python lists and Java's ArrayList handle resizing automatically via amortized doubling.

# Stack Implementation using Array (Python List)
# All operations O(1) amortized

class ArrayStack:
    def __init__(self, capacity=None):
        """Initialize stack with optional fixed capacity"""
        self.capacity = capacity
        self.items = []
    
    def push(self, item):
        """Add item to top - O(1) amortized"""
        if self.capacity and len(self.items) >= self.capacity:
            raise OverflowError("Stack is full")
        self.items.append(item)
    
    def pop(self):
        """Remove and return top item - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()
    
    def peek(self):
        """Return top item without removing - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[-1]
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# Test
stack = ArrayStack()
stack.push(1)
stack.push(2)
stack.push(3)
print(f"Peek: {stack.peek()}")  # 3
print(f"Pop: {stack.pop()}")    # 3
print(f"Size: {stack.size()}")  # 2

// Stack Implementation using Array (Vector)

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;

template <typename T>
class ArrayStack {
private:
    vector<T> items;
    int maxCapacity;
    
public:
    ArrayStack(int capacity = -1) : maxCapacity(capacity) {}
    
    void push(T item) {
        if (maxCapacity > 0 && items.size() >= maxCapacity)
            throw overflow_error("Stack is full");
        items.push_back(item);
    }
    
    T pop() {
        if (isEmpty()) throw runtime_error("Stack is empty");
        T item = items.back();
        items.pop_back();
        return item;
    }
    
    T peek() {
        if (isEmpty()) throw runtime_error("Stack is empty");
        return items.back();
    }
    
    bool isEmpty() { return items.empty(); }
    int size() { return items.size(); }
};

int main() {
    ArrayStack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    cout << "Peek: " << stack.peek() << endl;  // 3
    cout << "Pop: " << stack.pop() << endl;    // 3
    cout << "Size: " << stack.size() << endl;  // 2
    return 0;
}

// Stack Implementation using ArrayList

import java.util.ArrayList;

public class ArrayStack<T> {
    private ArrayList<T> items;
    private int maxCapacity;
    
    public ArrayStack() { this(-1); }
    
    public ArrayStack(int capacity) {
        this.items = new ArrayList<>();
        this.maxCapacity = capacity;
    }
    
    public void push(T item) {
        if (maxCapacity > 0 && items.size() >= maxCapacity)
            throw new RuntimeException("Stack is full");
        items.add(item);
    }
    
    public T pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return items.remove(items.size() - 1);
    }
    
    public T peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return items.get(items.size() - 1);
    }
    
    public boolean isEmpty() { return items.isEmpty(); }
    public int size() { return items.size(); }
    
    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Peek: " + stack.peek());  // 3
        System.out.println("Pop: " + stack.pop());    // 3
        System.out.println("Size: " + stack.size());  // 2
    }
}

Fixed-Size Array Stack (Lower Level)

# Fixed-Size Array Stack Implementation

class FixedArrayStack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.array = [None] * capacity
        self.top = -1  # Index of top element
    
    def push(self, item):
        if self.is_full():
            raise OverflowError("Stack overflow")
        self.top += 1
        self.array[self.top] = item
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow")
        item = self.array[self.top]
        self.array[self.top] = None
        self.top -= 1
        return item
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.array[self.top]
    
    def is_empty(self):
        return self.top == -1
    
    def is_full(self):
        return self.top == self.capacity - 1
    
    def size(self):
        return self.top + 1

# Test
fixed_stack = FixedArrayStack(5)
for i in range(1, 6):
    fixed_stack.push(i * 10)
print(f"Is full: {fixed_stack.is_full()}")  # True
print(f"Pop: {fixed_stack.pop()}")  # 50

// Fixed-Size Array Stack Implementation

#include <iostream>
#include <stdexcept>
using namespace std;

template <typename T>
class FixedArrayStack {
private:
    T* array;
    int capacity;
    int topIndex;
    
public:
    FixedArrayStack(int cap) : capacity(cap), topIndex(-1) {
        array = new T[capacity];
    }
    
    ~FixedArrayStack() { delete[] array; }
    
    void push(T item) {
        if (isFull()) throw overflow_error("Stack overflow");
        array[++topIndex] = item;
    }
    
    T pop() {
        if (isEmpty()) throw runtime_error("Stack underflow");
        return array[topIndex--];
    }
    
    T peek() {
        if (isEmpty()) throw runtime_error("Stack is empty");
        return array[topIndex];
    }
    
    bool isEmpty() { return topIndex == -1; }
    bool isFull() { return topIndex == capacity - 1; }
    int size() { return topIndex + 1; }
};

int main() {
    FixedArrayStack<int> stack(5);
    for (int i = 1; i <= 5; i++) stack.push(i * 10);
    cout << "Is full: " << (stack.isFull() ? "true" : "false") << endl;  // true
    cout << "Pop: " << stack.pop() << endl;  // 50
    return 0;
}

// Fixed-Size Array Stack Implementation

public class FixedArrayStack<T> {
    private Object[] array;
    private int capacity;
    private int topIndex;
    
    public FixedArrayStack(int capacity) {
        this.capacity = capacity;
        this.array = new Object[capacity];
        this.topIndex = -1;
    }
    
    public void push(T item) {
        if (isFull()) throw new RuntimeException("Stack overflow");
        array[++topIndex] = item;
    }
    
    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        T item = (T) array[topIndex];
        array[topIndex--] = null;
        return item;
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return (T) array[topIndex];
    }
    
    public boolean isEmpty() { return topIndex == -1; }
    public boolean isFull() { return topIndex == capacity - 1; }
    public int size() { return topIndex + 1; }
    
    public static void main(String[] args) {
        FixedArrayStack<Integer> stack = new FixedArrayStack<>(5);
        for (int i = 1; i <= 5; i++) stack.push(i * 10);
        System.out.println("Is full: " + stack.isFull());  // true
        System.out.println("Pop: " + stack.pop());  // 50
    }
}

Linked List-Based Stack

A linked-list stack pushes and pops at the head — making every operation truly \(O(1)\) with no amortized cost and no capacity limit. Each push allocates a new node; each pop frees the head. The tradeoff: each element requires extra memory for the pointer (8 bytes on 64-bit systems), and nodes are scattered in memory (poor cache performance). Use this when you need guaranteed \(O(1)\) worst-case (no resize pauses) or when implementing stacks in languages without dynamic arrays.

# Stack Implementation using Linked List
# True O(1) for all operations

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

class LinkedListStack:
    def __init__(self):
        self.head = None
        self._size = 0
    
    def push(self, item):
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node
        self._size += 1
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.head.data
        self.head = self.head.next
        self._size -= 1
        return item
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.head.data
    
    def is_empty(self):
        return self.head is None
    
    def size(self):
        return self._size

# Test
ll_stack = LinkedListStack()
ll_stack.push(1)
ll_stack.push(2)
ll_stack.push(3)
print(f"Peek: {ll_stack.peek()}")  # 3
print(f"Pop: {ll_stack.pop()}")    # 3
print(f"Size: {ll_stack.size()}")  # 2

// Stack Implementation using Linked List

#include <iostream>
#include <stdexcept>
using namespace std;

template <typename T>
class LinkedListStack {
private:
    struct Node {
        T data;
        Node* next;
        Node(T d) : data(d), next(nullptr) {}
    };
    
    Node* head;
    int _size;
    
public:
    LinkedListStack() : head(nullptr), _size(0) {}
    
    ~LinkedListStack() {
        while (!isEmpty()) pop();
    }
    
    void push(T item) {
        Node* newNode = new Node(item);
        newNode->next = head;
        head = newNode;
        _size++;
    }
    
    T pop() {
        if (isEmpty()) throw runtime_error("Stack is empty");
        T item = head->data;
        Node* temp = head;
        head = head->next;
        delete temp;
        _size--;
        return item;
    }
    
    T peek() {
        if (isEmpty()) throw runtime_error("Stack is empty");
        return head->data;
    }
    
    bool isEmpty() { return head == nullptr; }
    int size() { return _size; }
};

int main() {
    LinkedListStack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    cout << "Peek: " << stack.peek() << endl;  // 3
    cout << "Pop: " << stack.pop() << endl;    // 3
    cout << "Size: " << stack.size() << endl;  // 2
    return 0;
}

// Stack Implementation using Linked List

public class LinkedListStack<T> {
    private class Node {
        T data;
        Node next;
        Node(T data) { this.data = data; }
    }
    
    private Node head;
    private int size;
    
    public LinkedListStack() {
        head = null;
        size = 0;
    }
    
    public void push(T item) {
        Node newNode = new Node(item);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    public T pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        T item = head.data;
        head = head.next;
        size--;
        return item;
    }
    
    public T peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return head.data;
    }
    
    public boolean isEmpty() { return head == null; }
    public int size() { return size; }
    
    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Peek: " + stack.peek());  // 3
        System.out.println("Pop: " + stack.pop());    // 3
        System.out.println("Size: " + stack.size());  // 2
    }
}

Array vs Linked List Stack

Aspect	Array Stack	Linked List Stack
Push	\(O(1)\) amortized*	\(O(1)\)
Pop	\(O(1)\)	\(O(1)\)
Memory	Contiguous, less overhead	Scattered, pointer overhead
Cache	Better locality	Poor locality
Size	Fixed or resize needed	Dynamic

* \(O(n)\) worst case when resizing, but amortized \(O(1)\)

Stack Applications

Parentheses Matching

The balanced parentheses problem is the canonical stack application. The insight: every closing bracket must match the most-recently-opened bracket — exactly LIFO order. Push opening brackets; on a closing bracket, pop and verify it matches. If the stack is empty when you need to pop (extra closer) or non-empty after processing (unclosed opener), the expression is unbalanced. This pattern extends to HTML tag matching, code block nesting, and compiler syntax validation.

# Balanced Parentheses Check
# Time: O(n), Space: O(n)

def is_balanced(expression):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}
    
    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
    
    return len(stack) == 0

# Test
print(is_balanced("((a+b)*(c-d))"))   # True
print(is_balanced("[(a+b)*{c-d}]"))   # True
print(is_balanced("((a+b)"))          # False
print(is_balanced("([)]"))            # False

// Balanced Parentheses Check

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

bool isBalanced(string expression) {
    stack<char> stk;
    unordered_map<char, char> matching = {
        {')', '('}, {']', '['}, {'}', '{'}
    };
    
    for (char ch : expression) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stk.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (stk.empty() || stk.top() != matching[ch])
                return false;
            stk.pop();
        }
    }
    return stk.empty();
}

int main() {
    cout << boolalpha;
    cout << isBalanced("((a+b)*(c-d))") << endl;  // true
    cout << isBalanced("[(a+b)*{c-d}]") << endl;  // true
    cout << isBalanced("((a+b)") << endl;         // false
    cout << isBalanced("([)]") << endl;           // false
    return 0;
}

// Balanced Parentheses Check

import java.util.*;

public class ParenthesesMatching {
    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> matching = Map.of(
            ')', '(', ']', '[', '}', '{'
        );
        
        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty() || stack.peek() != matching.get(ch))
                    return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        System.out.println(isBalanced("((a+b)*(c-d))"));  // true
        System.out.println(isBalanced("[(a+b)*{c-d}]"));  // true
        System.out.println(isBalanced("((a+b)"));         // false
        System.out.println(isBalanced("([)]"));           // false
    }
}

Expression Evaluation

# Postfix (Reverse Polish Notation) Expression Evaluation
# Example: "3 4 + 5 *" means (3 + 4) * 5 = 35

def evaluate_postfix(expression):
    stack = []
    operators = {'+', '-', '*', '/', '^'}
    tokens = expression.split()
    
    for token in tokens:
        if token not in operators:
            stack.append(float(token))
        else:
            b = stack.pop()  # Second operand
            a = stack.pop()  # First operand
            
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/': stack.append(a / b)
            elif token == '^': stack.append(a ** b)
    
    return stack[0]

# Test
print(evaluate_postfix("3 4 +"))          # 7
print(evaluate_postfix("3 4 + 5 *"))      # 35
print(evaluate_postfix("2 3 ^ 4 +"))      # 12

// Postfix Expression Evaluation

#include <iostream>
#include <stack>
#include <sstream>
#include <cmath>
using namespace std;

double evaluatePostfix(string expression) {
    stack<double> stk;
    istringstream iss(expression);
    string token;
    
    while (iss >> token) {
        if (token == "+" || token == "-" || token == "*" || 
            token == "/" || token == "^") {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            
            if (token == "+") stk.push(a + b);
            else if (token == "-") stk.push(a - b);
            else if (token == "*") stk.push(a * b);
            else if (token == "/") stk.push(a / b);
            else if (token == "^") stk.push(pow(a, b));
        } else {
            stk.push(stod(token));
        }
    }
    return stk.top();
}

int main() {
    cout << evaluatePostfix("3 4 +") << endl;       // 7
    cout << evaluatePostfix("3 4 + 5 *") << endl;   // 35
    cout << evaluatePostfix("2 3 ^ 4 +") << endl;   // 12
    return 0;
}

// Postfix Expression Evaluation

import java.util.*;

public class PostfixEvaluator {
    public static double evaluatePostfix(String expression) {
        Stack<Double> stack = new Stack<>();
        String[] tokens = expression.split(" ");
        Set<String> operators = Set.of("+", "-", "*", "/", "^");
        
        for (String token : tokens) {
            if (operators.contains(token)) {
                double b = stack.pop();
                double 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;
                    case "^": stack.push(Math.pow(a, b)); break;
                }
            } else {
                stack.push(Double.parseDouble(token));
            }
        }
        return stack.pop();
    }
    
    public static void main(String[] args) {
        System.out.println(evaluatePostfix("3 4 +"));       // 7
        System.out.println(evaluatePostfix("3 4 + 5 *"));   // 35
        System.out.println(evaluatePostfix("2 3 ^ 4 +"));   // 12
    }
}

Python - Prefix Evaluation

# Prefix Expression Evaluation
# Process right to left

def evaluate_prefix(expression):
    stack = []
    operators = {'+', '-', '*', '/', '^'}
    tokens = expression.split()[::-1]  # Reverse
    
    for token in tokens:
        if token not in operators:
            stack.append(float(token))
        else:
            a = stack.pop()  # First operand
            b = stack.pop()  # Second operand
            
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/': stack.append(a / b)
            elif token == '^': stack.append(a ** b)
    
    return stack[0]

# Test
print(evaluate_prefix("+ 3 4"))       # 7
print(evaluate_prefix("* + 3 4 5"))   # 35

Infix to Postfix Conversion

# Infix to Postfix Conversion (Shunting Yard Algorithm)

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    right_associative = {'^'}
    output = []
    operator_stack = []
    tokens = expression.replace('(', ' ( ').replace(')', ' ) ').split()
    
    for token in tokens:
        if token.replace('.', '').lstrip('-').isdigit():
            output.append(token)
        elif token == '(':
            operator_stack.append(token)
        elif token == ')':
            while operator_stack and operator_stack[-1] != '(':
                output.append(operator_stack.pop())
            if operator_stack:
                operator_stack.pop()
        elif token in precedence:
            while (operator_stack and operator_stack[-1] != '(' and
                   operator_stack[-1] in precedence and
                   (precedence[operator_stack[-1]] > precedence[token] or
                    (precedence[operator_stack[-1]] == precedence[token] and
                     token not in right_associative))):
                output.append(operator_stack.pop())
            operator_stack.append(token)
    
    while operator_stack:
        output.append(operator_stack.pop())
    
    return ' '.join(output)

# Test
print(infix_to_postfix("3 + 4"))         # 3 4 +
print(infix_to_postfix("3 + 4 * 5"))     # 3 4 5 * +
print(infix_to_postfix("(3 + 4) * 5"))   # 3 4 + 5 *

// Infix to Postfix Conversion (Shunting Yard)

#include <iostream>
#include <stack>
#include <sstream>
#include <unordered_map>
#include <set>
using namespace std;

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '^') return 3;
    return 0;
}

string infixToPostfix(string expression) {
    stack<char> opStack;
    string output;
    set<char> rightAssoc = {'^'};
    
    for (char ch : expression) {
        if (isdigit(ch)) {
            output += ch;
            output += ' ';
        } else if (ch == '(') {
            opStack.push(ch);
        } else if (ch == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                output += opStack.top();
                output += ' ';
                opStack.pop();
            }
            if (!opStack.empty()) opStack.pop();
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^') {
            while (!opStack.empty() && opStack.top() != '(' &&
                   (precedence(opStack.top()) > precedence(ch) ||
                    (precedence(opStack.top()) == precedence(ch) &&
                     rightAssoc.find(ch) == rightAssoc.end()))) {
                output += opStack.top();
                output += ' ';
                opStack.pop();
            }
            opStack.push(ch);
        }
    }
    
    while (!opStack.empty()) {
        output += opStack.top();
        output += ' ';
        opStack.pop();
    }
    return output;
}

int main() {
    cout << infixToPostfix("3+4") << endl;       // 3 4 +
    cout << infixToPostfix("3+4*5") << endl;     // 3 4 5 * +
    cout << infixToPostfix("(3+4)*5") << endl;   // 3 4 + 5 *
    return 0;
}

// Infix to Postfix Conversion (Shunting Yard)

import java.util.*;

public class InfixToPostfix {
    private static int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        if (op == '^') return 3;
        return 0;
    }
    
    public static String convert(String expression) {
        Stack<Character> opStack = new Stack<>();
        StringBuilder output = new StringBuilder();
        Set<Character> rightAssoc = Set.of('^');
        
        for (char ch : expression.toCharArray()) {
            if (Character.isDigit(ch)) {
                output.append(ch).append(' ');
            } else if (ch == '(') {
                opStack.push(ch);
            } else if (ch == ')') {
                while (!opStack.isEmpty() && opStack.peek() != '(') {
                    output.append(opStack.pop()).append(' ');
                }
                if (!opStack.isEmpty()) opStack.pop();
            } else if ("+-*/^".indexOf(ch) != -1) {
                while (!opStack.isEmpty() && opStack.peek() != '(' &&
                       (precedence(opStack.peek()) > precedence(ch) ||
                        (precedence(opStack.peek()) == precedence(ch) &&
                         !rightAssoc.contains(ch)))) {
                    output.append(opStack.pop()).append(' ');
                }
                opStack.push(ch);
            }
        }
        
        while (!opStack.isEmpty()) {
            output.append(opStack.pop()).append(' ');
        }
        return output.toString().trim();
    }
    
    public static void main(String[] args) {
        System.out.println(convert("3+4"));       // 3 4 +
        System.out.println(convert("3+4*5"));     // 3 4 5 * +
        System.out.println(convert("(3+4)*5"));   // 3 4 + 5 *
    }
}

Monotonic Stack

A monotonic stack maintains elements in either increasing or decreasing order. It's a powerful technique for solving problems involving "next greater/smaller element" patterns.

Next Greater Element

For each element in an array, find the first element to its right that is larger. The brute force is \(O(n^2)\) (nested loops). The monotonic stack solves it in \(O(n)\): maintain a decreasing stack (stack top is always the smallest unresolved element). When a new element is larger than the stack top, it IS the "next greater" for that top element — pop and record the answer. Each element is pushed and popped at most once, guaranteeing \(O(n)\) total.

# Next Greater Element - Monotonic Decreasing Stack
# Time: O(n), Space: O(n)

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # Stack of indices
    
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result

# Test
nums = [4, 5, 2, 10, 8]
print(next_greater_element(nums))  # [5, 10, 10, -1, -1]

// Next Greater Element - Monotonic Stack

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

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk;  // Stack of indices
    
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && nums[stk.top()] < nums[i]) {
            result[stk.top()] = nums[i];
            stk.pop();
        }
        stk.push(i);
    }
    return result;
}

int main() {
    vector<int> nums = {4, 5, 2, 10, 8};
    vector<int> nge = nextGreaterElement(nums);
    // Output: [5, 10, 10, -1, -1]
    for (int x : nge) cout << x << " ";
    return 0;
}

// Next Greater Element - Monotonic Stack

import java.util.*;

public class NextGreaterElement {
    public static int[] nextGreater(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();  // Stack of indices
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums = {4, 5, 2, 10, 8};
        int[] nge = nextGreater(nums);
        System.out.println(Arrays.toString(nge));  // [5, 10, 10, -1, -1]
    }
}

Python - Circular Array

# Next Greater Element (Circular Array)

def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    
    # Process array twice to handle circular nature
    for i in range(2 * n):
        idx = i % n
        while stack and nums[stack[-1]] < nums[idx]:
            result[stack.pop()] = nums[idx]
        if i < n:
            stack.append(idx)
    
    return result

# Test
print(next_greater_circular([1, 2, 1]))  # [2, -1, 2]

Python - Next Smaller Element

# Next Smaller Element - Monotonic Increasing Stack

def next_smaller_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(n):
        while stack and nums[stack[-1]] > nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result

# Test
nums = [4, 5, 2, 10, 8]
print(next_smaller_element(nums))  # [2, 2, -1, 8, -1]

Daily Temperatures

# Daily Temperatures - Classic Monotonic Stack Problem

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stack of indices
    
    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)
    
    return result

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

// Daily Temperatures - Monotonic Stack

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

vector<int> dailyTemperatures(vector<int>& temps) {
    int n = temps.size();
    vector<int> result(n, 0);
    stack<int> stk;
    
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && temps[stk.top()] < temps[i]) {
            int prevIdx = stk.top();
            stk.pop();
            result[prevIdx] = i - prevIdx;
        }
        stk.push(i);
    }
    return result;
}

int main() {
    vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> days = dailyTemperatures(temps);
    // Output: [1, 1, 4, 2, 1, 1, 0, 0]
    for (int d : days) cout << d << " ";
    return 0;
}

// Daily Temperatures - Monotonic Stack

import java.util.*;

public class DailyTemperatures {
    public static int[] dailyTemperatures(int[] temps) {
        int n = temps.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
                int prevIdx = stack.pop();
                result[prevIdx] = i - prevIdx;
            }
            stack.push(i);
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] days = dailyTemperatures(temps);
        System.out.println(Arrays.toString(days));  // [1, 1, 4, 2, 1, 1, 0, 0]
    }
}

LeetCode Practice Problems

Easy 20. Valid Parentheses

Determine if the input string has valid bracket pairs.

# LeetCode 20 - Valid Parentheses
# Time: O(n), Space: O(n)

def isValid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:
            stack.append(char)
    return len(stack) == 0

# Test
print(isValid("()[]{}"))  # True
print(isValid("([)]"))    # False

bool isValid(string s) {
    stack<char> stk;
    unordered_map<char, char> mapping = {{')', '('}, {']', '['}, {'}', '{'}};
    
    for (char c : s) {
        if (mapping.count(c)) {
            if (stk.empty() || stk.top() != mapping[c])
                return false;
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.empty();
}

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    Map<Character, Character> map = Map.of(')', '(', ']', '[', '}', '{');
    
    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            if (stack.isEmpty() || stack.peek() != map.get(c))
                return false;
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

Easy 155. Min Stack

Design a stack that supports getMin() in \(O(1)\).

# LeetCode 155 - Min Stack

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
    
    def top(self):
        return self.stack[-1]
    
    def getMin(self):
        return self.min_stack[-1]

class MinStack {
    stack<int> stk;
    stack<int> minStk;
    
public:
    void push(int val) {
        stk.push(val);
        if (minStk.empty() || val <= minStk.top())
            minStk.push(val);
    }
    
    void pop() {
        if (stk.top() == minStk.top())
            minStk.pop();
        stk.pop();
    }
    
    int top() { return stk.top(); }
    int getMin() { return minStk.top(); }
};

class MinStack {
    Stack<Integer> stack = new Stack<>();
    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(); }
}

Medium 150. Evaluate Reverse Polish Notation

Evaluate postfix expression given as array of tokens.

# LeetCode 150 - Evaluate Reverse Polish Notation

def evalRPN(tokens):
    stack = []
    for token in tokens:
        if token in {'+', '-', '*', '/'}:
            b, a = stack.pop(), 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))
        else:
            stack.append(int(token))
    return stack[0]

print(evalRPN(["2","1","+","3","*"]))  # 9

int evalRPN(vector<string>& tokens) {
    stack<int> stk;
    for (const string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = stk.top(); stk.pop();
            int a = stk.top(); stk.pop();
            if (token == "+") stk.push(a + b);
            else if (token == "-") stk.push(a - b);
            else if (token == "*") stk.push(a * b);
            else stk.push(a / b);
        } else {
            stk.push(stoi(token));
        }
    }
    return stk.top();
}

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    Set<String> ops = Set.of("+", "-", "*", "/");
    
    for (String token : tokens) {
        if (ops.contains(token)) {
            int b = stack.pop(), 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;
            }
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

Medium 739. Daily Temperatures

Find how many days to wait for warmer temperature.

# LeetCode 739 - Daily Temperatures

def dailyTemperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []
    
    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            prev = stack.pop()
            result[prev] = i - prev
        stack.append(i)
    return result

vector<int> dailyTemperatures(vector<int>& temps) {
    int n = temps.size();
    vector<int> result(n, 0);
    stack<int> stk;
    
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && temps[stk.top()] < temps[i]) {
            result[stk.top()] = i - stk.top();
            stk.pop();
        }
        stk.push(i);
    }
    return result;
}

public int[] dailyTemperatures(int[] temps) {
    int n = temps.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
            int prev = stack.pop();
            result[prev] = i - prev;
        }
        stack.push(i);
    }
    return result;
}

Medium 84. Largest Rectangle in Histogram

Find the largest rectangle in a histogram.

# LeetCode 84 - Largest Rectangle in Histogram

def largestRectangleArea(heights):
    stack = []  # (index, height)
    max_area = 0
    
    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))
    
    for idx, height in stack:
        max_area = max(max_area, height * (len(heights) - idx))
    
    return max_area

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

int largestRectangleArea(vector<int>& heights) {
    stack<pair<int, int>> stk;  // (index, height)
    int maxArea = 0;
    
    for (int i = 0; i < heights.size(); i++) {
        int start = i;
        while (!stk.empty() && stk.top().second > heights[i]) {
            auto [idx, h] = stk.top();
            stk.pop();
            maxArea = max(maxArea, h * (i - idx));
            start = idx;
        }
        stk.push({start, heights[i]});
    }
    
    while (!stk.empty()) {
        auto [idx, h] = stk.top();
        stk.pop();
        maxArea = max(maxArea, h * ((int)heights.size() - idx));
    }
    return maxArea;
}

public int largestRectangleArea(int[] heights) {
    Stack<int[]> stack = new Stack<>();  // [index, height]
    int maxArea = 0;
    
    for (int i = 0; i < heights.length; i++) {
        int start = i;
        while (!stack.isEmpty() && stack.peek()[1] > heights[i]) {
            int[] top = stack.pop();
            maxArea = Math.max(maxArea, top[1] * (i - top[0]));
            start = top[0];
        }
        stack.push(new int[]{start, heights[i]});
    }
    
    while (!stack.isEmpty()) {
        int[] top = stack.pop();
        maxArea = Math.max(maxArea, top[1] * (heights.length - top[0]));
    }
    return maxArea;
}

Hard 32. Longest Valid Parentheses

Find the length of the longest valid parentheses substring.

# LeetCode 32 - Longest Valid Parentheses

def longestValidParentheses(s):
    stack = [-1]  # Base index
    max_len = 0
    
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # New base
            else:
                max_len = max(max_len, i - stack[-1])
    
    return max_len

print(longestValidParentheses(")()())"))  # 4

int longestValidParentheses(string s) {
    stack<int> stk;
    stk.push(-1);  // Base index
    int maxLen = 0;
    
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            stk.push(i);
        } else {
            stk.pop();
            if (stk.empty()) {
                stk.push(i);  // New base
            } else {
                maxLen = max(maxLen, i - stk.top());
            }
        }
    }
    return maxLen;
}

public int longestValidParentheses(String s) {
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);  // Base index
    int maxLen = 0;
    
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);  // New base
            } else {
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }
    return maxLen;
}

Next in the Series

In Part 8: Queue, we’ll complement the stack with queues — FIFO, circular, deque, and priority queue implementations that power BFS, scheduling, and sliding-window problems.