Linear Data Structures
Queues
A First-In-First-Out (FIFO) collection: enqueue at the rear, dequeue from the front.
1Introduction
Queues model fairness: whoever arrives first is served first. They appear wherever work must be processed in arrival order — CPU scheduling, printers, message brokers and breadth-first search.
2What is it?
A queue is a linear collection where elements are added at the rear (enqueue) and removed from the front (dequeue). The first element in is the first out — FIFO.
3Why do we use it?
- O(1) enqueue and dequeue (with the right implementation).
- Preserves arrival order.
- Core of BFS and level-order traversal.
- Buffers producers and consumers running at different speeds.
4Real-world examples
- A ticket counter line.
- Print jobs waiting for the printer.
- Customer support call queue.
- Keyboard buffer.
5Internal working
A naive array queue removes from index 0 and shifts everything left — O(n) per dequeue.
A circular buffer keeps `front` and `rear` indexes and advances them with (index + 1) % capacity, reusing freed slots. Both operations become O(1).
Linked-list queues keep head (front) and tail (rear) pointers.
6Memory representation
Circular queue, capacity 4, after enqueue 10, 20, 30, dequeue, enqueue 40, 50 (rear wrapped):
index: 0 1 2 3
+------+------+------+------+
data: | 50 | 20 | 30 | 40 |
+------+------+------+------+
^ ^
rear front size = 4 (full)7Operations
| Operation | How it works |
|---|---|
| enqueue(x) | Add at rear. |
| dequeue() | Remove from front. |
| peek() | Read front. |
| isEmpty / isFull | Compare size with 0 / capacity. |
8Visual explanation
Size 0 / 4 · FIFO — values leave in the same order they arrived
A queue is First-In-First-Out (FIFO): enqueue adds at the rear, dequeue removes from the front. This circular-array queue wraps the rear pointer around to reuse freed slots.
9Code implementation
Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.
class Queue {
constructor(capacity) {
this.data = new Array(capacity).fill(null);
this.capacity = capacity;
this.front = 0;
this.rear = -1;
this.size = 0;
}
enqueue(value) {
if (this.size === this.capacity) {
console.log("Queue Overflow: cannot enqueue " + value);
return;
}
this.rear = (this.rear + 1) % this.capacity;
this.data[this.rear] = value;
this.size++;
}
dequeue() {
if (this.size === 0) {
console.log("Queue Underflow: nothing to dequeue");
return null;
}
const value = this.data[this.front];
this.data[this.front] = null;
this.front = (this.front + 1) % this.capacity;
this.size--;
return value;
}
toArray() {
const out = [];
for (let k = 0; k < this.size; k++) out.push(this.data[(this.front + k) % this.capacity]);
return out;
}
}
const queue = new Queue(4);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log("Dequeued:", queue.dequeue());
queue.enqueue(40);
queue.enqueue(50);
queue.enqueue(60);
console.log("Dequeued:", queue.dequeue());
console.log("Dequeued:", queue.dequeue());
console.log("Queue (front -> rear):", queue.toArray());
10Time complexity
| Operation | Time |
|---|---|
| enqueue(x) | O(1) |
| dequeue() | O(1) |
| peek() | O(1) |
| isEmpty / isFull | O(1) |
11Space complexity
A queue with n elements uses O(n) space; a circular buffer uses exactly its fixed capacity.
12Advantages
- Fair FIFO ordering.
- Constant-time operations.
- Natural fit for BFS and scheduling.
13Disadvantages
- No access to middle elements.
- Fixed-capacity circular queues can fill up.
- Naive array implementations are O(n) per dequeue.
14Common mistakes
- Using array.shift() in JavaScript or list.pop(0) in Python — both are O(n). Use a deque or circular buffer.
- Confusing the full and empty conditions in a circular buffer (track size explicitly).
- Forgetting the modulo when advancing front/rear.
- Marking BFS nodes visited on dequeue instead of on enqueue (duplicates in the queue).
15Interview questions
16Practice exercises
- Design a circular queue.
- Implement a stack using two queues.
- Generate binary numbers from 1 to n using a queue.
- First non-repeating character in a stream.
Try them in the Coding Playground.