Queue
Last updated
A queue has two live ends. New values join at the rear, and values leave from the front, so whatever waited longest is served first. That is FIFO, and it is exactly how a line at a counter behaves: joining at the back and being served from the front is what makes the wait fair. Press Play above and watch values enter on one side and leave from the other.
Because each end is tracked by its own index or pointer, both operations are O(1) and neither one shifts the rest of the data. That is why queues sit under anything that processes work in arrival order: print jobs, task and message queues, request buffers, and breadth-first search, which visits a graph level by level precisely because it keeps its frontier in a queue. Move the removal end to the back and you have a stack instead.
Time & space complexity
For a queue backed by a ring buffer or a linked list, the two standard implementations:
| Operation | Complexity | Notes |
|---|---|---|
| Enqueue | O(1) | Write at the rear and advance the rear index. |
| Dequeue | O(1) | Read at the front and advance the front index, with no shifting. |
| Peek (front) | O(1) | Read the front value without removing it. |
| Search | O(n) | Not what a queue is for: you must drain it to look inside. |
| Space | O(n) | One slot per waiting value. |
Step by step
| Step | What happens |
|---|---|
| 1 | The queue starts empty, with front and rear pointing at the same slot. |
| 2 | Enqueue writes the value at the rear, then advances the rear by one. |
| 3 | Each further enqueue lands behind the values already waiting. |
| 4 | Dequeue reads the value at the front, then advances the front by one. |
| 5 | The value that comes back is always the one that has waited longest. |
| 6 | When front meets rear the queue is empty again, and dequeueing further is an error. |
Worked example
Enqueueing 3, 7, 5 and then draining the queue:
| Operation | Queue (front to rear) | Returns |
|---|---|---|
enqueue(3) | [3] | nothing |
enqueue(7) | [3, 7] | nothing |
enqueue(5) | [3, 7, 5] | nothing |
dequeue() | [7, 5] | 3, the oldest value |
dequeue() | [5] | 7 |
dequeue() | [] | 5, the newest value, last |
When to use a queue
| Use it when | Avoid it when |
|---|---|
| Work must be handled in arrival order: job queues, request buffers, print spoolers | You need the most recent item first, which is a stack |
| You are exploring level by level, as breadth-first search does | Items must be served by priority rather than arrival, where a heap fits |
| A producer and a consumer run at different speeds and need a buffer between them | You need to search or index into the middle of the data |
You want O(1) insertion and removal without shifting elements | You would implement it by shifting an array on every dequeue, which makes it O(n) |
Queue code
A clean, runnable Queue implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Queue code in Python
Python
1from collections import deque2
3queue = deque()4
5# Enqueue three values at the rear6for value in [3, 7, 5]:7 queue.append(value)8 print(f"enqueue {value} -> {list(queue)}")9
10# Dequeue them from the front: first in, first out11while queue:12 value = queue.popleft()13 print(f"dequeue {value} -> {list(queue)}")14
15print("empty:", len(queue) == 0)Queue code in JavaScript
JavaScript
1// A plain array makes dequeue O(n): shift() moves every element left.2// Track a head index instead, the fix the queue article describes.3const queue = { items: [], head: 0 };4
5function enqueue(value) {6 queue.items.push(value);7}8
9function dequeue() {10 const value = queue.items[queue.head];11 queue.items[queue.head] = undefined; // free the slot12 queue.head += 1;13 // Reclaim space once the consumed prefix dominates.14 if (queue.head * 2 >= queue.items.length) {15 queue.items = queue.items.slice(queue.head);16 queue.head = 0;17 }18 return value;19}20
21const size = () => queue.items.length - queue.head;22
23for (const value of [3, 7, 5]) {24 enqueue(value);25 console.log(`enqueue ${value} -> size ${size()}`);26}27
28// Dequeue from the front: first in, first out, amortized O(1)29while (size() > 0) {30 console.log(`dequeue ${dequeue()} -> size ${size()}`);31}32
33console.log('empty:', size() === 0);Queue code in Java
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 public static void main(String[] args) {6 Queue<Integer> queue = new ArrayDeque<>();7
8 // Enqueue three values at the rear9 for (int value : new int[] {3, 7, 5}) {10 queue.add(value);11 System.out.println("enqueue " + value + " -> " + queue);12 }13
14 // Dequeue them from the front: first in, first out15 while (!queue.isEmpty()) {16 int value = queue.remove();17 System.out.println("dequeue " + value + " -> " + queue);18 }19
20 System.out.println("empty: " + queue.isEmpty());21 }22}Queue code in C++
C++
1#include <iostream>2#include <queue>3
4int main() {5 std::queue<int> queue;6
7 // Enqueue three values at the rear8 for (int value : {3, 7, 5}) {9 queue.push(value);10 std::cout << "enqueue " << value << " -> size " << queue.size() << "\n";11 }12
13 // Dequeue them from the front: first in, first out14 while (!queue.empty()) {15 int value = queue.front();16 queue.pop();17 std::cout << "dequeue " << value << " -> size " << queue.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << queue.empty() << "\n";21 return 0;22}Queue code in C
C
1#include <stdio.h>2
3#define CAP 164
5int queue[CAP];6int front = 0;7int rear = 0; /* index of the next free slot */8
9int main(void) {10 int values[3] = {3, 7, 5};11
12 /* Enqueue three values at the rear */13 for (int i = 0; i < 3; i++) {14 queue[rear++] = values[i];15 printf("enqueue %d -> size %d\n", values[i], rear - front);16 }17
18 /* Dequeue them from the front: first in, first out */19 while (front < rear) {20 int value = queue[front++];21 printf("dequeue %d -> size %d\n", value, rear - front);22 }23
24 printf("empty: %d\n", front == rear);25 return 0;26}Queue FAQ
What does FIFO mean?
First in, first out: the value that has waited longest is the next one served. A line at a ticket counter is the everyday picture. A stack is the opposite discipline, LIFO.
What is the difference between a queue and a stack?
Only which end you remove from. Both add at the rear in
O(1); a queue removes from the front (FIFO), a stack removes from the same end it added to (LIFO). Their complexity tables are otherwise identical.What are the main queue operations?
enqueue adds a value at the rear, dequeue removes and returns the front value, peek (or front) reads the front without removing it, and is_empty reports whether anything is waiting. All four are O(1).Why is dequeue slow if I use a plain array?
Because removing index 0 from an array shifts every remaining element left, making each dequeue
O(n). Real implementations avoid this with a ring buffer that advances a front index, or a linked list with a head pointer. Python's collections.deque and Java's ArrayDeque do this for you, while list.pop(0) does not.What is a circular queue?
A queue in a fixed-size array where the front and rear indices wrap back to 0 when they run off the end. It reuses the slots freed by dequeues, so a queue of capacity
n keeps working indefinitely instead of walking off the end of the array.Where are queues used in real programs?
Task and message queues between services, print and job spoolers, request buffers in web servers, keyboard and event buffers, producer-consumer pipelines, and breadth-first search, where the queue is what makes the traversal go level by level.
Related resources
More visualizations
