Stacks & Queues | DSA Prep

Core Concepts

While conceptually simple, these structures are the backbone of many advanced algorithms.

Stack (LIFO): Used for tracking state, parsing expressions, and Depth First Search. The Monotonic Stack pattern is common for "next greater element" problems.
Queue (FIFO): The fundamental data structure for Breadth First Search and scheduling tasks.

block-beta columns 2 block:Stack A["Push(3)"] B["Push(2)"] C["Push(1)\n(Top)"] end block:Queue X["Enqueue(1)\n(Front)"] Y["Enqueue(2)"] Z["Enqueue(3)\n(Back)"] end

Cheatsheet Formulas

Monotonic Increasing Stack: Find "Next Smaller Element". Loop elements, while stack not empty and curr < stack.top(), pop stack.
Monotonic Decreasing Stack: Find "Next Greater Element". Loop elements, while stack not empty and curr > stack.top(), pop stack.
Queue for BFS: queue.append(root). Loop while queue: pop front, process, push children.

Classic Problem: Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}
        
        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
                
        return not stack