What Is a Queue? The Data Structure That Waits in Line

You've used a queue today. When you sent a print job and your document waited behind someone else's 47-page PDF. When your Spotify song buffered before playing. When an HTTP request sat in a server's backlog before a worker picked it up.

A queue is a data structure where items exit in the same order they entered. First in, first out. That's the whole idea. What makes it worth understanding is what you can build with it, how fast those operations run, and where it shows up in coding interviews.

One Rule: The Longest Waiter Goes Next

A queue enforces a single ordering constraint: the item that has waited the longest leaves next.

Think of a grocery store checkout line. The customer who joined first gets served first. No cutting. No priority based on basket size. Pure chronological order. (A priority queue breaks this rule, which is why it has a different name and a whole different section of interview prep hell.)

This is FIFO: First In, First Out. Contrast it with a stack, which is LIFO (Last In, First Out). A stack is a pile of plates where you grab from the top. A queue is a line where you join at the back and leave from the front. Sounds obvious until you're staring at a BFS problem at 11pm wondering why your results are wrong.

Four Operations, All O(1)

A queue exposes four operations, all with the same time complexity:

Operation	What it does	Time
`enqueue(item)`	Add item to the back	O(1)
`dequeue()`	Remove and return item from the front	O(1)
`peek()`	Return the front item without removing it	O(1)
`isEmpty()`	Check if the queue has no items	O(1)

Every operation is O(1). That's the guarantee that makes queues useful. You can process tasks as fast as they arrive without paying any cost for the queue itself. No "wait, let me reorganize first." Just in, out, done.

Space complexity is O(n) for n elements. The queue holds what you put in it.

Two Ways to Build It, One Right Answer for Production

Two implementations dominate in practice.

Linked list. Each node points to the next. You maintain a head pointer (front of the queue) and a tail pointer (back). Enqueue appends to the tail in O(1). Dequeue removes the head in O(1). Clean and simple, with a per-node allocation cost that hurts your cache.

Circular buffer (ring buffer). A fixed-size array with two indices, head and tail, that wrap around when they reach the array's end. Enqueue writes to tail and increments it (mod capacity). Dequeue reads from head and increments it (mod capacity). No shifting, no allocation overhead, O(1) everywhere. It sounds fancier than it is: it's just an array that thinks it's a circle.

The circular buffer is what most production queues use under the hood. Python's collections.deque, Java's ArrayDeque, and JavaScript's typed arrays all exploit this idea.

class Queue:
    def __init__(self, capacity: int):
        self.buffer = [None] * capacity
        self.head = 0
        self.tail = 0
        self.size = 0
        self.capacity = capacity

    def enqueue(self, item) -> None:
        if self.size == self.capacity:
            raise OverflowError("Queue is full")
        self.buffer[self.tail] = item
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("Queue is empty")
        item = self.buffer[self.head]
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return item

    def peek(self):
        if self.size == 0:
            raise IndexError("Queue is empty")
        return self.buffer[self.head]

    def is_empty(self) -> bool:
        return self.size == 0

The modulo trick (% self.capacity) is what makes it circular. The tail chases the head around the array forever without either pointer escaping the bounds.

The Python Trap Nobody Warns You About

If you use a Python list as a queue, you will regret it. Possibly in production. Definitely in an interview when your BFS times out with n=10,000.

# Wrong: O(n) dequeue
queue = []
queue.append(item)      # O(1) - fine
item = queue.pop(0)     # O(n) - shifts every remaining element left

# Right: O(1) dequeue
from collections import deque
queue = deque()
queue.append(item)      # O(1)
item = queue.popleft()  # O(1)

list.pop(0) is O(n) because Python has to shift every element down by one index. On a queue with 10,000 items, that's 10,000 operations per dequeue call. Your "O(n)" BFS suddenly becomes O(n²). This is the kind of bug that passes small test cases, gets submitted to LeetCode, and TLEs on the last two examples with no clear explanation of why.

Use collections.deque in Python. Always. It takes one import line and one word change. There is no excuse.

In TypeScript/JavaScript, arrays also have O(n) shift(). For interview problems where n is small, the array works fine in practice. For anything performance-sensitive, use a linked list or a proper ring buffer.

BFS Is Just a Queue in Disguise

Queues are not a pattern you recognize by the shape of a problem. They're the mechanism behind a pattern you almost certainly already know: breadth-first search.

BFS explores a graph level by level. It does that by processing all nodes at distance 1 before any at distance 2. To maintain that order, it needs a structure where the first node added is the first node processed. A queue.

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 neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

The queue here isn't incidental. If you swapped it for a stack, you'd get DFS. Change one data structure, get a completely different traversal. That's not a coincidence. The data structure determines the traversal order, which is why understanding the queue is the same as understanding why BFS finds shortest paths and DFS doesn't.

This is also why "just swap stack for queue" is one of the more satisfying tricks in interview prep. Same skeleton, different behavior.

The Three Moves You'll Actually Use in Interviews

1. Level-order tree traversal. Process a binary tree layer by layer. Enqueue the root, then for each node you dequeue, enqueue its children. Every time the queue empties, you've finished a level.

from collections import deque

def level_order(root) -> list[list[int]]:
    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

Snapshotting len(queue) at the start of each iteration is the trick. It tells you exactly how many nodes belong to the current level before their children arrive and contaminate the count.

2. Shortest path in an unweighted graph. BFS on a grid or adjacency list finds the minimum number of steps between two nodes. This is LeetCode 994 (Rotting Oranges), 127 (Word Ladder), and dozens more. The queue guarantees you explore closer nodes first, so the first time you reach the target, it's via the shortest path.

3. Multi-source BFS. Start BFS from multiple nodes simultaneously by enqueueing all sources before the main loop. The classic example: every rotten orange infects neighbors in parallel. Enqueue all rotten oranges at once, then BFS outward. The queue handles the parallelism naturally because FIFO processes all level-0 sources before any level-1 nodes. No threads required. No coordination required. Just a queue doing its job.

A One-Question Test for Picking the Right Structure

Ask yourself: does order matter, and is it the order things arrived?

If yes, queue. If you need the most recently added item, stack. If you need the most important item, heap. That's the whole decision tree. You don't need a flowchart.

More concretely: if you see "level by level," "shortest path," "process in order of arrival," or "simulate a waiting line," a queue is almost certainly the right structure.

If you need to add and remove from both ends (like a sliding window maximum), reach for a deque instead. A deque is a double-ended queue that supports O(1) operations at both the front and the back. Python's collections.deque is already a deque, so you're not switching libraries. You're just calling appendleft() and pop() instead of append() and popleft().

O(1) Means It Doesn't Slow Down. Ever.

O(1) per operation sounds obvious, but it means something concrete: a queue of one million items behaves exactly the same as a queue of ten. Enqueue and dequeue don't slow down as the queue grows. There's no secret O(log n) hiding in there. No periodic "compaction" phase. Just constant time, forever.

This is why queues are everywhere in systems. A web server's request queue processes request 1,000,000 just as fast as request 1. A message broker like Kafka doesn't slow down enqueue because there are a lot of messages waiting. The queue doesn't care how backed up it is.

Queue vs Stack: The Maze Test

Imagine you're exploring a maze from the entrance, looking for the exit.

A stack sends you racing down one corridor until you hit a dead end, then backtracks. You might find the exit quickly. You might explore the entire wrong half of the maze first. It depends on which way you turned.

A queue spreads outward evenly from the entrance, exploring every corridor one step at a time. Slower to go deep, but guaranteed to find the shortest path to the exit. You'll visit every dead end at distance 3 before you try any corridor at distance 4. Methodical. Thorough. The kind of approach that would drive an impatient person crazy but wins on worst-case guarantees.

Neither is better. They solve different problems. The queue's FIFO ordering is a feature, not a convenience.

If you want to see how queue-based reasoning plays out under interview pressure, SpaceComplexity runs voice-based mock interviews where you talk through BFS problems in real time and get rubric feedback on your thinking, not just your code.