RugvAI Labs

Stacks, Queues & Deque: LIFO and FIFO Mastered

Stacks power Python's own call frames — every time you call a function, you push to a stack. Queues power Celery, RabbitMQ, and every async job system in production. collections.deque shows up constantly in coding interviews, and it's how real systems implement sliding-window rate limiters.

Learning Objectives

After this lesson, you will be able to:

Implement a Stack (LIFO) with push, pop, and peek operations using a list
Implement a Queue (FIFO) using collections.deque for O(1) enqueue and dequeue
Explain why deque is more efficient than list for queue operations
Apply a monotonic stack to solve classic problems like Next Greater Element
Implement a circular queue and a min-stack that tracks minimum in O(1)
Use queue.Queue and queue.PriorityQueue for thread-safe operations

Why

Why This Matters

DFS uses stacks, BFS uses queues. These two fundamental traversal algorithms differ in only one data structure. Swapping a stack for a queue changes the entire search strategy from depth-first to breadth-first
Your browser history is a stack. The back button pops the current page. Undo/redo in editors are two stacks. Function calls use the call stack. Stacks are everywhere in computing
Messaging systems are queues. RabbitMQ, Kafka, and cloud task queues are all FIFO pipelines. Every web server's request handling is a queue. Understanding queues means understanding distributed systems
Monotonic stacks solve O(n²) problems in O(n). Problems like "next greater element" and "trapping rain water" that seem to require nested loops can be solved in a single pass with a monotonic stack

Prerequisites

Before You Start

Review

#Stack (LIFO): Deep Dive

A stack is a collection where the last item added is the first one removed — LIFO: Last In, First Out.

pythonrunnable cell

class Stack:
    """A stack data structure (LIFO)."""

    def __init__(self):
        self._items = []

    def push(self, item):
        """Add an item to the top of the stack. O(1) amortized."""
        self._items.append(item)

    def pop(self):
        """Remove and return the top item. Raises IndexError if empty. O(1)."""
        if self.is_empty():
            raise IndexError("Pop from an empty stack")
        return self._items.pop()

    def peek(self):
        """Return the top item without removing it. O(1)."""
        if self.is_empty():
            raise IndexError("Peek at an empty stack")
        return self._items[-1]

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self._items) == 0

    def size(self):
        """Return the number of items in the stack."""
        return len(self._items)

    def __str__(self):
        return f"Stack(top -> {self._items[::-1]})"


# Using the stack
stack = Stack()
stack.push("A")
stack.push("B")
stack.push("C")

print(stack)           # Stack(top -> ['C', 'B', 'A'])
print(stack.peek())    # C
print(stack.pop())     # C  (removed from top)
print(stack.pop())     # B
print(stack)           # Stack(top -> ['A'])

What Do You Think?

You push A, B, C onto a stack. What's the first element you pop?

The answer is C. A stack follows Last In, First Out (LIFO). Since C was pushed last, it sits on top and is the first to be popped.

#How the Call Stack Works

Every time Python calls a function, it pushes a stack frame onto the call stack. When the function returns, its frame is popped. This is why recursion can cause a RecursionError — too many frames on the stack.

pythonrunnable cell

def factorial(n):
    # Each call pushes a new frame onto the call stack
    print(f"  Calling factorial({n})")
    if n <= 1:
        print(f"  Returning 1 (base case, start unwinding)")
        return 1
    result = n * factorial(n - 1)
    print(f"  Returning {result} for n={n}")
    return result

print(factorial(4))

# Output shows the stack being built, then unwound:
#   Calling factorial(4)   <- push frame 4
#   Calling factorial(3)   <- push frame 3
#   Calling factorial(2)   <- push frame 2
#   Calling factorial(1)   <- push frame 1 (base case)
#   Returning 1 (base case, start unwinding)
#   Returning 2 for n=2    <- pop frame 2
#   Returning 6 for n=3    <- pop frame 3
#   Returning 24 for n=4   <- pop frame 4
# 24

# You can inspect the call stack manually:
import traceback

def show_stack():
    for line in traceback.format_stack():
        print(line.strip())

def inner():
    show_stack()  # prints the current call chain

def outer():
    inner()

outer()

#Application: Balanced Parentheses Checker

The call stack insight directly maps to bracket matching — nested brackets mirror nested function calls.

pythonreference · read-only

def is_balanced(expression):
    """Check if parentheses, brackets, and braces are balanced.
    
    Uses a stack to track opening brackets. When we see a closing
    bracket, we pop from the stack and verify it matches.
    """
    stack = Stack()
    matching = {")": "(", "]": "[", "}": "{"}

    for char in expression:
        if char in "([{":
            stack.push(char)
        elif char in ")]}":
            if stack.is_empty() or stack.pop() != matching[char]:
                return False

    return stack.is_empty()  # must be empty — all brackets closed

print(is_balanced("((a + b) * [c - d])"))   # True
print(is_balanced("((a + b)"))              # False — missing closing
print(is_balanced("([)]"))                  # False — wrong nesting
print(is_balanced("{[()]}"))                # True — correct nesting

#Application: Evaluate Postfix (RPN) Expressions

Postfix notation (Reverse Polish Notation) eliminates parentheses. 3 4 + 2 * means (3 + 4) * 2. Evaluating it requires only a stack:

pythonreference · read-only

def evaluate_rpn(tokens):
    """Evaluate a postfix expression given as a list of tokens.
    
    Algorithm:
    - If token is a number: push it
    - If token is an operator: pop two operands, apply, push result
    """
    stack = Stack()
    operators = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: int(a / b),  # truncate toward zero
    }

    for token in tokens:
        if token in operators:
            b = stack.pop()  # second operand
            a = stack.pop()  # first operand
            stack.push(operators[token](a, b))
        else:
            stack.push(int(token))

    return stack.pop()

# (3 + 4) * 2  =>  3 4 + 2 *
print(evaluate_rpn(["3", "4", "+", "2", "*"]))  # 14

# 5 + ((1 + 2) * 4) - 3  =>  5 1 2 + 4 * + 3 -
print(evaluate_rpn(["5", "1", "2", "+", "4", "*", "+", "3", "-"]))  # 14

#MinStack: O(1) Minimum at Any Time

A classic interview problem: design a stack that supports push, pop, top, and get_min — all in O(1). The trick is a parallel min stack that tracks the running minimum.

pythonrunnable cell

class MinStack:
    """A stack that returns the minimum element in O(1).
    
    Key insight: maintain a parallel stack where each position
    stores the minimum of all elements at or below that position.
    """

    def __init__(self):
        self._stack = []
        self._min_stack = []  # parallel stack tracking minimums

    def push(self, val):
        self._stack.append(val)
        # push current min (maintain invariant: min_stack[-1] is always current min)
        current_min = val if not self._min_stack else min(val, self._min_stack[-1])
        self._min_stack.append(current_min)

    def pop(self):
        self._min_stack.pop()
        return self._stack.pop()

    def top(self):
        return self._stack[-1]

    def get_min(self):
        return self._min_stack[-1]  # O(1)!


ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
ms.push(2)
ms.push(4)

print(ms.get_min())    # 2  (current minimum)
ms.pop()               # remove 4
print(ms.get_min())    # 2  (still 2)
ms.pop()               # remove 2
print(ms.get_min())    # 3  (minimum is now 3)
ms.pop()               # remove 7
print(ms.get_min())    # 3  (still 3)
ms.pop()               # remove 3
print(ms.get_min())    # 5  (only 5 remains)

Figure

MinStack visualized: two parallel stacks side by side. Left stack shows actual values [5, 3, 7, 2, 4]. Right min_stack shows running minimums [5, 3, 3, 2, 2]. As you pop elements from the left, the corresponding min is also removed from the right. The min_stack top always shows the current minimum in O(1).

#Queue (FIFO): Deep Dive

A queue is a collection where the first item added is the first one removed — FIFO: First In, First Out. Think of a line at a ticket counter: first person in line is first to be served.

#Why deque, Not list?

The critical performance question: why use collections.deque instead of a plain list?

pythonrunnable cell

# THE WRONG WAY — list as a queue
bad_queue = []
bad_queue.append("Alice")    # O(1) — fast
bad_queue.append("Bob")      # O(1) — fast
bad_queue.pop(0)             # O(n) — SLOW! Shifts every remaining element left

# THE RIGHT WAY — deque
from collections import deque

good_queue = deque()
good_queue.append("Alice")    # O(1) — fast
good_queue.append("Bob")      # O(1) — fast
good_queue.popleft()          # O(1) — fast! No shifting needed

# Benchmark to see the difference:
import timeit

def list_queue(n):
    q = []
    for i in range(n):
        q.append(i)
    for _ in range(n):
        q.pop(0)  # O(n) each time

def deque_queue(n):
    q = deque()
    for i in range(n):
        q.append(i)
    for _ in range(n):
        q.popleft()  # O(1) each time

n = 10_000
list_time = timeit.timeit(lambda: list_queue(n), number=10)
deque_time = timeit.timeit(lambda: deque_queue(n), number=10)

print(f"List  (n={n}): {list_time:.3f}s")   # e.g. 3.241s
print(f"Deque (n={n}): {deque_time:.3f}s")  # e.g. 0.018s — ~180x faster

#Queue Implementation

pythonrunnable cell

from collections import deque

class Queue:
    """A queue data structure (FIFO) backed by collections.deque."""

    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        """Add an item to the back of the queue. O(1)."""
        self._items.append(item)

    def dequeue(self):
        """Remove and return the front item. Raises IndexError if empty. O(1)."""
        if self.is_empty():
            raise IndexError("Dequeue from an empty queue")
        return self._items.popleft()

    def front(self):
        """Return the front item without removing it. O(1)."""
        if self.is_empty():
            raise IndexError("Front of an empty queue")
        return self._items[0]

    def is_empty(self):
        """Check if the queue is empty."""
        return len(self._items) == 0

    def size(self):
        """Return the number of items in the queue."""
        return len(self._items)

    def __str__(self):
        return f"Queue(front -> {list(self._items)})"


queue = Queue()
queue.enqueue("Alice")
queue.enqueue("Bob")
queue.enqueue("Charlie")

print(queue)             # Queue(front -> ['Alice', 'Bob', 'Charlie'])
print(queue.dequeue())   # Alice (first in, first out)
print(queue.dequeue())   # Bob
print(queue)             # Queue(front -> ['Charlie'])

#Circular Queue

A circular queue uses a fixed-size array with two pointers (front and rear) that wrap around using modulo arithmetic. This avoids wasted space and is the foundation of ring buffers in operating systems and hardware drivers.

pythonrunnable cell

class CircularQueue:
    """Fixed-capacity queue using a circular array.
    
    Uses modulo arithmetic so the rear pointer wraps around
    to the front of the array when it reaches the end.
    Memory: always exactly `capacity` slots — no dynamic resizing.
    """

    def __init__(self, capacity):
        self._data = [None] * capacity
        self._front = 0
        self._rear = -1
        self._size = 0
        self._capacity = capacity

    def enqueue(self, val):
        if self.is_full():
            raise OverflowError("Queue is full")
        self._rear = (self._rear + 1) % self._capacity
        self._data[self._rear] = val
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        val = self._data[self._front]
        self._data[self._front] = None   # help GC
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return val

    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._data[self._front]

    def is_empty(self):
        return self._size == 0

    def is_full(self):
        return self._size == self._capacity

    def __str__(self):
        return f"CircularQueue(data={self._data}, front={self._front}, rear={self._rear})"


cq = CircularQueue(4)
cq.enqueue("A")
cq.enqueue("B")
cq.enqueue("C")
print(cq)            # CircularQueue(data=['A', 'B', 'C', None], front=0, rear=2)
print(cq.dequeue())  # A  — front advances to index 1
cq.enqueue("D")      # rear wraps: (2+1) % 4 = 3
cq.enqueue("E")      # rear wraps: (3+1) % 4 = 0  — wraps to start!
print(cq)            # CircularQueue(data=['E', 'B', 'C', 'D'], front=1, rear=0)

Thread-Safe Queues: the `queue` Module

When multiple threads read from and write to the same queue, you need thread safety. Python's queue module provides this:

pythonrunnable cell

import queue
import threading
import time

# queue.Queue — standard FIFO, thread-safe
# queue.LifoQueue — LIFO (thread-safe stack)
# queue.PriorityQueue — priority-based ordering, thread-safe

# ---- Producer-Consumer Pattern ----
task_queue = queue.Queue(maxsize=5)  # blocks if full

def producer():
    for i in range(8):
        task_queue.put(f"task-{i}")    # blocks if queue is full
        print(f"Produced: task-{i}")
        time.sleep(0.1)
    task_queue.put(None)  # sentinel: signals consumer to stop

def consumer():
    while True:
        item = task_queue.get()        # blocks until item is available
        if item is None:
            break
        print(f"  Consumed: {item}")
        task_queue.task_done()          # signals item processing is done
        time.sleep(0.25)

t1 = threading.Thread(target=producer)
t2 = threading.Thread(target=consumer)
t1.start(); t2.start()
t1.join(); t2.join()

# ---- PriorityQueue ----
pq = queue.PriorityQueue()
pq.put((3, "low priority task"))    # (priority, item) — lower number = higher priority
pq.put((1, "critical task"))
pq.put((2, "medium priority task"))

while not pq.empty():
    priority, task = pq.get()
    print(f"[P{priority}] {task}")
# [P1] critical task
# [P2] medium priority task
# [P3] low priority task

#deque: The Swiss Army Knife

collections.deque (pronounced "deck") is a double-ended queue — O(1) operations at both ends. It is not just a queue implementation detail; it is a first-class data structure with unique capabilities.

pythonrunnable cell

from collections import deque

d = deque([1, 2, 3, 4, 5])

# All four endpoint operations are O(1)
d.append(6)       # add to right:  [1, 2, 3, 4, 5, 6]
d.appendleft(0)   # add to left:   [0, 1, 2, 3, 4, 5, 6]
d.pop()           # remove right:  [0, 1, 2, 3, 4, 5]
d.popleft()       # remove left:   [1, 2, 3, 4, 5]

print(d)  # deque([1, 2, 3, 4, 5])

# rotate(n): move n elements from right to left (positive n)
#            or left to right (negative n)
d.rotate(2)
print(d)  # deque([4, 5, 1, 2, 3])

d.rotate(-2)
print(d)  # deque([1, 2, 3, 4, 5])  — back to original

#maxlen: Automatic Sliding Window

The maxlen parameter caps the deque size. When full, adding to one end automatically discards from the other. This is the perfect building block for sliding windows and recent-history buffers.

pythonrunnable cell

from collections import deque

# Sliding window: track last 5 sensor readings
window = deque(maxlen=5)

sensor_readings = [12, 15, 14, 18, 20, 22, 19, 25, 23, 21]

for reading in sensor_readings:
    window.append(reading)
    avg = sum(window) / len(window)
    print(f"Reading: {reading:2d}  |  Window: {list(window)}  |  Avg: {avg:.1f}")

# Reading: 12  |  Window: [12]                  |  Avg: 12.0
# Reading: 15  |  Window: [12, 15]              |  Avg: 13.5
# Reading: 14  |  Window: [12, 15, 14]          |  Avg: 13.7
# Reading: 18  |  Window: [12, 15, 14, 18]      |  Avg: 14.8
# Reading: 20  |  Window: [12, 15, 14, 18, 20]  |  Avg: 15.8
# Reading: 22  |  Window: [15, 14, 18, 20, 22]  |  Avg: 17.8  <- 12 auto-discarded
# Reading: 19  |  Window: [14, 18, 20, 22, 19]  |  Avg: 18.6


# Browser history buffer: remember last 10 pages
history = deque(maxlen=10)

def visit(url):
    history.append(url)
    print(f"Visited: {url}")
    print(f"  History: {list(history)}")

def back():
    if len(history) > 1:
        history.pop()  # remove current
        print(f"  Back to: {history[-1]}")

visit("google.com")
visit("python.org")
visit("docs.python.org/deque")
back()
# Back to: python.org

#deque vs list: Performance Comparison

pythonrunnable cell

from collections import deque
import timeit

n = 100_000

# Prepending to a list: O(n) — shifts all elements
list_prepend = timeit.timeit(
    lambda: [0] + list(range(n)),  # creates new list
    number=100
)

# Prepending to a deque: O(1)
deque_prepend = timeit.timeit(
    lambda: deque([0], maxlen=n+1),
    number=100
)

print(f"List prepend:  {list_prepend:.3f}s")    # ~2.1s
print(f"Deque prepend: {deque_prepend:.3f}s")   # ~0.01s

# Summary table of complexities:
#
# Operation          | list   | deque
# -------------------|--------|-------
# append (right)     | O(1)*  | O(1)
# pop (right)        | O(1)   | O(1)
# appendleft (left)  | O(n)   | O(1)
# popleft (left)     | O(n)   | O(1)
# Index access [i]   | O(1)   | O(n)
# len()              | O(1)   | O(1)
#
# * amortized — occasional resizes are O(n)
# Rule: use list when you need fast random access (list[i]),
#       use deque when you need fast both-end operations.

#Monotonic Stack: Advanced Pattern

A monotonic stack is a stack where elements are maintained in either strictly increasing or strictly decreasing order. When a new element violates the order, we pop elements until the order is restored. This single-pass technique converts many O(n²) problems into O(n).

#Next Greater Element: O(n) with Monotonic Stack

pythonrunnable cell

def next_greater_element(nums):
    """For each element, find the next element that is greater.
    Returns -1 if no greater element exists.
    
    Naive O(n²): for each element, scan right until finding greater.
    Monotonic stack O(n): single pass.
    
    We maintain a decreasing stack of indices.
    When nums[i] > nums[stack top], the top has found its answer.
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # indices of elements waiting for their "next greater"

    for i in range(n):
        # Pop all elements that have found their next greater element
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]  # nums[i] is the next greater for idx
        stack.append(i)

    # Any index still in the stack has no greater element -> stays -1
    return result


nums = [2, 1, 2, 4, 3, 1, 5, 2]
print(next_greater_element(nums))
# [4, 2, 4, 5, 5, 5, -1, -1]
#  ^  ^  ^  ^  ^  ^   ^   ^
#  |  |  |  |  |  |   no greater element
#  2's NGE=4, 1's NGE=2, 4's NGE=5, ...

# Trace through the first few steps:
# i=0, nums[0]=2:  stack empty -> push 0.         stack=[0]
# i=1, nums[1]=1:  1 < 2 -> push 1.              stack=[0, 1]
# i=2, nums[2]=2:  2 > nums[1]=1 -> pop 1, result[1]=2; 2=nums[0]=2 -> push 2.  stack=[0, 2]
# i=3, nums[3]=4:  4 > nums[2]=2 -> pop 2, result[2]=4; 4 > nums[0]=2 -> pop 0, result[0]=4; push 3. stack=[3]

#Daily Temperatures

Given a list of daily temperatures, find for each day how many days until a warmer temperature. Return 0 if there is no future warmer day.

pythonrunnable cell

def daily_temperatures(temps):
    """Find number of days to wait for a warmer temperature.
    
    Uses a monotonic decreasing stack of indices.
    When we find a warmer day, resolve all colder waiting days.
    """
    n = len(temps)
    result = [0] * n
    stack = []  # indices of days waiting for a warmer day

    for i in range(n):
        while stack and temps[i] > temps[stack[-1]]:
            prev = stack.pop()
            result[prev] = i - prev  # days waited = current index - past index
        stack.append(i)

    return result

temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]
# Day 0 (73°): wait 1 day (day 1 is 74°)
# Day 2 (75°): wait 4 days (day 6 is 76°)
# Day 6 (76°): no warmer day -> 0

#Largest Rectangle in Histogram

The classic hard problem — find the largest rectangle that fits within a histogram. A monotonic stack makes this O(n):

pythonrunnable cell

def largest_rectangle(heights):
    """Find the largest rectangle area in a histogram.
    
    Strategy: use a monotonic increasing stack.
    When we encounter a bar shorter than the stack top, we know
    the stack top bar cannot extend further right. Calculate its area.
    
    Time: O(n)  Space: O(n)
    """
    stack = []  # indices — maintains increasing heights
    max_area = 0
    heights = heights + [0]  # sentinel: forces all remaining bars to be processed

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # width: from current i to the new stack top (or start if stack empty)
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

#  histogram:  [2, 1, 5, 6, 2, 3]
#               _
#              | |
#         _    | |_
#        | |   | | |_
#    _   | |   | | | |
#   | |  | |   | | | |
#   [2,  1,  5,  6,  2,  3]
#                       largest rectangle = 10 (height=2, width=5, indices 1-5)

print(largest_rectangle([2, 1, 5, 6, 2, 3]))  # 10
print(largest_rectangle([2, 4]))               # 4

#Real-World Applications Showcase

pythonrunnable cell

# ============================================================
# 1. Undo / Redo System using Two Stacks
# ============================================================

class TextEditor:
    """Simple text editor with undo/redo using two stacks.
    
    undo_stack: history of previous states
    redo_stack: states undone (cleared on new action)
    """

    def __init__(self):
        self.text = ""
        self.undo_stack = []
        self.redo_stack = []

    def type(self, chars):
        self.undo_stack.append(self.text)
        self.redo_stack.clear()  # new action clears redo history
        self.text += chars

    def undo(self):
        if self.undo_stack:
            self.redo_stack.append(self.text)
            self.text = self.undo_stack.pop()

    def redo(self):
        if self.redo_stack:
            self.undo_stack.append(self.text)
            self.text = self.redo_stack.pop()

    def __str__(self):
        return f'TextEditor("{self.text}")'


editor = TextEditor()
editor.type("Hello")
editor.type(", World")
print(editor)        # TextEditor("Hello, World")
editor.undo()
print(editor)        # TextEditor("Hello")
editor.undo()
print(editor)        # TextEditor("")
editor.redo()
print(editor)        # TextEditor("Hello")

pythonrunnable cell

# ============================================================
# 2. Rate Limiter using deque (Sliding Window Counter)
# ============================================================

from collections import deque
import time

class RateLimiter:
    """Sliding window rate limiter using a deque of timestamps.
    
    Allows at most `max_requests` requests within any `window_seconds`
    rolling window. Uses a deque to efficiently expire old timestamps.
    """

    def __init__(self, max_requests, window_seconds):
        self.max_requests = max_requests
        self.window = window_seconds
        self.requests = deque()  # timestamps of recent requests

    def is_allowed(self):
        now = time.time()
        # Remove expired timestamps (older than the window)
        while self.requests and now - self.requests[0] > self.window:
            self.requests.popleft()

        if len(self.requests) < self.max_requests:
            self.requests.append(now)
            return True
        return False  # rate limit exceeded


# Allow 3 requests per second
limiter = RateLimiter(max_requests=3, window_seconds=1.0)

for i in range(6):
    allowed = limiter.is_allowed()
    print(f"Request {i+1}: {'ALLOWED' if allowed else 'BLOCKED'}")
    time.sleep(0.2)

# Request 1: ALLOWED
# Request 2: ALLOWED
# Request 3: ALLOWED
# Request 4: BLOCKED  <- 3 requests happened within last 1s
# Request 5: ALLOWED  <- first request (t=0) has now expired
# Request 6: ALLOWED

pythonrunnable cell

# ============================================================
# 3. BFS for Shortest Path (Queue Application)
# ============================================================

from collections import deque

def shortest_path(graph, start, end):
    """Find shortest path between two nodes using BFS.
    
    BFS guarantees the shortest path in an unweighted graph because
    it explores nodes in order of increasing distance from the start.
    A stack (DFS) would find A path, but not necessarily the shortest.
    """
    if start == end:
        return [start]

    queue = deque([(start, [start])])  # (current_node, path_so_far)
    visited = {start}

    while queue:
        node, path = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == end:
                    return new_path
                visited.add(neighbor)
                queue.append((neighbor, new_path))

    return None  # no path found


graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(shortest_path(graph, "A", "F"))   # ['A', 'C', 'F']
print(shortest_path(graph, "D", "F"))   # ['D', 'B', 'E', 'F']

Build and Explore Data StructuresInteractive

Switch between Stack, Queue, and other modes. Insert values and watch the structure update in real time.

Loading visualization...

#Code Playground

pythonplayground.py · Pyodide

# MinStack and Monotonic Stack — explore advanced patterns
from collections import deque

# ---- MinStack ----
class MinStack:
  """Stack that returns the minimum element in O(1)."""
  def __init__(self):
      self._stack = []
      self._min_stack = []

def push(self, val: int) -> None:
      self._stack.append(val)
      current_min = val if not self._min_stack else min(val, self._min_stack[-1])
      self._min_stack.append(current_min)

def pop(self) -> int:
      self._min_stack.pop()
      return self._stack.pop()

def top(self) -> int:
      return self._stack[-1]

def get_min(self) -> int:
      return self._min_stack[-1]  # O(1)

# Test MinStack
ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
ms.push(2)
print(f"Min: {ms.get_min()}")    # 2
ms.pop()
print(f"Min: {ms.get_min()}")    # 3
ms.pop()
print(f"Min: {ms.get_min()}")    # 3
ms.pop()
print(f"Min: {ms.get_min()}")    # 5

print()

# ---- Monotonic Stack: Next Greater Element ----
def next_greater_element(nums):
  n = len(nums)
  result = [-1] * n
  stack = []
  for i in range(n):
      while stack and nums[i] > nums[stack[-1]]:
          idx = stack.pop()
          result[idx] = nums[i]
      stack.append(i)
  return result

print(next_greater_element([2, 1, 2, 4, 3, 1, 5, 2]))
# [4, 2, 4, 5, 5, 5, -1, -1]

# CHALLENGES:
# 1. Implement daily_temperatures(temps) using a monotonic stack
#    Input:  [73, 74, 75, 71, 69, 72, 76, 73]
#    Output: [1, 1, 4, 2, 1, 1, 0, 0]
#
# 2. Implement a TextEditor class with type(), undo(), redo()
#    using two stacks
#
# 3. Implement is_balanced(expression) to check if brackets are
#    balanced, handling (, ), [, ], {, }
#
# 4. Use a deque with maxlen=3 to build a "last 3 visited pages"
#    history tracker

Tests · Explore stacks, monotonic patterns, and deque!

Watch Out

Common Mistake

Using a plain list as a queue (calling list.pop(0) for dequeue)

pythonrunnable cell

# WRONG — O(n) per dequeue operation
queue = []
queue.append("Alice")
queue.append("Bob")
queue.pop(0)  # shifts every remaining element left — O(n)!

# RIGHT — O(1) per dequeue operation
from collections import deque
queue = deque()
queue.append("Alice")
queue.append("Bob")
queue.popleft()  # just advances a pointer — O(1)

For n=100,000 items, list.pop(0) in a loop is ~180x slower than deque.popleft(). This is one of the most common performance bugs in Python interview code and production code alike. If you need FIFO semantics, always use collections.deque or queue.Queue.

Watch Out

Watch out

Fix: BFS (Breadth-First Search) requires a FIFO queue: deque.append() to enqueue, deque.popleft() to dequeue. DFS (Depth-First Search) requires a LIFO stack: list.append() to push, list.pop() to pop. Swapping them changes your traversal from level-order to depth-first (or vice versa) with no error message.

Accidentally using a stack (list) when a queue (deque) is needed for BFS, or vice versa — swapping the data structure accidentally changes the entire traversal order

This bug is silent — both versions run without exceptions but produce completely different results. Using a stack for BFS gives you DFS behavior. Using a queue for DFS gives you BFS behavior. In graph traversal, shortest-path BFS relies on FIFO order: you must finish all nodes at distance k before exploring distance k+1. A stack breaks this guarantee.

```python from collections import deque

graph = {0: [1, 2], 1: [3], 2: [4], 3: [], 4: []}

BFS — correct: deque + popleft() visits level by level

def bfs(start): queue = deque([start]) visited = set() order = [] while queue: node = queue.popleft() # FIFO: oldest node first if node not in visited: visited.add(node) order.append(node) queue.extend(graph[node]) return order

DFS — correct: list + pop() goes deep first

def dfs(start): stack = [start] visited = set() order = [] while stack: node = stack.pop() # LIFO: newest node first if node not in visited: visited.add(node) order.append(node) stack.extend(graph[node]) return order

print("BFS order:", bfs(0)) # [0, 1, 2, 3, 4] (level by level) print("DFS order:", dfs(0)) # [0, 2, 4, 1, 3] (goes deep first) ```

Mnemonic: Breadth = Big deque (queue). Depth = Down into a stack.

#Key Takeaways

A stack is LIFO. Push adds to the top, pop removes from the top. Python's function call stack, undo/redo systems, bracket matching, and DFS all rely on this structure
A queue is FIFO. Enqueue adds to the back, dequeue removes from the front. Always use collections.deque, never list.pop(0), for O(1) dequeue
Circular queues use modulo arithmetic to wrap pointers in a fixed array — the foundation of ring buffers in OS kernels and hardware drivers
collections.deque supports O(1) operations at both ends. The maxlen parameter makes it the perfect sliding window and history buffer. Use deque for queues, list for random access
Monotonic stacks solve "next greater/smaller element" style problems in O(n) instead of O(n²) by maintaining elements in sorted order and resolving waiting elements on each new arrival
queue.Queue / queue.PriorityQueue add thread-safety for producer-consumer patterns in multithreaded programs

Quick Check1 / 5

You push the values 5, 3, 7, 2 onto a MinStack (in that order). What does get_min() return?

Your Reflection

Continue Learning

Discussion

Stacks, Queues & Deque: LIFO and FIFO Mastered

After this lesson, you will be able to:

Before You Start

#Stack (LIFO): Deep Dive

#How the Call Stack Works

#Application: Balanced Parentheses Checker

#Application: Evaluate Postfix (RPN) Expressions

#MinStack: O(1) Minimum at Any Time

#Queue (FIFO): Deep Dive

#Why deque, Not list?

#Queue Implementation

#Circular Queue

Thread-Safe Queues: the `queue` Module

#deque: The Swiss Army Knife

#maxlen: Automatic Sliding Window

#deque vs list: Performance Comparison

#Monotonic Stack: Advanced Pattern

#Next Greater Element: O(n) with Monotonic Stack

#Daily Temperatures

#Largest Rectangle in Histogram

#Real-World Applications Showcase

#Code Playground

How deque is Implemented in CPython

#Key Takeaways

Your Reflection

Continue Learning

Discussion

Stacks, Queues & Deque: LIFO and FIFO Mastered

#Stack (LIFO): Deep Dive

#How the Call Stack Works

#Application: Balanced Parentheses Checker

#Application: Evaluate Postfix (RPN) Expressions

#MinStack: O(1) Minimum at Any Time

#Queue (FIFO): Deep Dive

#Why deque, Not list?

#Queue Implementation

#Circular Queue

Thread-Safe Queues: the queue Module

#deque: The Swiss Army Knife

#maxlen: Automatic Sliding Window

#deque vs list: Performance Comparison

#Monotonic Stack: Advanced Pattern

#Next Greater Element: O(n) with Monotonic Stack

#Daily Temperatures

#Largest Rectangle in Histogram

#Real-World Applications Showcase

#Code Playground

How deque is Implemented in CPython

#Key Takeaways

Thread-Safe Queues: the `queue` Module