Stacks & Queues

Stacks and Queues are fundamental linear data structures that manage data in a specific order. Unlike arrays where you can access any element at any index, stacks and queues strictly control how data is added and removed.

1. Stack (LIFO - Last In, First Out)

Think of a stack like a pile of plates.

• Push: You add a new plate on top.
• Pop: You remove the top plate.
• LIFO: The Last plate you put on is the First one you take off.

Common Operations:

• push(x): Add x to the top. $O(1)$
• pop(): Remove and return the top element. $O(1)$
• peek(): Look at the top element without removing it. $O(1)$
• isEmpty(): Check if the stack is empty. $O(1)$

Use Cases:

• Function Call Stack: managing recursion and function calls.
• Undo/Redo: storing history of actions.
• Expression Evaluation: parsing math expressions (e.g., Reverse Polish Notation).
• Depth-First Search (DFS): exploring graphs/trees.

2. Queue (FIFO - First In, First Out)

Think of a queue like a line of people waiting for a bus.

• Enqueue: A person joins the back of the line.
• Dequeue: The person at the front gets on the bus.
• FIFO: The First person to join is the First one to leave.

Common Operations:

• enqueue(x): Add x to the back (tail). $O(1)$
• dequeue(): Remove and return the front (head) element. $O(1)$
• peek(): Look at the front element. $O(1)$
• isEmpty(): Check if the queue is empty. $O(1)$

Use Cases:

• Breadth-First Search (BFS): finding shortest paths in unweighted graphs.
• Job Scheduling: printer queues, CPU task scheduling.
• Data Streaming: buffering data between producers and consumers.

3. Implementation Details

Both structures can be implemented using Dynamic Arrays or Linked Lists.

Note on Python/Java/C++:

• Python: Use list for stacks (append/pop). Use collections.deque for queues (append/popleft).
• Java: Use Stack or ArrayDeque for stacks. Use LinkedList or ArrayDeque for queues.
• C++: Use std::stack and std::queue.

Reusable Idea: Reframe Balanced Parentheses as Plot Heights

We can visualize a string of parentheses as a plot that starts at 0 and goes up for each opening parenthesis and down for each closing parenthesis:

The plot for a balanced string creates a valid 'mountain range outline':

1. it never goes below height 0, and
2. it ends at height 0.

Balanced parentheses questions are often easier to solve when reframed in terms of this plot.

def balanced(s):
    height = 0
    for c in s:
        if c == '(':
            height += 1
        else:
            height -= 1
        if height < 0:
            return False
    return height == 0

This code is simple enough that we didn't need any data structure, but we'll see harder balanced parentheses problems later where stacks will be helpful.

As an example of how the mountain range visualization is useful, imagine you have a balanced string, and you want to find the parentheses that are most deeply nested in other parentheses. You would just need to find the highest point in the plot (peak in the mountain range).