# Queues and Deques — FIFO, Circular Queues and Sliding Window Maximum

Source: https://skills101.in/learn/dsa/dsa-queues-and-deques — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

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).

```python
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))
```

```text
Asha Ravi 2
['Ravi', 'Meena', 'Vikram']
```

```java
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());
    }
}
```

```text
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.

```python
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)
```

```text
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).

```python
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())
```

```text
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](https://skills101.in/learn-img/dsa/window-max.svg)

```python
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))
```

```text
[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 quiz and free certificate: https://skills101.in/learn/dsa/dsa-queues-and-deques