Overview

A queue serves elements in arrival order: enqueue at the back, dequeue from the front. That makes it the natural structure for anything processed in rounds — breadth-first search explores a graph level by level with a queue, and simulations of waiting lines, task schedulers and rate limiters all use one.

A deque (double-ended queue) allows O(1) pushes and pops at both ends. Its star application is the monotonic deque: keep indices whose values are in decreasing order, drop indices that slide out of the window from the front, and the front is always the window's maximum. Sliding-window maximum goes from O(n·k) to O(n).

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Enqueue / dequeue (deque)O(1)
Python list.pop(0)O(n) — avoid
Sliding window max with dequeO(n) total

Patterns to recognise

Level-by-level processing

Use it for: BFS, level order traversal, rotting oranges.

Record len(queue) at the start of a level and process exactly that many.

Monotonic deque

Use it for: Sliding window maximum/minimum, shortest subarray with sum ≥ k.

Keep the deque sorted; front is the answer for the current window.

Round-based simulation

Use it for: Recent calls counter, Dota2 senate, task scheduling.

Push items back with updated state; pop expired items from the front.

Code template

Sliding window maximum — monotonic deque
from collections import deque


def max_sliding_window(nums, k):
    dq, out = deque(), []            # indices, values decreasing
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                 # smaller values can never be a max again
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()             # front index left the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Common mistakes

  • Using a list as a queue in Python and paying O(n) per dequeue.
  • Forgetting to expire indices that have left the window.
  • Reading the front of an empty queue.

Quick check

Three questions on Queues. Get all three right to earn +15 XP.

  1. Which traversal naturally uses a queue?

  2. Why is list.pop(0) a poor way to dequeue in Python?

  3. In the sliding-window maximum, the monotonic deque keeps:

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Queues?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor