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).

#include <queue>

// Standard queue operations
queue<int> q;
q.push(1);        // Enqueue
q.front();        // Peek front
q.back();         // Peek back
q.pop();          // Dequeue
q.empty();        // Check if empty
q.size();         // Get size

Implement Queue using Stacks

class MyQueue {
    stack<int> input, output;
public:
    void push(int x) {
        input.push(x);
    }
    
    int pop() {
        peek();
        int val = output.top();
        output.pop();
        return val;
    }
    
    int peek() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        return output.top();
    }
    
    bool empty() {
        return input.empty() && output.empty();
    }
};
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).

// BFS on graph
void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        // Process node
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

// Level-order traversal (BFS on tree)
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        result.push_back(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).

// Monotonic decreasing queue (for sliding window maximum)
class MonotonicQueue {
    deque<int> dq;
public:
    void push(int val) {
        // Remove elements smaller than val
        while (!dq.empty() && dq.back() < val) {
            dq.pop_back();
        }
        dq.push_back(val);
    }
    
    void pop(int val) {
        if (!dq.empty() && dq.front() == val) {
            dq.pop_front();
        }
    }
    
    int max() {
        return dq.front();
    }
};

// Sliding Window Maximum
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    MonotonicQueue mq;
    vector<int> result;
    
    for (int i = 0; i < nums.size(); ++i) {
        if (i < k - 1) {
            mq.push(nums[i]);
        } else {
            mq.push(nums[i]);
            result.push_back(mq.max());
            mq.pop(nums[i - k + 1]);
        }
    }
    
    return result;
}
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.

#include <queue>
#include <vector>

// Max heap (default)
priority_queue<int> maxHeap;

// Min heap
priority_queue<int, vector<int>, greater<int>> minHeap;

// Custom comparator using struct
struct Compare {
    bool operator()(pair<int, int>& a, pair<int, int>& b) {
        return a.second > b.second; // Min heap by second element
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

// Custom comparator using lambda operator
auto cmp = [](pair<int, int>& a, pair<int, int>& b) {
    return a.second > b.second; // Min heap by second element
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

// Lambda example: Min heap by distance (for Dijkstra's algorithm)
auto distCmp = [](pair<int, int>& a, pair<int, int>& b) {
    return a.first > b.first; // {distance, node} - min heap by distance
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(distCmp)> pq(distCmp);

K-way Merge

// Merge k sorted lists using priority queue
ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    
    for (ListNode* list : lists) {
        if (list) pq.push(list);
    }
    
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    
    while (!pq.empty()) {
        ListNode* node = pq.top();
        pq.pop();
        cur->next = node;
        cur = cur->next;
        if (node->next) pq.push(node->next);
    }
    
    return dummy->next;
}

Top K Elements

// Find top k frequent elements
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) freq[num]++;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for (auto& [num, count] : freq) {
        pq.push({count, num});
        if (pq.size() > k) pq.pop();
    }
    
    vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top().second);
        pq.pop();
    }
    
    return result;
}
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 {
    vector<int> data;
    int head, tail, size, capacity;
public:
    MyCircularQueue(int k) : data(k), head(0), tail(0), size(0), capacity(k) {}
    
    bool enQueue(int value) {
        if (isFull()) return false;
        data[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % capacity;
        size--;
        return true;
    }
    
    int Front() {
        return isEmpty() ? -1 : data[head];
    }
    
    int Rear() {
        return isEmpty() ? -1 : data[(tail - 1 + capacity) % capacity];
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == 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.

#include <deque>

deque<int> dq;
dq.push_front(1);  // Add to front
dq.push_back(2);   // Add to back
dq.pop_front();     // Remove from front
dq.pop_back();      // Remove from back
dq.front();         // Access front
dq.back();          // Access back

Sliding Window with Deque

// Sliding window maximum using deque
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;
    
    for (int i = 0; i < nums.size(); ++i) {
        // Remove indices outside window
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        
        // Remove indices with smaller values
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

Two Deques Pattern (Middle Element Access)

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

// Front Middle Back Queue: Two deques with rebalancing
class FrontMiddleBackQueue {
    deque<int> front_cache, back_cache;
    
    void rebalance() {
        // Maintain: front_cache.size() <= back_cache.size() <= front_cache.size() + 1
        while(front_cache.size() > back_cache.size()) {
            back_cache.push_front(front_cache.back());
            front_cache.pop_back();
        }
        while(back_cache.size() > front_cache.size() + 1) {
            front_cache.push_back(back_cache.front());
            back_cache.pop_front();
        }
    }
    
public:
    void pushMiddle(int val) {
        front_cache.push_back(val);
        rebalance();
    }
    
    int popMiddle() {
        if(front_cache.empty() && back_cache.empty()) return -1;
        if(front_cache.size() == back_cache.size()) {
            int val = front_cache.back();
            front_cache.pop_back();
            return val;
        } else {
            int val = back_cache.front();
            back_cache.pop_front();
            return val;
        }
    }
};

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