Computer Science › Data Structures

Queue

A first-in, first-out collection.

Also known as: FIFO, queue data structure, deque

A queue is a collection where the first item added is the first one removed (FIFO: first in, first out). Like a line at a shop, people are served in the order they arrived.

from collections import deque

q = deque()
q.append("a")            # enqueue at the back
q.append("b")
q.popleft()              # dequeue from the front → "a"
q[0]                     # peek at the front → "b"

const q = [];
q.push("a");
q.shift();               // works, but shift on a big array is slow

Operations: enqueue (add at the back), dequeue (remove from the front), peek, and is empty. All should be constant time.

Implementing it

• A linked list with a head and a tail.
• A ring buffer (a fixed array used in a circle), efficient and common.
• Don’t use a plain list and remove from the front, which shifts every element (linear time). Use a deque.

Where you meet them

• Breadth-first search in graphs and level-order tree traversals.
• Task scheduling: jobs waiting for a worker (background jobs).
• Message queues between services, a distributed version of the same idea (message queues).
• Buffers: keyboard input, network packets, streaming data.
• Rate limiting and fair processing.

Variants

• Deque (double-ended queue): add and remove at both ends.
• Priority queue: items come out by priority, not arrival.
• Bounded queue: a maximum size, which forces a choice when full: block, drop or reject (backpressure).

Compare with the stack, which is last-in, first-out.