A stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. This means the last element added to the stack is the first one to be removed. Think of it like a stack of plates; you add a plate to the top and remove a plate from the top.

Core Operations:

  • Push: Adds an element to the top of the stack.
  • Pop: Removes and returns the element from the top of the stack.
  • Peek (or Top): Returns the element at the top of the stack without removing it.
  • isEmpty: Checks if the stack is empty.
  • Size: Returns the number of elements in the stack.

Common Scenarios & How it Works:

  1. Function Call Management (Call Stack): Programming languages use a stack to manage function calls. When a function is called, it’s pushed onto the stack. When it returns, it’s popped off.
  2. Expression Evaluation & Parsing:
    • Infix to Postfix/Prefix Conversion: Stacks are used to convert expressions between different notations.
    • Evaluating Postfix/Prefix Expressions: A stack can efficiently evaluate expressions in these forms.
    • Balancing Parentheses/Brackets/Braces (e.g., LeetCode #20): A stack is used to ensure that every opening symbol has a corresponding closing symbol in the correct order.
  3. Undo/Redo Functionality: Applications often use stacks to store states or operations, allowing users to undo the last action (pop from stack) or redo it (push back to stack).
  4. Depth-First Search (DFS) for Graphs and Trees: An iterative DFS algorithm typically uses a stack to keep track of the nodes to visit.
  5. Backtracking Problems: Stacks can be used to manage the path taken in a backtracking algorithm, making it easy to revert to a previous state.
  6. Monotonic Stack (e.g., Next Greater Element - LeetCode #496, #503, #739): A stack where elements are kept in a specific order (e.g., increasing or decreasing). This is useful for problems where you need to find the next/previous greater/smaller element for each element in an array.
  7. Simplifying Path (e.g., LeetCode #71): Stacks can be used to process directory structures and simplify file paths.
  8. Browser History: Navigating back and forth in a web browser can be modeled using two stacks (one for back history, one for forward history).

Advantages:

  • Simplicity: The LIFO principle and basic operations are easy to understand and implement.
  • Efficiency: Push, pop, peek, and isEmpty operations are typically O(1) time complexity when using an array or linked list as the underlying implementation.
  • Memory Management: Helps manage memory for function calls (call stack).
  • Natural for Recursive Problems: Many recursive algorithms can be implemented iteratively using a stack.

When to Use:

  • When the problem involves processing elements in a LIFO order.
  • For reversing the order of items.
  • In algorithms involving backtracking or recursion (iterative implementation).
  • For parsing and evaluating expressions, especially with parentheses or operator precedence.
  • When you need to keep track of “nested” structures or states.

Example LeetCode Problems:

  1. (#20) Valid Parentheses
  2. (#71) Simplify Path
  3. (#150) Evaluate Reverse Polish Notation
  4. (#155) Min Stack
  5. (#225) Implement Stack using Queues
  6. (#232) Implement Queue using Stacks
  7. (#496) Next Greater Element I
  8. (#739) Daily Temperatures
  9. (#84) Largest Rectangle in Histogram (Often solved using a monotonic stack)
  10. (#94) Binary Tree Inorder Traversal (Iterative solution uses a stack)
  11. (#144) Binary Tree Preorder Traversal (Iterative solution uses a stack)
  12. (#145) Binary Tree Postorder Traversal (Iterative solutions often use one or two stacks)