5.1 Stacks (LIFO) & Queues (FIFO)

1. What Are Stacks & Queues?

• Stack (LIFO — Last-In, First-Out): Picture a stack of cafeteria trays. You can only put a new tray on the very top (push) and take the tray from the very top (pop). The last item you put in is always the first item that comes out.
• Queue (FIFO — First-In, First-Out): Picture a line of people waiting for coffee. New people join at the back (enqueue), and the person at the front gets served first (dequeue). The first item in is the first item out.

2. Why Do We Need Stacks & Queues?

If a normal Array lets you read and write anywhere, why restrict yourself to only touching the top or ends?

1. Stacks Remember "The Most Recent Unfinished Business": When you read nested brackets like "{ [ ( ) ] }" or nested function calls, which bracket must close first? The ( ) that opened most recently! A Stack naturally holds opening brackets so the top of the stack is always the exact bracket waiting to be closed next.
2. Queues Guarantee Fair Order & Level-by-Level Exploration: When exploring a tree or graph floor by floor (Breadth-First Search), a Queue ensures every node at distance 1 is processed before any node at distance 2.
3. Every Operation Is O(1): Pushing, popping, and peeking at the top of a Stack or ends of a Deque never shifts elements in memory (O(1) time). (Warning: In Python, never use list.pop(0) for a queue—that shifts the whole list in O(N) time! Always use collections.deque.)

3. Basic Operations & Walkthroughs (All 4 Languages)

from collections import deque

# 1. Stack (LIFO) — Use a normal Python list
stack = []
stack.append(10)        # push 10 -> [10]
stack.append(20)        # push 20 -> [10, 20]
top_val = stack[-1]     # peek top -> 20 (O(1))
popped = stack.pop()    # pop top  -> 20 (O(1))

# 2. Queue (FIFO) — Always use collections.deque!
q = deque()
q.append("A")           # enqueue back  -> ["A"]
q.append("B")           # enqueue back  -> ["A", "B"]
front_val = q[0]        # peek front    -> "A" (O(1))
out = q.popleft()       # dequeue front -> "A" (O(1))

3B. More Operations: Circular Queue & Implementing a Queue Using Two Stacks

Before jumping into LeetCode problems, top product companies (Amazon, Microsoft, Apple) frequently ask how Stacks and Queues are built under the hood:

1. Circular Buffer Queue (Fixed-Size Array with Wrap-Around)

How do operating systems build a fast O(1) Queue inside a fixed-size array of capacity K without ever shifting elements? They keep head and tail indices and wrap around the end of the array using the modulo operator (index + 1) % K!

2. Building a FIFO Queue Using Two LIFO Stacks (Implement Queue using Stacks)

If you push [1, 2, 3] into an in_stack, 3 sits on top (LIFO). How do you get 1 out first (FIFO)? When out_stack is empty, pop everything from in_stack and push it into out_stack ([3, 2, 1]). Pouring from one stack into another reverses the order twice, putting 1 right on top of out_stack in amortized O(1) time!

Warm-Up Example Before Interview Problems: Remove Adjacent Duplicates ("abbaca" -> "ca")

Let's trace a simple beginner problem before tackling nested brackets:

• Read 'a' -> stack is ['a']
• Read 'b' -> stack is ['a', 'b']
• Read 'b' -> matches top of stack ('b')! Pop 'b' -> stack is back to ['a']!
• Read 'a' -> matches top of stack ('a')! Pop 'a' -> stack is []!
• Read 'c', then 'a' -> final stack is ['c', 'a'] -> "ca" in one O(N) pass!

# Warm-Up: Remove Adjacent Duplicates in a String -> O(N) time, O(N) space
def remove_duplicates(s: str) -> str:
  stack = []
  for ch in s:
      if stack and stack[-1] == ch:
          stack.pop()      # Duplicate pair cancels out!
      else:
          stack.append(ch)
  return "".join(stack)

# Classic Under-the-Hood Operation: FIFO Queue Using Two LIFO Stacks -> O(1) amortized
class MyQueue:
  def __init__(self):
      self.in_st, self.out_st = [], []

  def push(self, x: int) -> None:
      self.in_st.append(x)

  def pop(self) -> int:
      self.peek()
      return self.out_st.pop()

  def peek(self) -> int:
      if not self.out_st:
          while self.in_st:
              self.out_st.append(self.in_st.pop())
      return self.out_st[-1]

4. Core Interview Patterns

Pattern A: Bracket & Expression Matching (Valid Parentheses)

Push every opening bracket (, [, { onto the stack. Whenever a closing bracket arrives, check if the stack is non-empty and its top matches. At the very end, the stack must be completely empty!

Pattern B: Prefix-Min / Auxiliary State Stack (Min Stack)

How do you support getMin() in O(1) time even as items are popped off a stack? Instead of storing just val on the stack, push a pair (val, current_min_so_far) at every slot! That way, every item on the stack remembers what the minimum of the stack was at the moment it arrived.

class MinStack:
  def __init__(self):
      self.st = []  # stores (val, min_at_this_depth)
  def push(self, val: int) -> None:
      cur_min = val if not self.st else min(val, self.st[-1][1])
      self.st.append((val, cur_min))
  def pop(self) -> None:
      self.st.pop()
  def getMin(self) -> int:
      return self.st[-1][1]

5. Practice On Your Own (Curated Submodule Problems)