Complete DSA Series Part 7: Stack

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 Operations

Stack Implementations

Array-Based Stack

Python

# 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

C++

// 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;
}

Java

// 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)

Python

# 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

C++

// 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;
}

Java

// 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

Python

# 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

C++

// 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;
}

Java

// 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
    }
}

Stack Applications

Parentheses Matching

Python

# 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

C++

// 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;
}

Java

// 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

Python - Postfix 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

C++ - Postfix Evaluation

// 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;
}

Java - Postfix Evaluation

// 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

Python

# 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 *

C++

// 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;
}

Java

// 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

Python

# 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]

C++

// 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;
}

Java

// 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

Python

# 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]

C++

// 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;
}

Java

// 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

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

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

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

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

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

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