DSA

Part 8 — Stacks & Queues

The LIFO and FIFO Patterns Every Python Coding Interviewer Expects You to Know.

Deepak Mishra18 min read

Stacks and queues are among the simplest data structures in computer science. Yet they appear repeatedly in coding interviews because they test something much more important than syntax:

Can you recognize the order in which information needs to be processed and choose the right data structure to preserve that order?

In the Elements of Programming Interviews in Python chapter on Stacks and Queues, the focus moves from basic LIFO/FIFO behavior to practical interview problems such as expression evaluation, bracket matching, path normalization, sunset-view buildings, breadth-first tree traversal, circular queues, implementing queues with stacks, and maintaining a queue maximum. For a Staff / Principal / Senior ML Engineer, however, memorizing these individual problems is not enough. The real objective is to recognize the reusable patterns behind them.

1. The Big Picture

There are two fundamental ordering models: STACK LIFO Last In → First Out

        ┌───┐         │ 3 │ ← pop         ├───┤         │ 2 │         ├───┤         │ 1 │         └───┘           ↑          push and: QUEUE FIFO First In → First Out

front                         back   ↓                             ↓ ┌───┬───┬───┬───┐ │ 1 │ 2 │ 3 │ 4 │ └───┴───┴───┴───┘   ↑               ↑ dequeue         enqueue The distinction is deceptively simple:

Data structure Ordering Typical operations
Stack LIFO push, pop, peek
Queue FIFO enqueue, dequeue
Deque Both ends append/pop from either side

The important interview question is not:

“What is a stack?”

It is:

“Why is a stack the correct abstraction for this problem?”

2. Stack: The LIFO Pattern

A stack supports two fundamental operations: push(x) pop() If we push: 1 2 3 4 the stack becomes: 4 ← top

3 2 1 The next pop() returns 4. Then: pop() → 3 pop() → 2 pop() → 1 This is Last-In, First-Out (LIFO). The chapter emphasizes that stack operations can be implemented with constant-time operations when the underlying representation supports insertion/removal at the appropriate end.

3. Python Stack Implementation

For most interview problems, Python’s list is sufficient. stack = []

stack.append(10) stack.append(20) stack.append(30)

top = stack[-1]

value = stack.pop() After the pushes: [10, 20, 30] pop() returns: 30

Complexity

push → O(1) amortized pop  → O(1) peek → O(1) A common interview mistake is using the beginning of a list: stack.insert(0, x) stack.pop(0) These operations require shifting elements. Prefer the end of the list.

4. The First Important Stack Pattern: Remembering History

One of the most useful ways to recognize a stack problem is:

The most recent unresolved item must be handled first.

Examples include:

  • matching parentheses
  • undo operations
  • expression evaluation
  • browser history
  • nested structures
  • reversing sequences
  • DFS
  • parsing
  • path normalization

Think: New information       ↓ Does it need to interact with the most recent unresolved item?       ↓      YES       ↓     STACK That mental model is much more valuable than memorizing individual solutions.

5. Problem 1 — Stack With a Maximum

One of the chapter’s first problems asks us to augment a stack so that it supports: push() pop() max() The challenge is making max() efficient. A naive implementation is: def max_value(stack):     return max(stack) But this requires scanning the entire stack. max() → O(n) Can we do better? Yes.

6. Pattern: Cache the Maximum

Suppose the stack contains: 2 7 4 9 At each position, maintain the maximum seen so far: value    max_so_far

2        2 7        7 4        7 9        9 Then the maximum can be obtained immediately. A clean implementation is: class MaxStack:     def __init__(self):         self.data = []         self.max_values = []

    def push(self, x):         self.data.append(x)

        if not self.max_values:             self.max_values.append(x)         else:             self.max_values.append(                 max(x, self.max_values[-1])             )

    def pop(self):         self.max_values.pop()         return self.data.pop()

    def max(self):         return self.max_values[-1] Now: push → O(1) pop  → O(1) max  → O(1) The trade-off is additional memory: Space → O(n)

7. A More Advanced Optimization

We don’t necessarily need to store the maximum for every element. Suppose: 5 5 5 5 All four elements have the same maximum. Instead of storing: 5 5 5 5 we can store: (value=5, count=4) This illustrates an important Staff-level principle:

Optimize memory by storing state transitions rather than redundant state.

This is a recurring theme in algorithm design.

8. Problem 2 — Evaluate Reverse Polish Notation

Consider: 3 4 + 2 * 1 + Instead of conventional notation: ((3 + 4) * 2) + 1 the operator comes after its operands. This is called Reverse Polish Notation (RPN). The key observation is:

Whenever an operator appears, it operates on the most recently available operands.

That screams: STACK.

9. RPN Algorithm

Process tokens from left to right.

If token is a number

Push it.

If token is an operator

Pop the required operands, perform the operation, and push the result. Example: 3 4 + Stack: [3, 4] Apply +: 3 + 4 = 7 Stack: [7] Then: 2 * becomes: 7 * 2 = 14 Finally: 1 + gives: 15

Python

def evaluate_rpn(expression):     stack = []

    for token in expression.split():         if token in {“+”, “-”, “*”, “/”}:             right = stack.pop()             left = stack.pop()

            if token == “+”:                 result = left + right             elif token == “-”:                 result = left - right             elif token == “*”:                 result = left * right             else:                 result = int(left / right)

            stack.append(result)         else:             stack.append(int(token))

    return stack[-1]

Complexity

For n tokens: Time  → O(n) Space → O(n)

10. Problem 3 — Valid Parentheses

Consider: { [ ( ) ] } Is it valid? The challenge isn’t simply counting brackets. We must ensure that the most recently opened bracket is the one being closed. For example: ([)] is invalid. Why? When we encounter: ) the most recent unmatched opening bracket is: [ not: ( Again:

Most recent unresolved item → Stack

11. Parentheses Algorithm

def is_well_formed(s):     stack = []     matching = {         ‘)’: ‘(’,         ‘]’: ‘[’,         ‘}’: ‘{’     }

    for ch in s:         if ch in “([{”:             stack.append(ch)

        elif ch in matching:             if not stack or stack.pop() != matching[ch]:                 return False

    return not stack The important invariant is:

The stack contains exactly the unmatched opening brackets encountered so far.

Complexity

Time  → O(n) Space → O(n)

12. Problem 4 — Normalize a File Path

Consider: /usr/lib/../bin/./gcc We want the shortest equivalent path. Special components: .   → current directory ..  → parent directory This is another stack problem. Process each directory: usr lib .. bin . gcc Rules: name → push .    → ignore ..   → pop Implementation: def normalize_path(path):     stack = []

    for part in path.split(“/”):         if part in (“”, “.”):             continue

        if part == “..”:             if stack:                 stack.pop()         else:             stack.append(part)

    return “/” + “/”.join(stack) For: /usr/lib/../bin/./gcc we get: /usr/bin/gcc Again: Time  → O(n) Space → O(n)

13. Problem 5 — Buildings With a Sunset View

This is one of the most interesting stack applications. Suppose buildings have heights: 3, 5, 2, 4, 6 Every building faces west. A building cannot see the sunset if a building to its west is at least as tall. The naive approach: For every building:     compare with all buildings to its west This can become: O(n²) But there is a better observation. When processing buildings from west to east:

A shorter building can become irrelevant once a taller building appears.

That suggests a monotonic stack.

14. Monotonic Stack

For each new building: while stack_top <= current_height:     pop() Then: push(current) Example: 3 Stack: [3] Next: 5 Since: 3 <= 5 remove 3. Stack: [5] Next: 2 Stack: [5, 2] Next: 4 Remove: 2 because 4 blocks it. Stack: [5, 4] Finally: 6 removes: 4 5 leaving: [6] The stack contains exactly the relevant candidates.

15. The Monotonic Stack Pattern

This is much more important than this individual problem. Whenever you see:

  • next greater element
  • previous greater element
  • next smaller element
  • skyline problems
  • histogram problems
  • temperature problems
  • visibility problems

think:

Monotonic stack

The key insight is:

Elements that can no longer influence the answer should be removed immediately.

Complexity

Although a while loop exists inside the loop, the total complexity is: O(n) Why? Every element is: pushed at most once popped at most once Therefore: Total operations ≤ 2n So: Time  → O(n) Space → O(n) This is an extremely important interview pattern.

16. Queue: The FIFO Pattern

A queue reverses the ordering principle. First In → First Out Think of:

  • print queues
  • task queues
  • request processing
  • message brokers
  • BFS
  • scheduling
  • producer/consumer systems

Example: enqueue(1) enqueue(2) enqueue(3) Queue: front  ↓ [1, 2, 3]           ↑          back Then: dequeue() → 1

17. Python’s deque

For queues, Python provides: from collections import deque Use: q = deque()

q.append(10) q.append(20) q.append(30)

value = q.popleft() Operations: append()  → O(1) popleft() → O(1) This is generally preferable to: list.pop(0) because removing from the beginning of a Python list requires shifting elements.

18. Queue and Deque

A deque—double-ended queue—supports operations at both ends. append() appendleft()

pop() popleft() This makes it useful when a problem requires controlled access to both the front and the back.

19. Problem 6 — Binary Tree Nodes by Depth

Now we see one of the most important applications of queues: Breadth-First Search (BFS). Suppose we want: nodes at depth 0 nodes at depth 1 nodes at depth 2 … A queue is a natural fit because nodes should be processed in the order they are discovered. The pattern is: Current level      ↓ Process nodes      ↓ Generate children      ↓ Next level

20. Level-Order Traversal

from collections import deque

def level_order(root):     if not root:         return []

    result = []     current = deque([root])

    while current:         level = []

        for _ in range(len(current)):             node = current.popleft()             level.append(node.data)

            if node.left:                 current.append(node.left)

            if node.right:                 current.append(node.right)

        result.append(level)

    return result The key invariant:

At the beginning of each iteration, the queue contains exactly the nodes belonging to the current depth.

This invariant is more important than the code.

Complexity

Every node is: enqueued once dequeued once Therefore: Time  → O(n) Space → O(w) where w is the maximum width of the tree.

21. Queue Problem — Circular Queue

A queue can also be implemented using an array. The challenge is avoiding unnecessary movement of elements. Suppose: [_, _, 3, 4, 5] The queue’s logical beginning might be somewhere in the middle. Instead of shifting everything after a dequeue, maintain: head tail and wrap around using modulo arithmetic: index = (index + 1) % capacity This creates a circular queue.

22. Circular Queue Concept

Imagine: 0 → 1 → 2 → 3 → 4 ↑               ↓ └───────────────┘ When the tail reaches the final slot, it wraps back to zero. This gives: enqueue → O(1) amortized dequeue → O(1) with dynamic resizing when capacity is exhausted. The chapter specifically uses this structure to illustrate efficient queue implementation without repeatedly shifting elements.

23. Queue Using Two Stacks

This is one of the most famous interview problems. Question:

How can we implement a FIFO queue using only LIFO stacks?

Use: enqueue_stack dequeue_stack

24. The Two-Stack Idea

Suppose: enqueue: 1 2 3 4 First stack: [1, 2, 3, 4] To dequeue 1, transfer everything: stack 1              stack 2

4                    1 3                    2 2                    3 1                    4 Now: stack2.pop() returns: 1 The second stack reverses the order.

25. Critical Optimization

A naive implementation transfers elements on every dequeue. That is inefficient. Instead: enqueue → always push into input stack

dequeue:     if output stack is empty:         transfer everything     pop output stack Python: class QueueUsingStacks:     def __init__(self):         self.in_stack = []         self.out_stack = []

    def enqueue(self, x):         self.in_stack.append(x)

    def dequeue(self):         if not self.out_stack:             while self.in_stack:                 self.out_stack.append(                     self.in_stack.pop()                 )

        if not self.out_stack:             raise IndexError(“empty queue”)

        return self.out_stack.pop()

26. Why Is Dequeue Amortized O(1)?

This is a classic interview discussion. Suppose we insert: 1 2 3 4 5 At some point we transfer: 1 2 3 4 5 That costs: O(n) But each element can be transferred only once before it is dequeued. Across m operations: Total work = O(m) Therefore: Amortized cost per operation = O(1) This is a very important Staff-level complexity concept. Don’t simply say:

“There is a while loop, so it’s O(n).”

Ask:

How many times can each element participate in that loop over the lifetime of the data structure?

27. Queue With a Maximum

Now consider: enqueue() dequeue() max() A naive implementation scans the entire queue: max(queue) which costs: O(n) Can we achieve: max() → O(1) Yes—with a monotonic deque.

28. Monotonic Deque Pattern

Suppose we enqueue: 3, 1, 4, 2 Maintain candidates for maximum: 3 Then: 3, 1 Then 4 arrives. Since: 1 < 4 3 < 4 neither can become the future maximum while 4 remains in the queue. So remove them. Deque: 4 Then add: 2 Deque: 4, 2 The maximum is always at the front.

29. The Deque Invariant

The key invariant is:

The deque contains only elements that could still become the maximum, maintained in decreasing order.

When inserting x: while candidates and candidates[-1] < x:     candidates.pop()

candidates.append(x) When removing from the queue: value = queue.popleft()

if candidates and candidates[0] == value:     candidates.popleft() Therefore: enqueue → amortized O(1) dequeue → O(1) max     → O(1) This is a powerful pattern that appears far beyond this chapter.

30. Stack vs Queue: The Interview Decision Tree

When you see a new problem, ask: Does the newest item need to be processed first?              │             YES              ↓            STACK Otherwise: Does the oldest item need to be processed first?              │             YES              ↓            QUEUE For tree traversal: DFS → Stack BFS → Queue For nested matching: Parentheses Expressions Paths Undo        ↓      STACK For ordered processing: Tasks Requests BFS Scheduling        ↓      QUEUE For “next greater/smaller”: Monotonic STACK For sliding-window maximum: Monotonic DEQUE

31. The Patterns You Should Actually Memorize

Don’t memorize nine solutions. Memorize these patterns.

Pattern 1 — LIFO

Most recent unresolved item         ↓       STACK Used for:

  • parentheses
  • RPN
  • paths
  • undo
  • DFS

Pattern 2 — FIFO

Oldest pending item         ↓       QUEUE Used for:

  • BFS
  • scheduling
  • task processing
  • producer/consumer

Pattern 3 — Monotonic Stack

Discard elements that can no longer affect future answers Used for:

  • next greater element
  • visibility
  • skyline
  • histogram
  • temperature problems

Pattern 4 — Monotonic Deque

Maintain only candidates that can still become the answer Used for:

  • sliding-window maximum
  • queue maximum
  • min/max window problems

Pattern 5 — Two Stacks

Stack A → Stack B      reverse        ↓ FIFO behavior Used for:

  • queue implementation
  • expression transformations
  • certain parsing problems

Pattern 6 — Circular Buffer

head  ↓ [ ][ ][ ][ ][ ]              ↑             tail Use modulo arithmetic to avoid shifting elements. Used for:

  • bounded queues
  • streaming systems
  • ring buffers
  • producer/consumer architectures

32. Complexity Cheat Sheet

Operation Stack Queue (deque)
Insert O(1) O(1)
Remove O(1) O(1)
Peek O(1) O(1)
Find maximum O(n) O(n)
Maximum with auxiliary structure O(1) O(1)

Advanced structures:

Problem Pattern Complexity
Valid brackets Stack O(n)
RPN evaluation Stack O(n)
Path normalization Stack O(n)
Sunset buildings Monotonic stack O(n)
Tree level order Queue O(n)
Circular queue Array + indices O(1) amortized
Queue with stacks Two stacks O(1) amortized
Queue with max Monotonic deque O(1) amortized

33. Common Interview Mistakes

Mistake 1 — Using a list as a queue

Avoid: q.pop(0) Prefer: from collections import deque

q.popleft()

Mistake 2 — Ignoring amortized complexity

Two-stack queues are not: O(n) per dequeue if implemented correctly. They are: O(1) amortized

Mistake 3 — Missing the monotonic structure

If you repeatedly compare the current element with many previous elements, ask:

Can I discard some previous elements permanently?

If yes, a monotonic stack/deque may reduce: O(n²) to: O(n)

Mistake 4 — Explaining code without an invariant

Don’t just say:

“I push this value.”

Say:

“The stack contains all unresolved candidates, and they remain ordered according to the invariant.”

That’s a much stronger interview answer.

34. Staff-Level Thinking: Eliminate Dead State

The deepest lesson from this part is not Stack or Queue. It is state elimination. Consider sunset buildings. Naive thinking: Compare current building with every previous building Better thinking: Which previous buildings can never matter again? Then remove them. The same idea appears in: Monotonic stack Monotonic deque Two-stack queue Caching maxima Sliding windows The general principle is:

Don’t preserve information merely because it existed. Preserve only information that can still affect the future.

That is a powerful algorithmic mindset.

35. How This Connects to Real Systems

These aren’t just interview tricks. The same concepts appear in production systems.

Stack

Used conceptually in:

  • call stacks
  • DFS
  • parsing
  • execution engines
  • undo systems

Queue

Used in:

  • distributed workers
  • message brokers
  • task scheduling
  • request processing
  • streaming pipelines

Deque

Useful for:

  • sliding windows
  • caches
  • scheduling
  • work-stealing-style structures

Circular buffer

Used in:

  • network buffers
  • telemetry pipelines
  • streaming systems
  • logging systems
  • high-throughput ingestion

For a Staff Engineer, being able to connect the data structure to system behavior is an important differentiator.

36. Interview Framework for Stack & Queue Problems

When you receive a problem, don’t immediately start coding. Use this sequence: Problem    ↓ Clarify requirements    ↓ Identify ordering    ↓ LIFO or FIFO?    ↓ Can old state be discarded?    ↓ Monotonic structure?    ↓ Define invariant    ↓ Implement    ↓ Test edge cases    ↓ Analyze complexity    ↓ Discuss trade-offs This builds directly on the interview methodology established earlier in the series: understand the problem, identify the pattern, state the invariant, code, test, analyze complexity, and discuss trade-offs.

37. The 10 Questions You Should Be Able to Answer

Before moving to the next part, make sure you can answer these without hesitation:

  1. What is LIFO?
  2. What is FIFO?
  3. When should you use a stack?
  4. When should you use a queue?
  5. Why is deque preferred for Python queues?
  6. How do you evaluate RPN using a stack?
  7. How do you validate nested parentheses?
  8. What is a monotonic stack?
  9. Why is a queue implemented with two stacks O(1) amortized?
  10. How can you maintain a queue maximum in O(1) amortized time?

If you can explain why each solution works—not just reproduce the code—you understand the part.

38. Final Interview Cheat Sheet

If you have only two minutes before an interview, remember this: STACK LIFO ↓ Most recent unresolved item ↓ Parsing Parentheses RPN DFS Path normalization Undo QUEUE FIFO ↓ Oldest pending item ↓ BFS Scheduling Tasks Requests Streaming MONOTONIC STACK ↓ Remove elements that can never matter again ↓ Next greater/smaller Visibility Skyline Histogram MONOTONIC DEQUE ↓ Maintain only future candidates ↓ Sliding-window maximum/minimum Queue max TWO STACKS ↓ Reverse order ↓ Implement FIFO using LIFO ↓ O(1) amortized CIRCULAR QUEUE ↓ Head + Tail + Modulo ↓ Avoid shifting ↓ O(1) operations

The Bigger Lesson From Part 8

Stacks and queues look like basic data structures. But the real lesson is much deeper:

Choose a data structure based on the order in which information matters.

And at the Staff/Principal level, go one step further:

Identify which information can be permanently discarded without affecting future decisions.

That is the idea behind: Stack → Queue → Monotonic Stack → Monotonic Deque → Amortized Algorithms Once you recognize those patterns, many seemingly different coding problems collapse into the same small set of ideas. And that is exactly what you want from a strong coding-interview preparation strategy: Don’t memorize problems. Recognize patterns. State invariants. Eliminate unnecessary work. Prove correctness. Analyze complexity. Explain trade-offs.

Part 8 in the Series

Part 7: Linked Lists ↓ Part 8: Stacks & Queues ↓ Part 9: Binary Trees The progression is deliberate: linked lists teach pointer/state manipulation; stacks and queues teach ordering and controlled state, which becomes essential when we move into tree traversal and graph-style algorithms. Source basis: uploaded Elements of Programming Interviews in Python PDF, Chapter 8, “Stacks and Queues.” The original chapter spans the stack and queue concepts and exercises discussed above.