Why should you care?
A queue is a fundamental data structure used whenever things need to be processed in the same order they arrive.
Unlike a stack, which follows Last In, First Out (LIFO), a queue follows:
First In, First Out (FIFO).
Queues appear in many real systems:
- Print job scheduling
- CPU task scheduling
- Network packet processing
- Customer service systems
- Message queues
- Breadth-First Search (BFS)
- Operating system process management
- Event handling
Understanding queues also introduces an important idea in computer science: how data structures can control the order in which work gets processed.
The Problem
Imagine several tasks arriving at a printer:
Document A
Document B
Document C
If Document C is printed before Document A, the system would be unfair.
We want the printer to process requests in the order they arrived:
A → B → C
So we need a data structure where:
The first element added is the first element removed.
That's exactly what a queue provides.
The Concept
A queue is a linear data structure that follows the FIFO principle:
First In
↓
First Out
A queue has two important ends:
- Front — where elements are removed
- Rear — where elements are added
For example:
FRONT REAR
↓ ↓
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘
↑ ↑
remove add
If we perform:
enqueue(50)
the queue becomes:
10 → 20 → 30 → 40 → 50
If we perform:
dequeue()
10 is removed:
20 → 30 → 40 → 50
The oldest element always leaves first.
Simple Explanation
Think of a queue as a line of people waiting for a service.
Suppose people arrive in this order:
Alice → Bob → Charlie
Alice arrived first, so she gets served first.
Then:
Bob → Charlie
Then:
Charlie
New people join at the back.
People leave from the front.
Queue
↓
Front Rear
↓ ↓
[Alice] → [Bob] → [Charlie] → [David]
↑ ↑
remove add
This is the essence of a queue.
Real-world Analogy
Imagine a ticket counter.
People arrive one after another:
Person 1
Person 2
Person 3
Person 4
They form a line:
┌───────┐
│Person1│ ← Front
└───────┘
↓
┌───────┐
│Person2│
└───────┘
↓
┌───────┐
│Person3│
└───────┘
↓
┌───────┐
│Person4│ ← Rear
└───────┘
Person 1 gets served first.
When Person 1 leaves, everyone else effectively moves toward the front.
A queue data structure follows the same logical rule:
Enqueue → join the rear
Dequeue → leave from the front
Code Example
In Java, a queue can be implemented using Queue and ArrayDeque.
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(10);
queue.offer(20);
queue.offer(30);
System.out.println(queue.peek());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}
Output:
10
10
20
Let's understand the operations.
Enqueue
Add an element:
queue.offer(10);
The queue becomes:
10
Then:
queue.offer(20);
becomes:
10 → 20
Then:
queue.offer(30);
becomes:
10 → 20 → 30
Peek
queue.peek();
returns:
10
but doesn't remove it.
Dequeue
queue.poll();
removes and returns:
10
The queue becomes:
20 → 30
So the basic operations are:
offer() → add
poll() → remove
peek() → inspect
Common Mistakes
Mistake 1: Confusing Queue with Stack
This is the most common mistake.
A queue uses:
FIFO
First In → First Out
A stack uses:
LIFO
Last In → First Out
Suppose we add:
10 → 20 → 30
A queue produces:
dequeue() → 10
A stack produces:
pop() → 30
The difference is fundamental:
Queue: → → → FIFO
Stack: → → → LIFO
Mistake 2: Removing from the wrong end
A queue should generally behave like:
REAR FRONT
↓ ↓
[30] ← [20] ← [10]
↑
remove
New elements enter from the rear.
Existing elements leave from the front.
If you add and remove from the same end, you're effectively implementing stack-like behavior rather than a conventional queue.
Mistake 3: Thinking peek() removes an element
Consider:
10 → 20 → 30
↑
FRONT
Calling:
queue.peek();
returns:
10
but the queue remains:
10 → 20 → 30
Calling:
queue.poll();
actually removes it:
20 → 30
So:
peek() → look
poll() → remove
Advanced Notes
1. Queue time complexity
A properly implemented queue typically provides:
| Operation | Time Complexity |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
| Search | O(n) |
This makes queues extremely efficient for processing data in arrival order.
2. Queue using an array
A naive array implementation might look like:
10 20 30 40
↑
FRONT
After removing 10:
_ 20 30 40
↑
FRONT
If we repeatedly remove elements, we could end up wasting space at the beginning of the array.
A better solution is a circular queue.
3. Circular queue
A circular queue treats the end of the array as connected back to the beginning:
┌────────────────────┐
↓ │
[0] [1] [2] [3] [4] │
└────────────────────────┘
For example:
Index: 0 1 2 3 4
┌───┬───┬───┬───┬───┐
│10 │20 │30 │40 │50 │
└───┴───┴───┴───┴───┘
↑ ↑
FRONT REAR
After reaching index 4, the rear can wrap back to index 0 if space is available.
This makes better use of fixed-size array storage.
4. Queue using a linked list
A queue can also be implemented using a linked list:
FRONT REAR
↓ ↓
[10] → [20] → [30] → [40] → null
When we enqueue:
[10] → [20] → [30] → [40] → [50]
↑
REAR
When we dequeue:
[20] → [30] → [40] → [50]
↑
FRONT
If both front and rear references are maintained, enqueue and dequeue can both be O(1).
5. Priority Queue
Not every queue processes elements strictly according to arrival time.
A priority queue processes elements according to their priority.
For example:
Normal task Priority: 1
Important task Priority: 5
Critical task Priority: 10
The critical task may be processed first even if it arrived later.
So:
Normal Queue:
First arrival → First processed
Priority Queue:
Highest priority → First processed
Priority queues are commonly implemented using heaps.
6. Deque
A deque (double-ended queue) allows insertion and removal from both ends.
FRONT REAR
↓ ↓
[10] ↔ [20] ↔ [30] ↔ [40]
↑ ↑
remove remove
/add /add
This makes a deque more flexible than a normal FIFO queue.
In Java:
Deque<Integer> deque = new ArrayDeque<>();
A deque can also be used to implement both:
- A queue
- A stack
The Bigger Picture
Queues are deeply connected to how real systems manage work over time.
A useful progression is:
Arrays
↓
Linked Lists
↓
Stacks / Queues
↓
Trees / Heaps
↓
Graphs
↓
Algorithms
Queues become particularly important in Breadth-First Search (BFS).
Consider:
A
/ \
B C
/ \
D E
BFS explores level by level:
A → B → C → D → E
A queue makes this possible.
Conceptually:
Queue
[A]
↓
Remove A
↓
Add B, C
↓
[B, C]
↓
Remove B
↓
Add D, E
↓
[C, D, E]
The queue ensures that nodes discovered earlier are processed before nodes discovered later.
Queues are also fundamental to operating systems, networking, distributed systems, and asynchronous programming.
For example:
Requests
↓
┌──────────────────┐
│ Request Queue │
├──────────────────┤
│ Request 1 │
│ Request 2 │
│ Request 3 │
└──────────────────┘
↓
Worker
The worker processes requests one at a time.
This same pattern appears in message brokers, web servers, task schedulers, and event-driven systems.
The Most Important Mental Model
A queue is a line: new elements join at the back, and the oldest element leaves from the front.
Remember:
ENQUEUE
↓
FRONT REAR
↓ ↓
[10] → [20] → [30] → [40] → [50]
↑
DEQUEUE
The golden rule is:
FIFO
First In → First Out
If you remember only one thing about queues, remember FIFO.
Summary
A queue is a linear data structure that processes elements according to the First In, First Out (FIFO) principle.
The key ideas are:
- Enqueue adds an element to the rear.
- Dequeue removes an element from the front.
- Peek examines the front without removing it.
- Enqueue and dequeue can both be O(1) with an appropriate implementation.
- Queues can be implemented using arrays or linked lists.
- Circular queues efficiently reuse array space.
- Priority queues process elements according to priority rather than arrival order.
- Deques allow operations at both ends.
- Queues are fundamental to BFS, scheduling, networking, and asynchronous systems.
A queue teaches one of the most important ideas in computing: when work arrives faster than it can be processed, a well-designed system needs a disciplined way to decide what gets handled next.
Top comments (0)