Queues are one of the most versatile data structures in algorithm problems. This page collects ready-to-use C++ templates for every queue variant you’ll encounter on LeetCode — from the basic FIFO queue used in BFS to monotonic queues, priority queues, and deques. Each section includes the template code and a curated problem list so you can practice immediately.

See also Graph and Data Structures (monotonic queue).

Queue = First-In-First-Out (FIFO). Use a queue whenever you need to process elements in the order they arrived — most commonly in BFS. A deque (double-ended queue) lets you push/pop from both ends.

Queue (FIFO) front → 1 2 3 ← back push → back | pop → front | BFS uses queue Deque (both ends) front → 5 3 1 ← back push_front / push_back | sliding window, 0-1 BFS Monotonic Queue — sliding window max for [1,3,-1,-3,5,3,6,7], k=3 13-1-35367 Deque keeps indices in decreasing order → front always has window maximum Output: [3, 3, 5, 5, 6, 7]

Contents

Basic Queue Operations

When to use: any problem requiring FIFO ordering, or when implementing a queue from scratch (e.g., using two stacks).

from collections import deque

# Standard deque as FIFO queue
q: deque[int] = deque()
q.append(1)  # enqueue (back)
q[0]  # peek front
q[-1]  # peek back
q.popleft()  # dequeue from front
not q  # empty check
len(q)

Implement Queue using Stacks

class MyQueue:
    def __init__(self) -> None:
        self._in: list[int] = []
        self._out: list[int] = []

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

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

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

    def empty(self) -> bool:
        return not self._in and not self._out
ID Title Link Solution
232 Implement Queue using Stacks Link -

BFS with Queue

When to use: “shortest path in unweighted graph”, “level order traversal”, “minimum steps”, or any problem that explores neighbors layer by layer.

Queue is essential for Breadth-First Search (level-order traversal).

from collections import deque


class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def bfs_graph(graph: list[list[int]], start: int) -> None:
    q: deque[int] = deque([start])
    visited = [False] * len(graph)
    visited[start] = True
    while q:
        node = q.popleft()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                q.append(neighbor)


def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    result: list[list[int]] = []
    q: deque[TreeNode] = deque([root])
    while q:
        level: list[int] = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)
    return result
ID Title Link Solution
102 Binary Tree Level Order Traversal Link -
107 Binary Tree Level Order Traversal II Link -

Monotonic Queue

When to use: “sliding window maximum/minimum”, or when you need the max/min of every window of size k in O(n) total.

Maintain queue with monotonic property (increasing or decreasing).

from collections import deque


class MonotonicQueue:
    """Decreasing deque of values (max at left)."""

    def __init__(self) -> None:
        self.dq: deque[int] = deque()

    def push(self, val: int) -> None:
        while self.dq and self.dq[-1] < val:
            self.dq.pop()
        self.dq.append(val)

    def pop(self, val: int) -> None:
        if self.dq and self.dq[0] == val:
            self.dq.popleft()

    def max_val(self) -> int:
        return self.dq[0]


def max_sliding_window(nums: list[int], k: int) -> list[int]:
    mq = MonotonicQueue()
    out: list[int] = []
    for i, x in enumerate(nums):
        mq.push(x)
        if i >= k - 1:
            out.append(mq.max_val())
            mq.pop(nums[i - k + 1])
    return out
ID Title Link Solution
239 Sliding Window Maximum Link Solution
1438 Longest Continuous Subarray With Absolute Diff <= Limit Link -

Priority Queue

When to use: “k-th largest/smallest”, “merge k sorted lists”, “top k elements”, “schedule tasks by priority”, or any problem needing efficient access to the current extreme value.

Priority queue (heap) for maintaining order.

import heapq

# Min-heap (default): heapq is a min-heap on the first element of tuples
pq: list[tuple[int, int]] = []
heapq.heappush(pq, (dist, node_id))

# Max-heap trick: store negated keys
heapq.heappush(pq, (-priority, item))

# Custom order: push tuples; Python compares lexicographically
heapq.heappush(pq, (secondary_key, primary_key, payload))

K-way Merge

import heapq


class ListNode:
    def __init__(self, val: int = 0, next=None):
        self.val = val
        self.next = next


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap: list[tuple[int, int, ListNode]] = []
    for i, h in enumerate(lists):
        if h:
            heapq.heappush(heap, (h.val, i, h))
    dummy = ListNode(0)
    cur = dummy
    while heap:
        _, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Top K Elements

import heapq
from collections import Counter


def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    heap: list[tuple[int, int]] = []
    for num, c in freq.items():
        heapq.heappush(heap, (c, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for _, num in heap]
ID Title Link Solution
23 Merge k Sorted Lists Link -
347 Top K Frequent Elements Link Solution
295 Find Median from Data Stream Link -
215 Kth Largest Element in an Array Link -
973 K Closest Points to Origin Link -
253 Meeting Rooms II Link Solution
378 Kth Smallest Element in a Sorted Matrix Link -
703 Kth Largest Element in a Stream Link -
767 Reorganize String Link -
1046 Last Stone Weight Link -
1167 Minimum Cost to Connect Sticks Link -
621 Task Scheduler Link -
743 Network Delay Time Link -
787 Cheapest Flights Within K Stops Link -

Circular Queue

When to use: “design a circular buffer”, “design a queue with fixed capacity”, or when you need wrap-around behavior with modulo arithmetic.

class MyCircularQueue:
    def __init__(self, k: int) -> None:
        self.data = [0] * k
        self.head = 0
        self.tail = 0
        self.size = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.tail] = value
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        return -1 if self.isEmpty() else self.data[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.tail - 1 + self.capacity) % self.capacity]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity
ID Title Link Solution
622 Design Circular Queue Link -

Double-ended Queue (Deque)

When to use: “sliding window” problems where you need to push/pop from both front and back, or when maintaining sorted order in a window by index.

from collections import deque

dq: deque[int] = deque()
dq.appendleft(1)  # add front
dq.append(2)  # add back
dq.popleft()  # remove front
dq.pop()  # remove back
dq[0]
dq[-1]

Sliding Window with Deque

from collections import deque


def max_sliding_window_deque(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    out: list[int] = []
    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:
            out.append(nums[dq[0]])
    return out

Two Deques Pattern (Middle Element Access)

Use two deques to efficiently access middle elements in a queue.

from collections import deque


class FrontMiddleBackQueue:
    def __init__(self) -> None:
        self.front: deque[int] = deque()
        self.back: deque[int] = deque()

    def _rebalance(self) -> None:
        while len(self.front) > len(self.back):
            self.back.appendleft(self.front.pop())
        while len(self.back) > len(self.front) + 1:
            self.front.append(self.back.popleft())

    def pushMiddle(self, val: int) -> None:
        self.front.append(val)
        self._rebalance()

    def popMiddle(self) -> int:
        if not self.front and not self.back:
            return -1
        if len(self.front) == len(self.back):
            return self.front.pop()
        return self.back.popleft()

Key points:

  • Split queue into two halves: front_cache and back_cache
  • Maintain balance: front_cache.size() <= back_cache.size() <= front_cache.size() + 1
  • Middle element is front_cache.back() (if sizes equal) or back_cache.front() (if back_cache larger)
  • Rebalance after each modification
ID Title Link Solution
239 Sliding Window Maximum Link Solution
1670 Design Front Middle Back Queue Link Solution

Summary

Pattern Signal Phrases Key Idea
BFS Queue “shortest path”, “level order” Process nodes level by level
Monotonic Queue “sliding window max/min” Maintain decreasing/increasing order
Priority Queue “k-th largest”, “merge k sorted” Auto-sorted by priority
Circular Queue “circular buffer”, “design queue” Wrap-around with modulo
Deque “sliding window”, “both ends” Push/pop from front and back

More templates