AdvancedData Structures & Algorithms · Lesson 24 of 25 · Updated ·
Queues and Deques — FIFO, Circular Queues and Sliding Window Maximum
A queue is a line at a ticket counter: the first person in is the first served — FIFO (first in, first out). A deque ("deck", double-ended queue) lets you add and remove at both ends. Queues drive breadth-first search, task scheduling and buffering; deques power some of the neatest O(n) tricks in interviews.
1. Queue operations
| Operation | Meaning | Cost |
|---|---|---|
enqueue / append | add at the back | O(1) |
dequeue / popleft | remove from the front | O(1) |
| peek | look at the front | O(1) |
Use the right class. In Python, list.pop(0) shifts every element — O(n). Use collections.deque. In Java, use ArrayDeque (through the Queue or Deque interface).
from collections import deque
q = deque()
for person in ["Asha", "Ravi", "Meena"]:
q.append(person) # join the back
print(q.popleft(), q[0], len(q))
q.append("Vikram")
print(list(q))
Asha Ravi 2
['Ravi', 'Meena', 'Vikram']
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<String> q = new ArrayDeque<>();
q.offer("Asha"); q.offer("Ravi"); q.offer("Meena");
System.out.println(q.poll() + " " + q.peek() + " " + q.size());
Deque<Integer> d = new ArrayDeque<>();
d.offerFirst(2); d.offerLast(3); d.offerFirst(1);
System.out.println(d + " " + d.pollLast() + " " + d.peekFirst());
}
}
Asha Ravi 2
[1, 2, 3] 3 1
offer/poll/peek return false/null on failure; add/remove/element throw exceptions instead.
2. A circular queue with an array
Interviews often ask you to implement a fixed-size queue. Keep a head index and a size; the back is at (head + size) % capacity. The % makes the indexes wrap around, so freed slots at the front get reused.
class CircularQueue:
def __init__(self, k):
self.a, self.head, self.size = [0] * k, 0, 0
def enqueue(self, x):
if self.size == len(self.a):
return False # full
self.a[(self.head + self.size) % len(self.a)] = x
self.size += 1
return True
def dequeue(self):
if self.size == 0:
return None # empty
x = self.a[self.head]
self.head = (self.head + 1) % len(self.a)
self.size -= 1
return x
q = CircularQueue(3)
print(q.enqueue(1), q.enqueue(2), q.enqueue(3), q.enqueue(4))
print(q.dequeue(), q.enqueue(4), q.a)
True True True False
1 True [4, 2, 3]
After removing 1, the value 4 goes into slot 0 — the slot that was freed — instead of needing a bigger array.
3. Queue using two stacks
Another favourite: build a FIFO queue from two LIFO stacks. Push into inbox; when you need the front and outbox is empty, pour everything from inbox into outbox (which reverses the order).
class TwoStackQueue:
def __init__(self):
self.inbox, self.outbox = [], []
def push(self, x):
self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
return self.outbox.pop()
q = TwoStackQueue()
for x in (1, 2, 3):
q.push(x)
print(q.pop(), q.pop())
q.push(4)
print(q.pop(), q.pop())
1 2
3 4
Each element moves from inbox to outbox at most once, so every operation is amortised O(1).
4. Sliding window maximum with a monotonic deque
Problem: for every window of k consecutive elements, print its maximum. Recomputing each window is O(n·k).
Idea: keep a deque of indexes whose values are decreasing. Then the front is always the window's maximum.
- Before adding
a[i], pop from the back every index whose value is ≤a[i]— they can never be a maximum again whilea[i]is in the window. - Pop from the front if that index has slid out of the window (
≤ i − k).
from collections import deque
def window_max(a, k):
dq, out = deque(), []
for i, x in enumerate(a):
if dq and dq[0] <= i - k: # front fell out of the window
dq.popleft()
while dq and a[dq[-1]] <= x: # smaller values are useless now
dq.pop()
dq.append(i)
if i >= k - 1:
out.append(a[dq[0]])
return out
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_max([9, 8, 7, 6], 2))
[3, 3, 5, 5, 6, 7]
[9, 8, 7]
Every index enters and leaves the deque once: O(n) overall. It is the monotonic stack from the previous lesson with one extra rule — removal from the front when the window moves.
5. Where queues appear
- Breadth-first search on graphs and grids — always a queue.
- Level-order traversal of a tree (next lesson).
- Task scheduling, printers, message queues — work in arrival order.
- Priority queue is different: it serves the smallest (or largest) item first, not the oldest. That is a heap — see the heaps lesson.
Common mistakes
list.pop(0)in Python for a queue — O(n) per pop; usedeque.popleft().- Using
java.util.StackorLinkedListeverywhere —ArrayDequeis the fast general choice. - In a circular queue, telling "full" from "empty" by
head == tailalone — keep asizecounter (or leave one slot empty). - In sliding window maximum, storing values instead of indexes, so you can't tell when the front left the window.
Quick recap
- Queue = FIFO: add at the back, remove from the front, all O(1).
- Python:
collections.deque; Java:ArrayDequeviaQueue/Deque. - Circular queue:
head,size, and% capacityto wrap around. - Queue from two stacks: amortised O(1).
- Sliding window maximum: a decreasing deque of indexes, O(n).