Initialize empty stack
Initialize result array

For i from n-1 down to 0:

    While stack not empty AND
          stack.top <= arr[i]:
        pop stack

    If stack empty:
        result[i] = -1
    Else:
        result[i] = stack.top

    push arr[i] onto stack

Return result

Types

• Increasing stack → Next Smaller
• Decreasing stack → Next Greater

Time: O(n) Each element pushed/popped once.

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();

    for (int i = n - 1; i >= 0; i--) {

        while (!stack.isEmpty() &&
               stack.peek() <= nums[i]) {
            stack.pop();
        }

        result[i] = stack.isEmpty() ?
                    -1 : stack.peek();

        stack.push(nums[i]);
    }
    return result;
}

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

    for i in range(n - 1, -1, -1):

        while stack and stack[-1] <= nums[i]:
            stack.pop()

        if stack:
            result[i] = stack[-1]

        stack.append(nums[i])

    return result

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n);
    stack<int> st;

    for (int i = n - 1; i >= 0; i--) {

        while (!st.empty() && st.top() <= nums[i]) {
            st.pop();
        }

        result[i] = st.empty() ? -1 : st.top();

        st.push(nums[i]);
    }
    return result;
}

function nextGreaterElement(nums) {
    const n = nums.length;
    const result = new Array(n);
    const stack = [];

    for (let i = n - 1; i >= 0; i--) {

        while (stack.length > 0 &&
               stack[stack.length - 1] <= nums[i]) {
            stack.pop();
        }

        result[i] = stack.length === 0 ?
                    -1 : stack[stack.length - 1];

        stack.push(nums[i]);
    }
    return result;
}

Initialize empty stack

For each character:
    If opening bracket:
        push to stack
    Else if closing bracket:
        If stack empty OR mismatch:
            return false
        pop stack

Return stack is empty

When to use

• Parentheses validation
• Expression evaluation
• Undo / backtracking simulation

Time: O(n)

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

    for (char c : s.toCharArray()) {

        if (c == '(' || c == '{' || c == '[')
            stack.push(c);
        else {
            if (stack.isEmpty())
                return false;

            char top = stack.pop();

            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '['))
                return false;
        }
    }
    return stack.isEmpty();
}

def is_valid(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for c in s:

        if c in '([{':
            stack.append(c)
        else:
            if not stack or stack[-1] != pairs[c]:
                return False
            stack.pop()

    return len(stack) == 0

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 top = st.top();
            st.pop();

            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '['))
                return false;
        }
    }
    return st.empty();
}

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

    for (const c of s) {

        if (c === '(' || c === '{' || c === '[') {
            stack.push(c);
        } else {
            if (stack.length === 0 ||
                stack[stack.length - 1] !== pairs[c])
                return false;

            stack.pop();
        }
    }
    return stack.length === 0;
}

Initialize mainStack
Initialize minStack

Push(x):
    push x to mainStack
    If minStack empty OR x <= minStack.top:
        push x to minStack

Pop():
    If popped value == minStack.top:
        pop minStack

GetMin():
    return minStack.top

Key Idea Maintain auxiliary stack to track running minimum.

Time: O(1) per operation

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);

        if (minStack.isEmpty() ||
            val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        int removed = stack.pop();

        if (removed == minStack.peek())
            minStack.pop();
    }

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

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

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):
        removed = self.stack.pop()

        if removed == 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 {
public:
    stack<int> st;
    stack<int> minSt;

    MinStack() {}

    void push(int val) {
        st.push(val);

        if (minSt.empty() || val <= minSt.top())
            minSt.push(val);
    }

    void pop() {
        int removed = st.top();
        st.pop();

        if (removed == minSt.top())
            minSt.pop();
    }

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

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

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

    push(val) {
        this.stack.push(val);

        if (this.minStack.length === 0 ||
            val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }

    pop() {
        const removed = this.stack.pop();

        if (removed === 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];
    }
}

Initialize stack
Push starting node
Mark visited

While stack not empty:
    node = pop
    process node

    For each neighbor:
        If not visited:
            mark visited
            push neighbor

When to use

• Replace recursive DFS
• Avoid stack overflow
• Control traversal order

Time: O(V + E)

public void dfsIterative(List<List<Integer>> graph,
                         int start) {

    boolean[] visited =
        new boolean[graph.size()];

    Stack<Integer> stack = new Stack<>();
    stack.push(start);
    visited[start] = true;

    while (!stack.isEmpty()) {

        int node = stack.pop();
        System.out.print(node + " ");

        for (int neighbor :
             graph.get(node)) {

            if (!visited[neighbor]) {
                visited[neighbor] = true;
                stack.push(neighbor);
            }
        }
    }
}

def dfs_iterative(graph, start):

    visited = [False] * len(graph)

    stack = []
    stack.append(start)
    visited[start] = True

    while stack:

        node = stack.pop()
        print(node, end=" ")

        for neighbor in graph[node]:

            if not visited[neighbor]:
                visited[neighbor] = True
                stack.append(neighbor)

void dfsIterative(vector<vector<int>>& graph,
                  int start) {

    vector<bool> visited(graph.size(), false);

    stack<int> st;
    st.push(start);
    visited[start] = true;

    while (!st.empty()) {

        int node = st.top();
        st.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {

            if (!visited[neighbor]) {
                visited[neighbor] = true;
                st.push(neighbor);
            }
        }
    }
}

function dfsIterative(graph, start) {

    const visited =
        new Array(graph.length).fill(false);

    const stack = [];
    stack.push(start);
    visited[start] = true;

    while (stack.length > 0) {

        const node = stack.pop();
        process.stdout.write(node + " ");

        for (const neighbor of graph[node]) {

            if (!visited[neighbor]) {
                visited[neighbor] = true;
                stack.push(neighbor);
            }
        }
    }
}