Queues & Deques

#include <queue>
 
queue<int> q;
 
// --- Enqueue (add to back) ---
q.push(10);
q.push(20);
q.push(30);
q.emplace(40);    // Construct in-place
 
// --- Dequeue (remove from front) ---
q.pop();          // Removes front element (returns void)
 
// --- Access ---
cout << q.front();  // 20 — element at front (next to be removed)
cout << q.back();   // 40 — element at back (most recently added)
cout << q.size();   // 3
cout << q.empty();  // false
 
// Warning: Always check empty() before front(), back(), or pop()!
while (!q.empty()) {
    cout << q.front() << " ";
    q.pop();
}
// Output: 20 30 40

#include <deque>
 
deque<int> dq;
 
// --- Front operations ---
dq.push_front(1);    // [1]
dq.push_front(0);    // [0, 1]
 
// --- Back operations ---
dq.push_back(2);     // [0, 1, 2]
dq.push_back(3);     // [0, 1, 2, 3]
 
// --- Remove ---
dq.pop_front();      // [1, 2, 3]
dq.pop_back();       // [1, 2]
 
// --- Access ---
cout << dq.front();  // 1
cout << dq.back();   // 2
cout << dq[0];       // 1 — O(1) random access (but slightly slower than vector)
cout << dq.size();   // 2

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;   // Stores indices; values in dq are decreasing (front = max)
    vector<int> result;
    int n = nums.size();
 
    for (int i = 0; i < n; i++) {
        // 1. Remove indices that are out of the current window [i-k+1, i]
        while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
 
        // 2. Remove indices from back whose values are <= nums[i]
        //    (they are useless — nums[i] is newer and at least as large)
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
 
        dq.push_back(i);
 
        // 3. Record result once the first full window is formed
        if (i >= k - 1) result.push_back(nums[dq.front()]);
    }
    return result;
}
// Time: O(n) — each index is pushed once and popped at most once
// Space: O(k) — deque holds at most k indices
 
/*
  nums=[1,3,-1,-3,5,3,6,7], k=3
  i=0: dq=[0]          (val=1)
  i=1: pop 0 (1<=3), dq=[1]    (val=3)
  i=2: dq=[1,2]        (val=3,3is>=−1). Window complete: max=nums[1]=3 ✓
  i=3: dq=[1,2,3]      (-3 smallest). Front=1 still in [1,3]. max=nums[1]=3 ✓
  i=4: pop 3(-3<=5), pop 2(-1<=5), pop 1(3<=5). dq=[4]. Front=4 in [2,4]. max=5 ✓
  i=5: dq=[4,5]        (3<5). Front=4 in [3,5]. max=nums[4]=5 ✓
  i=6: pop 5(3<=6), dq=[4,6]. Front=4 in [4,6]. max=nums[4]... wait 4 < 6-3+1=4
       4 is at boundary, 4 >= 4 so still in window. max=nums[4]=5? No...
       Actually i=6, window=[4,5,6], front=4 is in window. max=nums[4]=5? But 6 is there!
       Let me re-trace: after popping 5 (nums[5]=3 <= nums[6]=6), dq=[4,6].
       Then pop 4 (nums[4]=5 <= 6), dq=[6]. max=nums[6]=6 ✓
  i=7: dq=[6,7] (nums[7]=7>nums[6]=6, but 6<=7 so pop 6). dq=[7]. max=7 ✓
  Result: [3,3,5,5,6,7] ✓
*/

// Change only the comparison direction in step 2
while (!dq.empty() && nums[dq.back()] >= nums[i]) dq.pop_back();
// Now dq front = minimum of window

// dp[i] = max score to reach index i
// dp[i] = nums[i] + max(dp[i-k], dp[i-k+1], ..., dp[i-1])
int maxResult(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
 
    deque<int> dq;   // Indices; dp values decreasing (front = max dp in window)
    dq.push_back(0);
 
    for (int i = 1; i < n; i++) {
        // Remove out-of-window indices from front
        while (!dq.empty() && dq.front() < i - k) dq.pop_front();
 
        // dp[i] = nums[i] + max dp in window
        dp[i] = nums[i] + dp[dq.front()];
 
        // Remove indices with dp value <= dp[i] from back
        while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
        dq.push_back(i);
    }
    return dp[n - 1];
}
// Time: O(n), Space: O(n)

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 val) {
        if (isFull()) return false;
        data[tail] = val;
        tail = (tail + 1) % capacity;   // Wrap around
        size++;
        return true;
    }
 
    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % capacity;  // Wrap around
        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; }
};
// All operations: O(1). Space: O(k).
 
/*
  Key formula: next index = (current + 1) % capacity
  Rear value:  data[(tail - 1 + capacity) % capacity]  (the +capacity handles tail=0)
*/

// BFS from start node — returns distance to every reachable node
vector<int> bfs(int start, int n, vector<vector<int>>& adj) {
    vector<int> dist(n, -1);
    queue<int> q;
 
    dist[start] = 0;
    q.push(start);
 
    while (!q.empty()) {
        int node = q.front(); q.pop();
 
        for (int neighbor : adj[node]) {
            if (dist[neighbor] == -1) {    // Not visited yet
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);          // Warning: Mark as visited HERE (when enqueuing)
            }
        }
    }
    return dist;
}
// Time: O(V + E), Space: O(V)

// Process nodes level by level; track the current depth
void bfsLevelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
 
    int level = 0;
    while (!q.empty()) {
        int levelSize = q.size();   // Snapshot of current level's size
 
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            cout << node->val << " ";   // Process node at this level
 
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << "\n";
        level++;
    }
}
// Time: O(n), Space: O(n) — at most O(width) nodes in queue at once

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> result;
    queue<TreeNode*> q;
    q.push(root);
 
    while (!q.empty()) {
        int sz = q.size();
        result.emplace_back();
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            result.back().push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}

// BFS on 2D grid to find shortest path from src to dst
// Returns minimum steps, or -1 if unreachable
int bfsGrid(vector<vector<int>>& grid, pair<int,int> src, pair<int,int> dst) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    queue<pair<int,int>> q;
 
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
 
    visited[src.first][src.second] = true;
    q.push(src);
    int steps = 0;
 
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            auto [x, y] = q.front(); q.pop();
            if (x == dst.first && y == dst.second) return steps;
 
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                    && !visited[nx][ny] && grid[nx][ny] != BLOCKED) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        steps++;
    }
    return -1;   // Unreachable
}
// Time: O(rows × cols), Space: O(rows × cols)

// Multi-source BFS — initialize queue with ALL sources at distance 0
void multiSourceBFS(vector<vector<int>>& grid,
                    vector<pair<int,int>>& sources,
                    vector<vector<int>>& dist) {
    int rows = grid.size(), cols = grid[0].size();
    queue<pair<int,int>> q;
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
 
    // Initialize ALL sources at distance 0
    for (auto [r, c] : sources) {
        dist[r][c] = 0;
        q.push({r, c});
    }
 
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
 
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                && dist[nx][ny] == -1) {          // Not yet reached
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}
// Applications: Rotting Oranges, 01 Matrix, Walls and Gates

vector<int> zeroOneBFS(int start, int n, vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, weight)} where weight is 0 or 1
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
 
    dist[start] = 0;
    dq.push_front(start);
 
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
 
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);   // 0-weight: front (processed first)
                else        dq.push_back(v);     // 1-weight: back (processed later)
            }
        }
    }
    return dist;
}
// Time: O(V + E), Space: O(V)

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> result;
    queue<TreeNode*> q;
    q.push(root);
 
    while (!q.empty()) {
        int sz = q.size();
        result.emplace_back();
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            result.back().push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}
// Time: O(n), Space: O(n)

int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size(), count = 0;
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
 
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1') {
                count++;
                // BFS to mark the entire island as visited
                queue<pair<int,int>> q;
                grid[i][j] = '0';   // Mark visited in-place
                q.push({i, j});
 
                while (!q.empty()) {
                    auto [x, y] = q.front(); q.pop();
                    for (int d = 0; d < 4; d++) {
                        int nx = x+dx[d], ny = y+dy[d];
                        if (nx>=0 && nx<rows && ny>=0 && ny<cols && grid[nx][ny]=='1') {
                            grid[nx][ny] = '0';   // Mark as visited when enqueuing
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }
    return count;
}
// Time: O(rows × cols), Space: O(min(rows, cols)) — queue width at most diagonal

int orangesRotting(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    queue<pair<int,int>> q;
    int fresh = 0;
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
 
    // Multi-source BFS: initialize ALL rotten oranges at time=0
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 2) q.push({i, j});
            if (grid[i][j] == 1) fresh++;
        }
 
    if (fresh == 0) return 0;
 
    int minutes = 0;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            auto [x, y] = q.front(); q.pop();
            for (int d = 0; d < 4; d++) {
                int nx = x+dx[d], ny = y+dy[d];
                if (nx>=0 && nx<rows && ny>=0 && ny<cols && grid[nx][ny]==1) {
                    grid[nx][ny] = 2;    // Infect
                    fresh--;
                    q.push({nx, ny});
                }
            }
        }
        if (!q.empty()) minutes++;   // Only count if something happened
    }
    return fresh == 0 ? minutes : -1;
}
// Time: O(rows × cols), Space: O(rows × cols)

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int rows = mat.size(), cols = mat[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    queue<pair<int,int>> q;
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
 
    // Initialize all zeros as sources (distance 0)
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (mat[i][j] == 0) { dist[i][j] = 0; q.push({i, j}); }
 
    // Multi-source BFS — expands outward from all zeros simultaneously
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x+dx[d], ny = y+dy[d];
            if (nx>=0 && nx<rows && ny>=0 && ny<cols && dist[nx][ny]==-1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return dist;
}
// Time: O(rows × cols), Space: O(rows × cols)

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    if (!wordSet.count(endWord)) return 0;
 
    queue<string> q;
    q.push(beginWord);
    wordSet.erase(beginWord);
    int steps = 1;
 
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            string word = q.front(); q.pop();
            if (word == endWord) return steps;
 
            // Try all one-letter mutations
            for (int j = 0; j < (int)word.size(); j++) {
                char original = word[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    word[j] = c;
                    if (wordSet.count(word)) {
                        wordSet.erase(word);   // Mark visited by removing from set
                        q.push(word);
                    }
                }
                word[j] = original;   // Restore
            }
        }
        steps++;
    }
    return 0;
}
// Time: O(M² × N) where M = word length, N = word list size
// Space: O(M × N)

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;   // Indices; values monotonically decreasing
    vector<int> result;
 
    for (int i = 0; i < (int)nums.size(); i++) {
        // Remove out-of-window indices from front
        while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
        // Remove smaller values from back — they can never be window maximum
        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;
}
// Time: O(n), Space: O(k)

class MyCircularQueue {
    vector<int> data;
    int head, tail, size, cap;
public:
    MyCircularQueue(int k) : data(k), head(0), tail(0), size(0), cap(k) {}
    bool enQueue(int val) {
        if (isFull()) return false;
        data[tail] = val; tail = (tail+1) % cap; size++; return true;
    }
    bool deQueue() {
        if (isEmpty()) return false;
        head = (head+1) % cap; size--; return true;
    }
    int  Front()   { return isEmpty() ? -1 : data[head]; }
    int  Rear()    { return isEmpty() ? -1 : data[(tail-1+cap) % cap]; }
    bool isEmpty() { return size == 0; }
    bool isFull()  { return size == cap; }
};
// All operations: O(1)

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
    if (n == 1) return 1;
 
    queue<pair<int,int>> q;
    grid[0][0] = 1;   // Mark visited (reuse grid to save space)
    q.push({0, 0});
    int steps = 1;
 
    int dx[] = {-1,-1,-1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1,-1, 1,-1, 0, 1};
 
    while (!q.empty()) {
        int sz = q.size();
        steps++;
        for (int i = 0; i < sz; i++) {
            auto [x, y] = q.front(); q.pop();
            for (int d = 0; d < 8; d++) {
                int nx = x+dx[d], ny = y+dy[d];
                if (nx>=0 && nx<n && ny>=0 && ny<n && grid[nx][ny]==0) {
                    if (nx==n-1 && ny==n-1) return steps;
                    grid[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    return -1;
}
// Time: O(n²), Space: O(n²)

int maxResult(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    deque<int> dq;
    dq.push_back(0);
 
    for (int i = 1; i < n; i++) {
        while (!dq.empty() && dq.front() < i - k) dq.pop_front();
        dp[i] = nums[i] + dp[dq.front()];
        while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
        dq.push_back(i);
    }
    return dp[n - 1];
}
// Time: O(n), Space: O(n)

int openLock(vector<string>& deadends, string target) {
    unordered_set<string> dead(deadends.begin(), deadends.end());
    if (dead.count("0000")) return -1;
    if (target == "0000")   return 0;
 
    unordered_set<string> visited;
    queue<string> q;
    q.push("0000");
    visited.insert("0000");
    int turns = 0;
 
    while (!q.empty()) {
        int sz = q.size();
        turns++;
        for (int i = 0; i < sz; i++) {
            string curr = q.front(); q.pop();
            // Try all 8 moves (4 wheels × 2 directions)
            for (int w = 0; w < 4; w++) {
                for (int dir : {1, -1}) {
                    string next = curr;
                    next[w] = (next[w] - '0' + dir + 10) % 10 + '0';
                    if (next == target) return turns;
                    if (!dead.count(next) && !visited.count(next)) {
                        visited.insert(next);
                        q.push(next);
                    }
                }
            }
        }
    }
    return -1;
}
// Time: O(10^4 × 4 × 2) = O(80000), Space: O(10^4)

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int maxWidth = 0;
    // Queue of {node, position_index}
    // Left child of node at pos p → 2p, right child → 2p+1
    queue<pair<TreeNode*, long long>> q;
    q.push({root, 0});
 
    while (!q.empty()) {
        int sz = q.size();
        long long leftmost = q.front().second;
        long long rightmost = leftmost;
 
        for (int i = 0; i < sz; i++) {
            auto [node, pos] = q.front(); q.pop();
            // Normalize position to prevent overflow: subtract leftmost
            long long normPos = pos - leftmost;
            rightmost = normPos;
 
            if (node->left)  q.push({node->left,  2 * normPos});
            if (node->right) q.push({node->right, 2 * normPos + 1});
        }
        maxWidth = max(maxWidth, (int)(rightmost + 1));
    }
    return maxWidth;
}
// Time: O(n), Space: O(n)
// Key: normalize positions each level to prevent long long overflow

void wallsAndGates(vector<vector<int>>& rooms) {
    if (rooms.empty()) return;
    int rows = rooms.size(), cols = rooms[0].size();
    const int INF = 2147483647;
    queue<pair<int,int>> q;
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
 
    // Multi-source BFS: start from ALL gates simultaneously
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (rooms[i][j] == 0) q.push({i, j});
 
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x+dx[d], ny = y+dy[d];
            if (nx>=0 && nx<rows && ny>=0 && ny<cols && rooms[nx][ny]==INF) {
                rooms[nx][ny] = rooms[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}
// Time: O(rows × cols), Space: O(rows × cols)