Queues and Deques: FIFO, Double-Ended, and Circular

The introduction article gave you the shape of a queue and how it differs from a stack. This post goes deeper. We will build real implementations, use queues to solve graph and array problems, and meet two powerful variants: the deque (double-ended queue) and the circular queue. By the end you will know which queue variant to reach for and why.

---

1. What is a Queue (FIFO)?

A queue enforces first-in, first-out order. The item that has been waiting the longest is the next one served. Real-world analogies are everywhere:

• A line at a coffee shop — whoever ordered first gets their drink first.
• A printer queue — documents print in the order they were submitted.
• A call center — the caller who dialed in first talks to the next available agent.

The two fundamental operations are:

Operation	What it does	Time
enqueue	Add an item to the rear	O(1)
dequeue	Remove the item at the front	O(1)
peek	Read the front item without removing it	O(1)
isEmpty	Check whether the queue is empty	O(1)

Every operation is O(1). That constant-time guarantee is what makes queues useful in performance-sensitive systems like task schedulers and network buffers.

---

2. Queue Implementation with collections.deque

Python’s built-in list can act as a queue, but do not use it. Popping from the front of a list is O(n) because every remaining element shifts left. The standard library gives us collections.deque, a doubly-linked list that supports O(1) operations on both ends.

from collections import deque

class Queue:
    """Simple FIFO queue backed by collections.deque."""

    def __init__(self):
        self._data = deque()

    def enqueue(self, val):
        """Add to the rear."""
        self._data.append(val)

    def dequeue(self):
        """Remove and return from the front. Raises IndexError if empty."""
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        return self._data.popleft()

    def peek(self):
        """Return the front item without removing it."""
        if self.is_empty():
            raise IndexError("peek from an empty queue")
        return self._data[0]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

    def __repr__(self):
        return f"Queue({list(self._data)})"

Usage:

q = Queue()
q.enqueue("A")
q.enqueue("B")
q.enqueue("C")

print(q.peek())     # "A"
print(q.dequeue())  # "A"
print(q.dequeue())  # "B"
print(q)            # Queue(['C'])

Notice how "A" came out first even though "C" was added last. That is FIFO in action.

Why not list.pop(0)?

# Bad — O(n) per dequeue
queue = [1, 2, 3, 4, 5]
front = queue.pop(0)  # every element shifts left

# Good — O(1) per dequeue
from collections import deque
queue = deque([1, 2, 3, 4, 5])
front = queue.popleft()  # no shifting needed

For a queue of 1 million items, the difference is the difference between 1 microsecond and 1 millisecond per dequeue. Over thousands of operations, it adds up fast.

---

3. Queue Operations — Big-O Summary

Operation	collections.deque	list (naive)	Notes
enqueue (append)	O(1)	O(1) amortized	Both append to the end
dequeue (popleft)	O(1)	O(n)	List shifts everything
peek (index 0)	O(1)	O(1)	Direct access
isEmpty	O(1)	O(1)	Length check
Search	O(n)	O(n)	Linear scan either way

The takeaway: always use deque for queues in Python.

---

4. BFS Using a Queue

Breadth-first search is the textbook use case for a queue. BFS visits all neighbors at distance d before visiting any neighbor at distance d + 1. A queue enforces exactly that order.

from collections import deque

def bfs(graph, start):
    """
    Breadth-first search on an adjacency-list graph.
    Returns the list of nodes in the order they were visited.
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

Let’s run it on a small graph:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(bfs(graph, "A"))
# ['A', 'B', 'C', 'D', 'E', 'F']

BFS explores level by level: first A, then its neighbors B and C, then their unvisited neighbors D, E, F. The queue keeps everything in the right order without any extra bookkeeping.

BFS for shortest path (unweighted)

Because BFS visits nodes in order of distance from the source, the first time it reaches a node is the shortest path. This makes BFS the go-to algorithm for shortest paths in unweighted graphs.

from collections import deque

def shortest_path(graph, start, target):
    """Return the shortest path from start to target, or None."""
    visited = {start}
    queue = deque([(start, [start])])

    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None

print(shortest_path(graph, "A", "F"))
# ['A', 'C', 'F']

---

5. What is a Deque (Double-Ended Queue)?

A deque (pronounced “deck”) allows insertion and removal at both ends in O(1) time. A regular queue restricts you to add at the rear and remove from the front. A deque lifts that restriction.

Think of a deque as a deck of cards where you can draw from either the top or the bottom and place new cards on either end.

When do you need a deque?

• Sliding window problems — you need to push on the right and sometimes discard from the left.
• Palindrome checking — compare characters from both ends.
• Work-stealing schedulers — threads push tasks onto one end and steal from the other.
• Undo/redo with bounded history — add new actions to the right, drop oldest from the left when the buffer is full.

---

6. Deque Operations in Python

collections.deque already is a deque. We have been using it as a queue, but it supports all four directional operations:

from collections import deque

d = deque()

# Add to right end
d.append(1)        # deque([1])
d.append(2)        # deque([1, 2])

# Add to left end
d.appendleft(0)    # deque([0, 1, 2])

# Remove from right end
d.pop()            # returns 2, deque([0, 1])

# Remove from left end
d.popleft()        # returns 0, deque([1])

All four operations — append, appendleft, pop, popleft — are O(1).

Bounded deque

You can limit the size of a deque. When the deque is full and you add to one end, the item on the opposite end is automatically dropped:

history = deque(maxlen=3)
history.append("page1")
history.append("page2")
history.append("page3")
history.append("page4")   # "page1" is silently dropped

print(history)  # deque(['page2', 'page3', 'page4'], maxlen=3)

This is perfect for keeping the last N items — recent logs, rolling averages, or bounded caches.

Full operation reference

Method	End	Time	Description
append(x)	Right	O(1)	Add to rear
appendleft(x)	Left	O(1)	Add to front
pop()	Right	O(1)	Remove from rear
popleft()	Left	O(1)	Remove from front
rotate(n)	Both	O(n)	Rotate right by n steps
extend(iterable)	Right	O(k)	Append multiple items
extendleft(iterable)	Left	O(k)	Prepend multiple items (reverses order)

---

7. Sliding Window Maximum — Monotonic Deque

This is one of the most important deque patterns in competitive programming and interviews.

Problem: Given an array nums and a window size k, return the maximum value in each sliding window of size k.

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Window [1, 3, -1]    -> max = 3
Window [3, -1, -3]   -> max = 3
Window [-1, -3, 5]   -> max = 5
Window [-3, 5, 3]    -> max = 5
Window [5, 3, 6]     -> max = 6
Window [3, 6, 7]     -> max = 7

Output: [3, 3, 5, 5, 6, 7]

The brute force approach scans every window for the max, giving O(n * k). With a monotonic deque, we solve it in O(n).

The idea: maintain a deque of indices where the values are in decreasing order. The front of the deque always holds the index of the current window’s maximum.

from collections import deque

def max_sliding_window(nums, k):
    """
    Return the max of each sliding window of size k.
    Uses a monotonic decreasing deque of indices.
    Time: O(n), Space: O(k)
    """
    result = []
    dq = deque()  # stores indices, values are decreasing

    for i, num in enumerate(nums):
        # 1. Remove indices that have fallen out of the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # 2. Remove indices whose values are smaller than num
        #    (they can never be the max while num is in the window)
        while dq and nums[dq[-1]] <= num:
            dq.pop()

        # 3. Add the current index
        dq.append(i)

        # 4. The window is full — record the max
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Why is this O(n)? Each index enters and leaves the deque at most once. The total work across all iterations is linear.

How the deque stays monotonic

At every step, before we push a new index, we pop all indices from the right whose values are smaller. This ensures the deque is always decreasing from left to right. The front is always the largest value in the current window.

---

8. Circular Queue

A circular queue (or ring buffer) uses a fixed-size array where the rear wraps around to the beginning when it reaches the end. This avoids wasting space that would accumulate in a naive array-based queue after many dequeues.

When to use a circular queue

• Bounded buffers — producer/consumer systems with a fixed buffer size.
• Streaming data — audio samples, network packets, or sensor readings where you only care about the last N values.
• OS scheduling — round-robin CPU schedulers use circular buffers for the ready queue.

Implementation

class CircularQueue:
    """Fixed-capacity circular queue (ring buffer)."""

    def __init__(self, capacity):
        self._data = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._size = 0

    def enqueue(self, val):
        if self.is_full():
            raise OverflowError("circular queue is full")
        rear = (self._front + self._size) % self._capacity
        self._data[rear] = val
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty circular queue")
        val = self._data[self._front]
        self._data[self._front] = None  # help garbage collection
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return val

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from an empty circular queue")
        return self._data[self._front]

    def is_empty(self):
        return self._size == 0

    def is_full(self):
        return self._size == self._capacity

    def __len__(self):
        return self._size

    def __repr__(self):
        if self.is_empty():
            return "CircularQueue([])"
        items = []
        for i in range(self._size):
            idx = (self._front + i) % self._capacity
            items.append(self._data[idx])
        return f"CircularQueue({items})"

Let’s trace through an example:

cq = CircularQueue(4)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
print(cq)           # CircularQueue([10, 20, 30])

cq.dequeue()        # removes 10
cq.dequeue()        # removes 20
print(cq)           # CircularQueue([30])

# Now front has moved forward — rear can wrap around
cq.enqueue(40)
cq.enqueue(50)
cq.enqueue(60)      # wraps around to index 0
print(cq)           # CircularQueue([30, 40, 50, 60])
print(cq.is_full()) # True

The internal array after these operations looks like [60, None, 30, 40] — notice how 60 wrapped around to index 0. The front pointer tracks where the logical front is, and the modulo arithmetic handles the wrap.

Complexity

Operation	Time	Space
enqueue	O(1)	—
dequeue	O(1)	—
peek	O(1)	—
Space	—	O(capacity)

The fixed capacity means no dynamic resizing, which is an advantage in systems where predictable memory usage matters.

---

9. Priority Queue vs Regular Queue

A priority queue does not serve items in FIFO order. Instead, it serves the item with the highest (or lowest) priority first. Under the hood, priority queues are typically implemented with a heap.

import heapq

pq = []
heapq.heappush(pq, (3, "low priority task"))
heapq.heappush(pq, (1, "high priority task"))
heapq.heappush(pq, (2, "medium priority task"))

while pq:
    priority, task = heapq.heappop(pq)
    print(f"  {priority}: {task}")

# Output:
#   1: high priority task
#   2: medium priority task
#   3: low priority task

Feature	Queue	Priority Queue
Order	FIFO	By priority
enqueue	O(1)	O(log n)
dequeue	O(1)	O(log n)
Best for	Fairness, BFS	Dijkstra, scheduling

Priority queues deserve their own deep dive. See the Heap & Priority Queue article for full coverage.

---

10. Queue vs Stack vs Deque — When to Use What

Choosing the right structure comes down to where you need to add and remove items:

Structure	Add	Remove	Order	Use when…
Stack	Top only	Top only	LIFO	Undo, DFS, expression parsing, backtracking
Queue	Rear	Front	FIFO	BFS, task scheduling, buffering, fairness
Deque	Both ends	Both ends	Both	Sliding window, palindrome check, work-stealing
Priority Queue	Any	Min/Max	By priority	Dijkstra, event simulation, top-K

Quick decision rules

1. Need FIFO? Use a queue (collections.deque).
2. Need LIFO? Use a stack (Python list).
3. Need to add/remove from both ends? Use a deque (collections.deque).
4. Need items in priority order? Use heapq.
5. Fixed buffer size? Use a circular queue or deque(maxlen=N).

In Python, collections.deque is versatile enough to serve as both a queue and a deque. You will use it far more than any other queue implementation.

---

Common Patterns and Tips

Pattern 1: BFS with level tracking

Sometimes you need to know which “level” each node is on. Use a loop that processes an entire level at once:

from collections import deque

def bfs_levels(graph, start):
    """BFS that tracks the level (distance) of each node."""
    visited = {start}
    queue = deque([start])
    level = 0

    while queue:
        level_size = len(queue)
        print(f"Level {level}:", end=" ")

        for _ in range(level_size):
            node = queue.popleft()
            print(node, end=" ")
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        print()
        level += 1

# Using the graph from earlier:
# Level 0: A
# Level 1: B C
# Level 2: D E F

Pattern 2: Multi-source BFS

Start BFS from multiple sources at once. Useful for problems like “distance from nearest 0 in a grid”:

from collections import deque

def multi_source_bfs(grid):
    """Find distance from each cell to the nearest 0."""
    rows, cols = len(grid), len(grid[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    queue = deque()

    # Initialize: all 0-cells are sources at distance 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))

    # BFS outward from all sources simultaneously
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))

    return dist

Pattern 3: Deque as a max-length history

from collections import deque

recent_searches = deque(maxlen=5)
for term in ["python", "queue", "deque", "bfs", "graph", "tree"]:
    recent_searches.append(term)

print(list(recent_searches))
# ['queue', 'deque', 'bfs', 'graph', 'tree']
# "python" was automatically dropped

---

Common Mistakes to Avoid

1. Using list.pop(0) as a queue — O(n) per dequeue. Always use deque.popleft().

2. Forgetting to mark visited before enqueueing in BFS — If you mark nodes as visited when you dequeue them instead of when you enqueue them, you will add duplicates to the queue and potentially get wrong shortest-path distances.

3. Using a regular queue when you need priority — If items have different urgencies, a FIFO queue will serve them in the wrong order. Use heapq or queue.PriorityQueue.

4. Not handling the empty-queue case — Always check is_empty() before calling dequeue() or peek().

---

Practice Problems

Here are five problems to solidify your understanding, ordered from easy to medium:

1. Implement Queue using Stacks (LeetCode 232) — Build a FIFO queue using two LIFO stacks. This forces you to deeply understand how FIFO differs from LIFO. Hint: use one stack for enqueue and one for dequeue.

2. Number of Islands (LeetCode 200) — Given a 2D grid of '1's (land) and '0's (water), count the number of islands. Solve it with BFS using a queue. Hint: start BFS from every unvisited land cell.

3. Sliding Window Maximum (LeetCode 239) — The monotonic deque problem we covered above. Implement it yourself without looking at the solution. Target: O(n) time.

4. Design Circular Queue (LeetCode 622) — Implement the MyCircularQueue class with enQueue, deQueue, Front, Rear, isEmpty, and isFull methods. Hint: use the modulo-based approach from Section 8.

5. Rotting Oranges (LeetCode 994) — A grid contains fresh and rotten oranges. Each minute, rotten oranges infect adjacent fresh ones. Return the minimum minutes until no fresh orange remains. This is a classic multi-source BFS problem.

---

Wrapping Up

Queues are everywhere in computing — from the operating system’s process scheduler to the browser’s event loop to your favorite streaming service’s buffering system. The key ideas to take away:

• A queue is FIFO: first in, first out. Use collections.deque in Python.
• A deque generalizes the queue to allow O(1) operations on both ends. It powers sliding window algorithms and many other patterns.
• A circular queue uses fixed memory and wraps around, making it ideal for bounded buffers.
• A priority queue orders by priority, not arrival time, and is built on a heap.

The next step is to practice. Start with the BFS problems — they build strong intuition for how queues drive exploration one level at a time. Then tackle the sliding window maximum to see the deque’s power. Once those feel natural, you will reach for the right queue variant without thinking twice.