You’ve mastered the strict rules of LIFO and FIFO. You can now build calculators, process browser history, and optimize sliding windows.

1. Real-World Context

  • Stacks: Undo/Redo mechanisms in text editors, call stack in programming languages, browser history (back button).
  • Queues: Task scheduling (e.g., printing jobs), BFS in graphs, managing requests in web servers, message brokers (Kafka/RabbitMQ).

2. Key Takeaways

  • The Difference: Stack = LIFO (Plates). Queue = FIFO (Coffee Line).
  • Performance: All operations (Push, Pop, Enqueue, Dequeue) must be O(1).
  • Hardware: Stacks power recursion and function calls. Queues power task scheduling and buffers.
  • Patterns:
  • Monotonic Stack: Solves “Next Greater Element” in O(N).
  • Monotonic Deque: Solves “Sliding Window Max” in O(N).
  • Two Stacks: Can implement a MinStack or a Queue.

3. Cheat Sheet

Operation Stack (Array/List) Queue (List) Queue (Array) Deque
Add Push (Top) O(1) Enqueue (Back) O(1) Enqueue (Back) O(1)* AddFirst/Last O(1)
Remove Pop (Top) O(1) Dequeue (Front) O(1) Dequeue (Front) O(N)** RemoveFirst/Last O(1)
Access Peek (Top) O(1) Peek (Front) O(1) Peek (Front) O(1) PeekFirst/Last O(1)

(*) Array Queue is O(1) amortized. () Array Queue Dequeue is O(N) unless implemented as a **Ring Buffer (Circular Queue), then O(1).

4. Interactive Flashcards

Test your knowledge. Click to flip.

What data structure is used for Breadth-First Search (BFS)?
Queue (FIFO).
What data structure is used for Depth-First Search (DFS) / Recursion?
Stack (LIFO).
Why is `java.util.Stack` deprecated?
It is synchronized (slow) and inherits from Vector. Use `ArrayDeque` instead.
What problem does a Monotonic Stack solve efficiently?
Finding the Next Greater/Smaller Element for every item in an array (O(N)).
What is the Shunting-yard algorithm used for?
Converting Infix expressions (3+4) to Postfix (3 4 +) for easier evaluation.
What is a Deque?
A Double-Ended Queue where elements can be added or removed from both ends in O(1) time.

5. Next Steps

  • Explore hierarchical structures in the Trees module.
  • Check the DSA Glossary for key term definitions.

6. Common Pitfalls

  • Assuming O(1) for all Queue operations: An array-based queue can have O(N) dequeue if elements are shifted. Always use a Ring Buffer or a Linked List for true O(1) dequeue.
  • Ignoring Thread Safety: While operations are O(1), standard Stacks/Queues are usually not thread-safe. Concurrent applications require specialized implementations (e.g., ConcurrentLinkedQueue).

7. Quick Revision

  • Stacks follow Last-In-First-Out (LIFO).
  • Queues follow First-In-First-Out (FIFO).
  • Monotonic stacks enforce elements strictly increasing/decreasing.
  • Deques support efficient operations at both ends.

8. Practice in the Vault

Looking to solidify your understanding? Head over to the Problem Vault to solve curated problems related to this module with detailed walkthroughs and optimal solutions.