🌱 Keegan's Digital Garden

03. Stacks & Queues

2 min read

Stack Queue

Stacks: Use Cases in Recursive Algorithms

  • Temporary Data Storage:

    • Push temporary data onto the stack during recursion and pop it off as you backtrack.
    • Example: Depth-first search (DFS), backtracking problems (e.g., maze solving, N-Queens).

  • Imitating Recursion:

    • Stacks can replace recursion by mimicking the call stack.
    • Example: Converting recursive DFS into an iterative implementation.

Queues: Use Cases in Iterative Algorithms

  • Breadth-First Search (BFS):
    • Use a queue to explore nodes level by level in graph or tree traversal.
  • Cache Implementation:
    • Queues (or dequeues) are used in algorithms like Least Recently Used (LRU) cache.

  1. Stack Problems:

    • Often involve last-in, first-out (LIFO) behavior.
    • Common tasks:
      • Evaluating expressions (e.g., postfix or infix conversion).
      • Validating parentheses or syntax.
      • Undo functionality.

  2. Queue Problems:

    • Typically follow first-in, first-out (FIFO) behavior.
    • Common tasks:
      • Task scheduling.
      • Level-order traversal in trees (BFS).
      • Managing resource requests in real-time systems.

  3. Identify Problem Types:

    • Look for patterns like:
      • Recursive problems → May use stacks.
      • Sequential processing → Likely involves queues.

  4. Optimize for Edge Cases:

    • Empty queues or stacks.
    • Overflow or underflow scenarios.

  5. Leverage Data Structures:

    • For stacks: Use std::stack in C++.
    • For queues: Use std::queue or std::deque in C++ for more flexibility.

  6. Visualize the Process:

    • Draw diagrams for stack or queue operations to avoid off-by-one errors.

Key Applications

  • Stacks:

    • Expression evaluation and syntax parsing.
    • Undo/Redo functionality.
    • Depth-first search (DFS).

  • Queues:

    • Breadth-first search (BFS).
    • Task scheduling systems.
    • Real-time streaming or messaging queues.

Graph View