Autocoder

Queue and deque interview questions with worked solutions

Last updated 2026-11-19

A queue serves items in the order they arrived, which is exactly what breadth-first search needs: explore everything one step away, then everything two steps away. A deque (double-ended queue) allows adds and removals at both ends, and that extra freedom powers sliding-window tricks and certain dynamic programming optimisations.

The problems below move from data-structure design to BFS on grids and trees and finally to monotonic deque problems. In Python use collections.deque (never list.pop(0), which is O(n)); in Java use ArrayDeque or LinkedList through the Queue and Deque interfaces. For the window-maximum classic, see sliding window questions; for tests in general, the DSA coding round guide.

Problems10, easy to hard
LanguagesPython and Java
Core ideasBFS by levels, monotonic deque

BFS template

Put the start node in a queue and mark it visited when you enqueue it, not when you dequeue it, so nothing enters the queue twice. To count levels or distance, process the queue in rounds: take the current size, handle exactly that many nodes, then increment the level.

Multi-source BFS starts with several nodes already in the queue, which gives the distance to the nearest source for every cell.

Choosing the right structure

A queue is the wrong choice for weighted shortest paths (use a heap), and a plain list is the wrong choice in Python for queues because popping from the front shifts every element. Circular buffers give O(1) operations with a fixed memory block, which is what a bounded queue design question is testing.

Queue and deque interview questions with worked solutions: questions with worked answers

  1. 1

    Design a circular queue with a fixed capacity.

    easy

    Use an array of size k, a head index and a count. Enqueue writes at (head + count) % k; dequeue advances head modulo k. Tracking count rather than a tail pointer avoids the classic ambiguity between full and empty. Time O(1) per operation, space O(k).. Edge cases: enqueue when full returns false, dequeue when empty returns false, wrap-around after many operations.

    python
    class MyCircularQueue:
        def __init__(self, k):
            self.a, self.k, self.head, self.n = [0] * k, k, 0, 0
    
        def en_queue(self, v):
            if self.n == self.k:
                return False
            self.a[(self.head + self.n) % self.k] = v
            self.n += 1
            return True
    
        def de_queue(self):
            if self.n == 0:
                return False
            self.head = (self.head + 1) % self.k
            self.n -= 1
            return True
    
        def front(self):
            return -1 if self.n == 0 else self.a[self.head]
    
        def rear(self):
            return -1 if self.n == 0 else self.a[(self.head + self.n - 1) % self.k]
    java
    class MyCircularQueue {
        private final int[] a;
        private int head = 0, n = 0;
    
        MyCircularQueue(int k) { a = new int[k]; }
        boolean enQueue(int v) {
            if (n == a.length) return false;
            a[(head + n) % a.length] = v;
            n++;
            return true;
        }
        boolean deQueue() {
            if (n == 0) return false;
            head = (head + 1) % a.length;
            n--;
            return true;
        }
        int front() { return n == 0 ? -1 : a[head]; }
        int rear() { return n == 0 ? -1 : a[(head + n - 1) % a.length]; }
    }
  2. 2

    Implement a stack using a single queue.

    easy

    On push, add the element at the back, then rotate the queue by moving every earlier element from the front to the back. The newest element is now at the front, so pop and top are plain queue operations. Push costs O(n); that is the trade. Time push O(n), pop and top O(1); space O(n).. Edge cases: pop on empty, alternating push and pop, a single element.

    python
    from collections import deque
    
    class MyStack:
        def __init__(self):
            self.q = deque()
    
        def push(self, x):
            self.q.append(x)
            for _ in range(len(self.q) - 1):
                self.q.append(self.q.popleft())
    
        def pop(self):
            return self.q.popleft()
    
        def top(self):
            return self.q[0]
    
        def empty(self):
            return not self.q
    java
    import java.util.*;
    
    class MyStack {
        private final Queue<Integer> q = new LinkedList<>();
    
        void push(int x) {
            q.add(x);
            for (int i = 0; i < q.size() - 1; i++) q.add(q.poll());
        }
        int pop() { return q.poll(); }
        int top() { return q.peek(); }
        boolean empty() { return q.isEmpty(); }
    }
  3. 3

    Number of recent requests: count pings within the last 3000 ms.

    easy

    Pings arrive with increasing timestamps. Append each timestamp to a queue and remove from the front any timestamp older than t - 3000. The queue length is the answer. Each timestamp is added and removed once. Time amortised O(1) per call, space O(window size).. Edge cases: first call, two calls at the same time, a long gap that empties the queue.

    python
    from collections import deque
    
    class RecentCounter:
        def __init__(self):
            self.q = deque()
    
        def ping(self, t):
            self.q.append(t)
            while self.q[0] < t - 3000:
                self.q.popleft()
            return len(self.q)
    java
    import java.util.*;
    
    class RecentCounter {
        private final Queue<Integer> q = new ArrayDeque<>();
    
        int ping(int t) {
            q.add(t);
            while (q.peek() < t - 3000) q.poll();
            return q.size();
        }
    }
  4. 4

    Moving average from a data stream with a fixed window size.

    easy

    Keep a queue of the last size values and their running sum. On each new value add it to the queue and the sum; if the queue exceeds size, remove the oldest and subtract it. Return sum divided by the current queue length (not size) until the window fills. Time O(1) per call, space O(size).. Edge cases: fewer values than the window size, a window of 1, negative values.

    python
    from collections import deque
    
    class MovingAverage:
        def __init__(self, size):
            self.size, self.q, self.s = size, deque(), 0
    
        def next(self, val):
            self.q.append(val)
            self.s += val
            if len(self.q) > self.size:
                self.s -= self.q.popleft()
            return self.s / len(self.q)
    java
    import java.util.*;
    
    class MovingAverage {
        private final int size;
        private final Queue<Integer> q = new ArrayDeque<>();
        private long sum = 0;
    
        MovingAverage(int size) { this.size = size; }
        double next(int val) {
            q.add(val);
            sum += val;
            if (q.size() > size) sum -= q.poll();
            return (double) sum / q.size();
        }
    }
  5. 5

    First unique number in a data stream: add numbers and report the first one seen only once.

    medium

    Keep a count map and a queue of candidates in arrival order. On add, increase the count and enqueue the value only the first time it appears. To read the answer, lazily discard from the front any value whose count is now above one. The front, if any, is the first unique number. Time amortised O(1) per operation, space O(n).. Edge cases: no unique value (return -1), a value that becomes non-unique after being at the front, empty stream.

    python
    from collections import deque
    
    class FirstUnique:
        def __init__(self, nums):
            self.cnt, self.q = {}, deque()
            for x in nums:
                self.add(x)
    
        def show_first_unique(self):
            while self.q and self.cnt[self.q[0]] > 1:
                self.q.popleft()
            return self.q[0] if self.q else -1
    
        def add(self, v):
            self.cnt[v] = self.cnt.get(v, 0) + 1
            if self.cnt[v] == 1:
                self.q.append(v)
    java
    import java.util.*;
    
    class FirstUnique {
        private final Map<Integer, Integer> cnt = new HashMap<>();
        private final Queue<Integer> q = new ArrayDeque<>();
    
        FirstUnique(int[] nums) { for (int x : nums) add(x); }
        int showFirstUnique() {
            while (!q.isEmpty() && cnt.get(q.peek()) > 1) q.poll();
            return q.isEmpty() ? -1 : q.peek();
        }
        void add(int v) {
            int c = cnt.merge(v, 1, Integer::sum);
            if (c == 1) q.add(v);
        }
    }
  6. 6

    Binary tree level order traversal.

    medium

    Use BFS. Push the root; while the queue is not empty, take its current size n, pop exactly n nodes into one list, and enqueue their children. Each round is one level. This is the template for zigzag, right-side view and average-per-level questions. Time O(n), space O(width of the tree).. Edge cases: empty tree (empty list), skewed tree, a single node.

    python
    from collections import deque
    
    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val, self.left, self.right = val, left, right
    
    def level_order(root):
        if not root:
            return []
        q, out = deque([root]), []
        while q:
            level = []
            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)
            out.append(level)
        return out
    java
    import java.util.*;
    
    class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    class Solution {
        static List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> out = new ArrayList<>();
            if (root == null) return out;
            Queue<TreeNode> q = new ArrayDeque<>();
            q.add(root);
            while (!q.isEmpty()) {
                List<Integer> level = new ArrayList<>();
                for (int i = q.size(); i > 0; i--) {
                    TreeNode node = q.poll();
                    level.add(node.val);
                    if (node.left != null) q.add(node.left);
                    if (node.right != null) q.add(node.right);
                }
                out.add(level);
            }
            return out;
        }
    }
  7. 7

    Rotting oranges: minutes until all fresh oranges rot, or -1.

    medium

    Multi-source BFS. Put every rotten orange in the queue and count the fresh ones. Each round of the queue is one minute: rot the fresh neighbours, decrement the fresh count and enqueue them. If fresh oranges remain at the end, some were unreachable, so return -1. Time O(rows * cols), space O(rows * cols).. Edge cases: no fresh oranges (0), no rotten oranges with fresh present (-1), an orange isolated by empty cells.

    python
    from collections import deque
    
    def oranges_rotting(g):
        R, C = len(g), len(g[0])
        q, fresh = deque(), 0
        for i in range(R):
            for j in range(C):
                if g[i][j] == 2:
                    q.append((i, j))
                elif g[i][j] == 1:
                    fresh += 1
        mins = 0
        while q and fresh:
            for _ in range(len(q)):
                r, c = q.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < R and 0 <= nc < C and g[nr][nc] == 1:
                        g[nr][nc] = 2
                        fresh -= 1
                        q.append((nr, nc))
            mins += 1
        return mins if fresh == 0 else -1
    java
    import java.util.*;
    
    class Solution {
        static int orangesRotting(int[][] g) {
            int R = g.length, C = g[0].length, fresh = 0, mins = 0;
            Queue<int[]> q = new ArrayDeque<>();
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++) {
                    if (g[i][j] == 2) q.add(new int[]{i, j});
                    else if (g[i][j] == 1) fresh++;
                }
            int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            while (!q.isEmpty() && fresh > 0) {
                for (int s = q.size(); s > 0; s--) {
                    int[] cur = q.poll();
                    for (int[] d : dirs) {
                        int nr = cur[0] + d[0], nc = cur[1] + d[1];
                        if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1) {
                            g[nr][nc] = 2;
                            fresh--;
                            q.add(new int[]{nr, nc});
                        }
                    }
                }
                mins++;
            }
            return fresh == 0 ? mins : -1;
        }
    }
  8. 8

    Shortest path in a binary matrix, moving in 8 directions through cells that are 0.

    medium

    BFS from the top-left cell, counting cells on the path. If the start or end is blocked, return -1. Mark cells visited when they are enqueued. The first time the bottom-right cell is dequeued, the distance is the shortest because BFS explores in increasing distance. Time O(n^2) for an n by n grid, space O(n^2).. Edge cases: a 1 by 1 grid with 0 (answer 1), blocked start or end, no path.

    python
    from collections import deque
    
    def shortest_path(g):
        n = len(g)
        if g[0][0] or g[n - 1][n - 1]:
            return -1
        seen = [[False] * n for _ in range(n)]
        seen[0][0] = True
        q = deque([(0, 0, 1)])
        while q:
            r, c, d = q.popleft()
            if r == n - 1 and c == n - 1:
                return d
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and not g[nr][nc] and not seen[nr][nc]:
                        seen[nr][nc] = True
                        q.append((nr, nc, d + 1))
        return -1
    java
    import java.util.*;
    
    class Solution {
        static int shortestPath(int[][] g) {
            int n = g.length;
            if (g[0][0] == 1 || g[n - 1][n - 1] == 1) return -1;
            boolean[][] seen = new boolean[n][n];
            seen[0][0] = true;
            Queue<int[]> q = new ArrayDeque<>();
            q.add(new int[]{0, 0, 1});
            while (!q.isEmpty()) {
                int[] cur = q.poll();
                if (cur[0] == n - 1 && cur[1] == n - 1) return cur[2];
                for (int dr = -1; dr <= 1; dr++)
                    for (int dc = -1; dc <= 1; dc++) {
                        int nr = cur[0] + dr, nc = cur[1] + dc;
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n && g[nr][nc] == 0 && !seen[nr][nc]) {
                            seen[nr][nc] = true;
                            q.add(new int[]{nr, nc, cur[2] + 1});
                        }
                    }
            }
            return -1;
        }
    }
  9. 9

    Longest subarray where the difference between max and min is at most limit.

    hard

    Slide a window and keep two deques of indices: one decreasing (front is the window maximum) and one increasing (front is the window minimum). After adding the new element, while max minus min exceeds the limit, advance the left edge and drop fronts that fell out of the window. Record the window length each step. Time O(n), space O(n).. Edge cases: limit 0 (equal runs only), a single element, a limit larger than the whole range.

    python
    from collections import deque
    
    def longest_subarray(a, limit):
        mx, mn = deque(), deque()
        l = best = 0
        for r, x in enumerate(a):
            while mx and a[mx[-1]] <= x:
                mx.pop()
            mx.append(r)
            while mn and a[mn[-1]] >= x:
                mn.pop()
            mn.append(r)
            while a[mx[0]] - a[mn[0]] > limit:
                l += 1
                if mx[0] < l:
                    mx.popleft()
                if mn[0] < l:
                    mn.popleft()
            best = max(best, r - l + 1)
        return best
    java
    import java.util.*;
    
    class Solution {
        static int longestSubarray(int[] a, int limit) {
            Deque<Integer> mx = new ArrayDeque<>(), mn = new ArrayDeque<>();
            int l = 0, best = 0;
            for (int r = 0; r < a.length; r++) {
                while (!mx.isEmpty() && a[mx.peekLast()] <= a[r]) mx.pollLast();
                mx.addLast(r);
                while (!mn.isEmpty() && a[mn.peekLast()] >= a[r]) mn.pollLast();
                mn.addLast(r);
                while (a[mx.peekFirst()] - a[mn.peekFirst()] > limit) {
                    l++;
                    if (mx.peekFirst() < l) mx.pollFirst();
                    if (mn.peekFirst() < l) mn.pollFirst();
                }
                best = Math.max(best, r - l + 1);
            }
            return best;
        }
    }
  10. 10

    Jump game VI: maximum score reaching the last index, jumping at most k steps each time.

    hard

    Let dp[i] be the best score ending at i: dp[i] = a[i] + max(dp[i-k..i-1]). The maximum over a sliding range is a job for a deque of indices with decreasing dp values. Drop front indices older than i - k, take dp from the front, then pop smaller dp values from the back before pushing i. Time O(n), space O(n).. Edge cases: k = 1 (sum of everything), negative values, a single element.

    python
    from collections import deque
    
    def max_result(a, k):
        n = len(a)
        dp = [0] * n
        dp[0] = a[0]
        dq = deque([0])
        for i in range(1, n):
            while dq[0] < i - k:
                dq.popleft()
            dp[i] = a[i] + dp[dq[0]]
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)
        return dp[-1]
    java
    import java.util.*;
    
    class Solution {
        static int maxResult(int[] a, int k) {
            int n = a.length;
            int[] dp = new int[n];
            dp[0] = a[0];
            Deque<Integer> dq = new ArrayDeque<>();
            dq.add(0);
            for (int i = 1; i < n; i++) {
                while (dq.peekFirst() < i - k) dq.pollFirst();
                dp[i] = a[i] + dp[dq.peekFirst()];
                while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
                dq.addLast(i);
            }
            return dp[n - 1];
        }
    }

Frequently asked questions

Why not use a Python list as a queue?

list.pop(0) shifts every remaining element, so it is O(n). collections.deque pops from either end in O(1).

When do I mark nodes visited in BFS?

When you enqueue them. Marking at dequeue time lets the same node enter the queue several times, which can blow up the running time.

What is the difference between a queue, a deque and a priority queue?

A queue is first in, first out. A deque allows adds and removals at both ends. A priority queue returns the smallest or largest item first, not the oldest.

How do I get the shortest path in a weighted graph?

BFS only works for equal weights. For non-negative weights use Dijkstra with a heap, which the top k elements questions introduce through heaps.

Where does a deque help beyond BFS?

Sliding-window extremes and DP over a bounded range, as in the last two problems here. The pattern is the same as in monotonic stack questions.

Related guides

More in DSA Interview Questions

See all in this section