Section 1: Core Concept (Clubbed)

Introduction

Stacks and queues are fundamental linear data structures commonly tested in coding interviews. Each enforces a different access order: a stack uses Last-In-First-Out (LIFO) ordering, while a queue uses First-In-First-Out (FIFO). In practice this means a stack always removes the most recently added element first, whereas a queue always removes the longest-waiting element first.

Interview problems often leverage these behaviors – for example, a stack might be used for backtracking or expression parsing, while a queue suits level-by-level traversal or task scheduling.

When to use a Stack vs. Queue?

• Stack (LIFO): Use for “recently used” or “undo” scenarios, nested/recursive structures (e.g., parentheses matching), or backtracking.
• Queue (FIFO): Use for “first-come, first-served” processing, level-order traversal (BFS), or buffering incoming data in order.

Core Idea / Mental Model

Stack (Last-In, First-Out): Imagine a stack of plates. You push new items onto the top, and pop items off from the top. The last item added is the first removed. Like an "undo" operation or programming call stack.

Queue (First-In, First-Out): Think of a line of people. The first person in line is served first; new people join at the end. You enqueue (add) at the back (rear) and dequeue (remove) from the front. Ensures fairness, used in BFS or task schedulers.

Base Template (Python)

Basic algorithmic patterns using a stack and a queue:

Stack-based Depth-First Search (DFS) template

# Assume start_node and node.neighbors are defined
stack = [start_node]
visited = {start_node}
while stack:
    node = stack.pop() # LIFO
    # process(node)
    for neighbor in reversed(node.neighbors): # Process left children first if applicable
        if neighbor not in visited:
            stack.append(neighbor)
            visited.add(neighbor)

In DFS, new elements go on top of the stack, processed before older ones. visited set prevents cycles in graphs.

Queue-based Breadth-First Search (BFS) template

from collections import deque
# Assume start_node and node.neighbors are defined
queue = deque([start_node])
visited = {start_node}
while queue:
    node = queue.popleft() # FIFO
    # process(node)
    for neighbor in node.neighbors:
        if neighbor not in visited:
            queue.append(neighbor)
            visited.add(neighbor)

In BFS, elements are processed in arrival order. deque ensures O(1) enqueue/dequeue. visited set prevents cycles.

Animation (Stack vs. Queue Operations)

The animation below demonstrates the fundamental LIFO (Stack) and FIFO (Queue) behaviors. Select a mode, enter a number, and use Push/Pop or Enqueue/Dequeue to see how the structure changes.

Time & Space Complexity

Operations Complexity:

These complexities assume efficient implementations (e.g., Python's list for stack, collections.deque for queue).

Algorithmic Complexity:

Many algorithms using stacks/queues (like BFS/DFS on n nodes) run in O(n) time. Space complexity is also often O(n) for storing elements or visited sets. For graphs, BFS/DFS are O(V+E) time and space.

Note: Using Python list's pop(0) for dequeuing is O(n). Prefer collections.deque for O(1) queue operations.

Common Pitfalls

• Off-by-one Errors: Miscalculating boundaries with array-based implementations.
• Forgetting Empty Checks: Popping/dequeuing from empty structures causes errors.
• Infinite Loops: Not updating loop conditions or visited sets correctly in traversals.
• Wrong Base/Edge Conditions: Missing base cases in recursion or improper loop setup.
• Incorrect Order of Operations: Pushing/enqueuing in an order that yields wrong processing sequence (e.g., for DFS stack, push neighbors in reverse of desired visit order).
• Neglecting to Free or Reset: Carrying over stale data if reusing structures across test cases.
• Using Suboptimal Operations: E.g., Python list's pop(0) for queue dequeue (O(n)) instead of deque.popleft() (O(1)).