Skills101

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

OperationMeaningCost
enqueue / appendadd at the backO(1)
dequeue / popleftremove from the frontO(1)
peeklook at the frontO(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 while a[i] is in the window.
  • Pop from the front if that index has slid out of the window (≤ i − k).

Sliding window maximum with k = 3 on 1 3 -1 -3 5 3 6 7: the deque values after each step are 3 -1, 3 -1 -3, 5, 5 3, 6, 7 and the window maxima are 3 3 5 5 6 7; the front of the deque is always the maximum

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; use deque.popleft().
  • Using java.util.Stack or LinkedList everywhere — ArrayDeque is the fast general choice.
  • In a circular queue, telling "full" from "empty" by head == tail alone — keep a size counter (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: ArrayDeque via Queue / Deque.
  • Circular queue: head, size, and % capacity to wrap around.
  • Queue from two stacks: amortised O(1).
  • Sliding window maximum: a decreasing deque of indexes, O(n).

Practice what you learned

📝 Quiz: Queues and Deques5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →