AI SWE Prep
0/23in Data Structures & Algorithms
Data Structures & Algorithms

Queues & Deques

FIFO processing, the double-ended queue, and the sliding-window-maximum trick that a monotonic deque makes O(n).

~12 minLesson 20 of 60
Your progressNot started

A queue processes work in arrival order: first in, first out. That makes it the natural structure for scheduling, breadth-first search, rate limiting, and any stream where old items expire as new items arrive.

A deque — double-ended queue — is the Python version you actually use. It gives O(1) append and pop at both ends, which matters because a plain list is cheap at the right end but expensive at the left.

The advanced pattern is a monotonic deque. It keeps only the candidates that can still become the maximum or minimum of the current sliding window.

The mental model

Use collections.deque when both ends matter:

from collections import deque

q = deque()
q.append("a")       # push to back
q.append("b")
first = q.popleft() # "a"

For a sliding maximum, the deque stores indices in decreasing value order. The front is always the best answer for the current window. Before adding a new index, remove weaker candidates from the back; before reading the answer, remove indices that fell out of the window.

from collections import deque

def window_max(nums, k):
    dq = deque()
    ans = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            ans.append(nums[dq[0]])
    return ans

The deque holds indices, not values, because you need to know when an item leaves the window.

Queue · circular buffer (FIFO)Step 1 / 11
0
T
1
2
3
4
size 0 / 5
Empty circular buffer, capacity 5. head = tail = 0.
just touchedhead (next out)tail (next in)

Pattern recognition

Variations

Worked problems

These progress from API simulation to the full monotonic-deque pattern.

LeetCode 232Easy
  • Queue
  • Stacks

Implement Queue using Stacks

Build a FIFO queue using only stack operations. It must support pushing to the back, peeking at the front, popping the front, and checking whether it is empty.

Approach. Push new values onto an in_stack. When you need the front, pour in_stack into out_stack only if out_stack is empty. That reversal makes the oldest item land on top, and each element moves between stacks at most once.

Show solution
class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

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

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

    def pop(self):
        self._move_if_needed()
        return self.out_stack.pop()

    def peek(self):
        self._move_if_needed()
        return self.out_stack[-1]

    def empty(self):
        return not self.in_stack and not self.out_stack

Complexity. Amortized O(1) time per operation and O(n) space. A single pop can move many items, but each item is moved only once from in_stack to out_stack.

LeetCode 933Easy
  • Queue
  • Time window

Number of Recent Calls

Design a counter for ping times. Each new ping has timestamp t; return how many pings happened in the inclusive window from t - 3000 to t.

Approach. Timestamps arrive in increasing order, so old pings expire only from the front. Append the new timestamp, then pop from the left while it is too old.

Show solution
from collections import deque

class RecentCounter:
    def __init__(self):
        self.calls = deque()

    def ping(self, t):
        self.calls.append(t)
        while self.calls[0] < t - 3000:
            self.calls.popleft()
        return len(self.calls)

Complexity. Amortized O(1) time per ping and O(w) space, where w is the number of calls in the 3000-millisecond window. Each timestamp is enqueued and dequeued once.

LeetCode 239Hard
  • Monotonic deque
  • Sliding window

Sliding Window Maximum

For every contiguous window of size k, return the maximum value in that window.

Approach. Keep a deque of indices whose values are decreasing from front to back. The front is the maximum. Remove front indices that left the window, and remove back indices whose values are no better than the new value because they can never win a future window.

Show solution
from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    ans = []

    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()

        while dq and nums[dq[-1]] <= x:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            ans.append(nums[dq[0]])

    return ans

Complexity. O(n) time, O(k) space. Each index is inserted once and removed at most once.

When not to use it

Also avoid list.pop(0) in Python for real queues. It shifts the whole list left on every pop, quietly turning linear streams into quadratic work.

Your progressNot started