Queue Data Structure Explained

Quick Reference

What Is a Queue?

A queue is a linear data structure that follows the FIFO principle — First In, First Out. The first element added is the first one removed, just like a line at a checkout counter.

Two ends:

• Front (head) — where elements leave (dequeue)
• Rear (tail) — where elements enter (enqueue)

  enqueue ──▶  [ A | B | C | D ]  ──▶ dequeue
               rear               front

Queue vs Stack

Implementation 1 — Naive Array (O(n) dequeue)

The simplest approach: append to enqueue, pop(0) to dequeue. Dequeue is O(n) because every element shifts left.

class NaiveQueue:
    def __init__(self):
        self._data = []

    def enqueue(self, val):
        self._data.append(val)          # O(1) amortised

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._data.pop(0)        # O(n) — every element shifts

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

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

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

Never use this in performance-critical code. Use collections.deque instead.

Implementation 2 — Python collections.deque (O(1) both ends)

Python's built-in deque (double-ended queue) uses a doubly-linked list of fixed-size blocks. Both append and popleft are O(1).

from collections import deque

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

    def enqueue(self, val):
        self._data.append(val)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._data.popleft()

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

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

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

# Usage
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.peek())     # 2
print(len(q))       # 2

Implementation 3 — Circular Array (fixed capacity, O(1) all ops)

When capacity is known in advance, a circular array wastes no space and has O(1) enqueue and dequeue with no shifting.

index: 0   1   2   3   4
       [D | E | _ | B | C]
              ↑         ↑
             rear      front

Wrap-around: (index + 1) % capacity

class CircularQueue:
    def __init__(self, capacity: int):
        self._cap = capacity
        self._data = [None] * capacity
        self._front = 0
        self._size = 0

    @property
    def _rear(self):
        return (self._front + self._size) % self._cap

    def enqueue(self, val):
        if self._size == self._cap:
            raise OverflowError("queue is full")
        self._data[self._rear] = val
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("dequeue from empty queue")
        val = self._data[self._front]
        self._data[self._front] = None          # help GC
        self._front = (self._front + 1) % self._cap
        self._size -= 1
        return val

    def peek(self):
        if self._size == 0:
            raise IndexError("peek from empty queue")
        return self._data[self._front]

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

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

    def __len__(self):
        return self._size

Implementation 4 — Linked List Queue (O(1), unbounded)

Linked list queues have O(1) enqueue and dequeue with no capacity limit. Extra memory per node (pointer overhead).

class _Node:
    __slots__ = ("val", "next")
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedQueue:
    def __init__(self):
        self._head = None   # front — dequeue here
        self._tail = None   # rear  — enqueue here
        self._size = 0

    def enqueue(self, val):
        node = _Node(val)
        if self._tail:
            self._tail.next = node
        self._tail = node
        if self._head is None:
            self._head = node
        self._size += 1

    def dequeue(self):
        if self._head is None:
            raise IndexError("dequeue from empty queue")
        val = self._head.val
        self._head = self._head.next
        if self._head is None:
            self._tail = None
        self._size -= 1
        return val

    def peek(self):
        if self._head is None:
            raise IndexError("peek from empty queue")
        return self._head.val

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

    def __len__(self):
        return self._size

JavaScript Implementation

class Queue {
  #data = [];
  #head = 0;       // pointer avoids O(n) shift

  enqueue(val) {
    this.#data.push(val);
  }

  dequeue() {
    if (this.isEmpty()) throw new Error("Queue is empty");
    const val = this.#data[this.#head];
    this.#head++;
    // Compact when wasted space > half the array
    if (this.#head > this.#data.length / 2) {
      this.#data = this.#data.slice(this.#head);
      this.#head = 0;
    }
    return val;
  }

  peek() {
    if (this.isEmpty()) throw new Error("Queue is empty");
    return this.#data[this.#head];
  }

  isEmpty() { return this.#head >= this.#data.length; }
  get size() { return this.#data.length - this.#head; }
}

const q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.dequeue()); // "a"
console.log(q.peek());    // "b"
console.log(q.size);      // 2

Java Implementation

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;

public class Queue<T> {
    private final Deque<T> deque = new ArrayDeque<>();

    public void enqueue(T val) {
        deque.addLast(val);
    }

    public T dequeue() {
        if (deque.isEmpty()) throw new NoSuchElementException();
        return deque.removeFirst();
    }

    public T peek() {
        if (deque.isEmpty()) throw new NoSuchElementException();
        return deque.peekFirst();
    }

    public boolean isEmpty() { return deque.isEmpty(); }
    public int size() { return deque.size(); }
}

Java tip: Use java.util.ArrayDeque as a queue — it is faster than LinkedList due to better cache locality.

Go Implementation

package queue

import "errors"

type Queue[T any] struct {
    data []T
    head int
}

func (q *Queue[T]) Enqueue(val T) {
    q.data = append(q.data, val)
}

func (q *Queue[T]) Dequeue() (T, error) {
    var zero T
    if q.IsEmpty() {
        return zero, errors.New("queue is empty")
    }
    val := q.data[q.head]
    q.data[q.head] = zero // help GC
    q.head++
    // Compact slice periodically
    if q.head > len(q.data)/2 {
        q.data = append([]T(nil), q.data[q.head:]...)
        q.head = 0
    }
    return val, nil
}

func (q *Queue[T]) Peek() (T, error) {
    var zero T
    if q.IsEmpty() {
        return zero, errors.New("queue is empty")
    }
    return q.data[q.head], nil
}

func (q *Queue[T]) IsEmpty() bool { return q.head >= len(q.data) }
func (q *Queue[T]) Len() int      { return len(q.data) - q.head }

Types of Queues

Deque (Double-Ended Queue)

A deque allows enqueue and dequeue at both ends.

from collections import deque

dq = deque()
dq.append(1)         # enqueue rear   → [1]
dq.appendleft(0)     # enqueue front  → [0, 1]
dq.append(2)         # enqueue rear   → [0, 1, 2]
print(dq.popleft())  # dequeue front  → 0, dq = [1, 2]
print(dq.pop())      # dequeue rear   → 2, dq = [1]

Use deque when you need:

• Sliding window operations (monotonic deque)
• BFS with bidirectional expansion
• LRU cache (deque of keys + dict)

Priority Queue

Elements are dequeued in priority order, not arrival order.

import heapq

class MinPriorityQueue:
    def __init__(self):
        self._heap = []

    def enqueue(self, priority, val):
        heapq.heappush(self._heap, (priority, val))

    def dequeue(self):
        if not self._heap:
            raise IndexError("empty")
        return heapq.heappop(self._heap)   # (priority, val)

    def peek(self):
        return self._heap[0]

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

pq = MinPriorityQueue()
pq.enqueue(3, "low")
pq.enqueue(1, "high")
pq.enqueue(2, "medium")
print(pq.dequeue())  # (1, 'high')
print(pq.dequeue())  # (2, 'medium')

For a max-priority queue, negate the priority: heappush(heap, (-priority, val)).

BFS — The Core Queue Use Case

Breadth-First Search visits all nodes at depth d before visiting depth d+1. A queue is essential — it preserves order.

from collections import deque

def bfs(graph: dict, start: int) -> list[int]:
    visited = {start}
    queue   = deque([start])
    order   = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

graph = {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []}
print(bfs(graph, 1))  # [1, 2, 3, 4, 5, 6]

Why a queue? Nodes enqueued earlier are visited earlier → level-by-level traversal.

6 Classic Interview Problems

1. Binary Tree Level-Order Traversal (LeetCode 102)

Return nodes level by level.

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Key pattern: Snapshot len(queue) at start of each iteration to know how many nodes belong to the current level.

2. Rotting Oranges (LeetCode 994)

Multi-source BFS — all rotten oranges start simultaneously.

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    fresh = 0
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))   # (row, col, minutes)
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while queue:
        r, c, t = queue.popleft()
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                minutes = t + 1
                queue.append((nr, nc, t + 1))

    return minutes if fresh == 0 else -1

3. Walls and Gates (LeetCode 286)

Fill each empty room with distance to nearest gate. Multi-source BFS from all gates at once.

from collections import deque

def walls_and_gates(rooms):
    INF = 2**31 - 1
    rows, cols = len(rooms), len(rooms[0])
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:           # gate
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

4. Implement Queue Using Two Stacks (LeetCode 232)

class MyQueue:
    def __init__(self):
        self._inbox  = []    # push here
        self._outbox = []    # pop from here

    def push(self, x: int) -> None:
        self._inbox.append(x)

    def _transfer(self):
        if not self._outbox:
            while self._inbox:
                self._outbox.append(self._inbox.pop())

    def pop(self) -> int:
        self._transfer()
        return self._outbox.pop()

    def peek(self) -> int:
        self._transfer()
        return self._outbox[-1]

    def empty(self) -> bool:
        return not self._inbox and not self._outbox

Amortized O(1) per operation: each element is moved at most once from inbox to outbox.

5. Sliding Window Maximum (LeetCode 239)

Find max in every window of size k. Uses a monotonic deque (decreasing order).

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()          # stores indices; front = current max
    result = []

    for i, num in enumerate(nums):
        # Remove indices outside window
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order — pop smaller values from rear
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        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]

Time: O(n) — each element enters and leaves deque at most once.

6. First Non-Repeating Character in a Stream (LeetCode 387 variant)

Process characters one by one; at each step report the first non-repeating char.

from collections import deque, Counter

def first_unique_char_stream(stream: str) -> list[str]:
    count = Counter()
    queue = deque()         # candidates; front = first unique so far
    result = []

    for ch in stream:
        count[ch] += 1
        queue.append(ch)
        # Evict front if it's no longer unique
        while queue and count[queue[0]] > 1:
            queue.popleft()
        result.append(queue[0] if queue else "#")

    return result

print(first_unique_char_stream("aabcbc"))
# ['a', '#', 'b', 'b', 'c', 'b']

Queue vs Stack vs Deque

When to Use a Queue

When NOT to Use a Queue

Real-World Analogy

Common Mistakes

Queue vs Related Structures

FAQ

Q: Which Python collection should I use as a queue?
collections.deque. Never use a plain list — pop(0) is O(n). deque.popleft() is O(1).

Q: When is a circular array better than a linked-list queue?
When capacity is bounded and you want better cache performance. No pointer overhead, contiguous memory. Use when you know max size upfront (e.g., fixed-size ring buffer).

Q: How is a priority queue different from a regular queue?
A regular queue dequeues in FIFO order. A priority queue dequeues the element with the highest (or lowest) priority, regardless of insertion order. Backed by a heap — O(log n) enqueue/dequeue instead of O(1).

Q: Can a queue be used for DFS?
No. DFS requires a stack (LIFO). Using a queue gives you BFS. A common interview mistake is accidentally getting BFS instead of DFS by choosing the wrong data structure.

Q: What is a monotonic deque?
A deque that maintains elements in increasing or decreasing order by removing dominated elements on enqueue. Used in sliding window maximum/minimum problems to achieve O(n) time instead of O(n·k).

Q: Queue using two stacks — what is the time complexity?
Amortized O(1) per operation. Each element is pushed to inbox once and popped to outbox at most once, giving O(1) amortized over a sequence of operations even though individual dequeue calls may cost O(n) when outbox is empty.