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.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Core ideas | BFS 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.
- Shortest path in an unweighted graph or grid: BFS.
- Level by level output: process the queue in rounds.
- Sliding extremes: deque of indices, kept monotonic.
- Recent-events window: deque with expiry from the front.
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 Design a circular queue with a fixed capacity.
easyUse 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.
pythonclass 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]javaclass 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 Implement a stack using a single queue.
easyOn 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.
pythonfrom 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.qjavaimport 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 Number of recent requests: count pings within the last 3000 ms.
easyPings 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.
pythonfrom 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)javaimport 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 Moving average from a data stream with a fixed window size.
easyKeep 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.
pythonfrom 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)javaimport 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 First unique number in a data stream: add numbers and report the first one seen only once.
mediumKeep 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.
pythonfrom 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)javaimport 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 Binary tree level order traversal.
mediumUse 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.
pythonfrom 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 outjavaimport 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 Rotting oranges: minutes until all fresh oranges rot, or -1.
mediumMulti-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.
pythonfrom 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 -1javaimport 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 Shortest path in a binary matrix, moving in 8 directions through cells that are 0.
mediumBFS 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.
pythonfrom 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 -1javaimport 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 Longest subarray where the difference between max and min is at most limit.
hardSlide 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.
pythonfrom 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 bestjavaimport 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 Jump game VI: maximum score reaching the last index, jumping at most k steps each time.
hardLet 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.
pythonfrom 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]javaimport 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
- Stack interview questions with worked solutions
- Monotonic stack interview questions with worked solutions
- Sliding window interview questions with worked solutions
- Matrix interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Linked list interview questions with worked solutions
More in DSA Interview Questions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Topological Sort Interview Questions
- Tree DP Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions