Queue
A Queue is a linear data structure that follows:
FIFO — First In, First Out
This means:
The element that enters the queue first is removed first.
The easiest real-life example is a line of people.
Person A → Person B → Person C → Person D ↑ ↑ FRONT REAR
Person A came first, so Person A gets served first.
1. Understanding FIFO
Suppose we insert:
10 20 30 40
The queue becomes:
FRONT REAR ↓ ↓ ┌────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ └────┴────┴────┴────┘
Now we remove one element.
10 is removed because it entered first.
FRONT REAR ↓ ↓ ┌────┬────┬────┐ │ 20 │ 30 │ 40 │ └────┴────┴────┘
Remove again:
20
Then:
30
Then:
40
So:
Inserted: 10 → 20 → 30 → 40 Removed: 10 → 20 → 30 → 40
That's FIFO.
2. Queue vs Stack
You just learned Stack.
This difference is extremely important.
Stack
LIFO Last In → First Out
Example:
10 20 30 ← removed first
Queue
FIFO First In → First Out
Example:
10 → 20 → 30 ↑ removed first
Think:
Stack = pile of plates Queue = people standing in a line
3. Basic Queue Operations
A queue mainly has these operations:
| Operation | Meaning |
|---|---|
enqueue() | Add an element |
dequeue() | Remove an element |
front() | See the first element |
rear() / back() | See the last element |
empty() | Check if empty |
size() | Number of elements |
In C++'s STL queue, these operations are usually named:
q.push() q.pop() q.front() q.back() q.empty() q.size()
4. Enqueue
Enqueue means adding an element to the rear/back of the queue.
Initially:
EMPTY
Add 10:
FRONT ↓ ┌────┐ │ 10 │ └────┘ ↑ REAR
Add 20:
FRONT REAR ↓ ↓ ┌────┬────┐ │ 10 │ 20 │ └────┴────┘
Add 30:
FRONT REAR ↓ ↓ ┌────┬────┬────┐ │ 10 │ 20 │ 30 │ └────┴────┴────┘
So:
enqueue(10) enqueue(20) enqueue(30)
gives:
10 → 20 → 30 ↑ ↑ front rear
5. Dequeue
Dequeue means removing the element from the front.
Suppose:
FRONT REAR ↓ ↓ ┌────┬────┬────┐ │ 10 │ 20 │ 30 │ └────┴────┴────┘
Perform:
dequeue()
10 is removed.
Now:
FRONT REAR ↓ ↓ ┌────┬────┐ │ 20 │ 30 │ └────┴────┘
Another dequeue:
20
Now:
FRONT ↓ ┌────┐ │ 30 │ └────┘
6. Front
front() tells us the element at the beginning of the queue.
Suppose:
FRONT ↓ 10 → 20 → 30
Then:
q.front()
returns:
10
It does not remove 10.
7. Rear / Back
back() tells us the last element.
Suppose:
FRONT REAR ↓ ↓ 10 → 20 → 30 → 40
Then:
q.back()
returns:
40
Again, it doesn't remove the element.
8. Queue in C++
C++ provides a queue through the STL.
Include:
#include <queue>
Create:
queue<int> q;
Now we can use it.
9. Basic Queue Example
#include <iostream> #include <queue> using namespace std; int main() { queue<int> q; q.push(10); q.push(20); q.push(30); cout << q.front() << endl; cout << q.back() << endl; return 0; }
Output:
10 30
Because:
FRONT REAR ↓ ↓ 10 → 20 → 30
10. Removing Elements
Use:
q.pop();
Example:
queue<int> q; q.push(10); q.push(20); q.push(30); q.pop(); cout << q.front();
Output:
20
Because 10 was removed.
11. Important Difference: pop() Doesn't Return the Value
This is a common beginner mistake.
You might think:
int x = q.pop(); // ❌
But pop() doesn't return the removed value.
Instead:
int x = q.front(); q.pop();
Example:
int first = q.front(); q.pop(); cout << first;
This prints the removed element.
12. Checking Empty Queue
Use:
q.empty()
Example:
if(q.empty()) { cout << "Queue is empty"; } else { cout << "Queue is not empty"; }
It returns:
true
or:
false
13. Finding Queue Size
Use:
q.size()
Example:
queue<int> q; q.push(10); q.push(20); q.push(30); cout << q.size();
Output:
3
14. Printing a Queue
Suppose:
10 → 20 → 30 → 40
We can process it:
while(!q.empty()) { cout << q.front() << " "; q.pop(); }
Output:
10 20 30 40
But remember:
This empties the queue.
If you want to preserve the original queue, use a copy:
queue<int> temp = q;
Then process temp.
15. Queue Complexity
For a proper queue implementation:
| Operation | Time |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Front | O(1) |
| Back | O(1) |
| Empty | O(1) |
| Size | O(1) |
This is the main reason queues are useful.
16. Queue Using an Array
We can implement a queue using an array.
For example:
int q[5];
We need to track:
front rear
Conceptually:
FRONT REAR ↓ ↓ ┌────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ │ │ └────┴────┴────┴────┴────┘
Here:
front = 0 rear = 2
17. Simple Array Queue
Initially:
front = 0 rear = -1
When inserting:
q[++rear] = 10;
Then:
front = 0 rear = 0
Queue:
10
Insert 20:
q[++rear] = 20;
Now:
10 20 ↑ ↑ F R
Insert 30:
10 20 30 ↑ ↑ F R
18. Problem With a Simple Array Queue
Suppose capacity is 5:
10 20 30 40 50 ↑ ↑ F R
Now remove:
10 20 30
We logically have:
40 50
But the beginning positions are unused.
[10][20][30][40][50] ↑ ↑ ↑ ↑ ↑ used unused
If rear has already reached the end, a simple array implementation may incorrectly think the queue is full.
This leads to the idea of a:
Circular Queue
19. Circular Queue
A circular queue treats the array as if the end connects back to the beginning.
Imagine:
┌───────────────┐ ↓ │ [0] → [1] → [2] → [3] → [4] ↑ │ └───────────────────────┘
After reaching the last position, we can go back to index 0.
This allows us to reuse empty spaces.
Circular queues are very important when learning queue implementations.
20. Queue Using Linked List
Since you just learned linked lists, you can also implement a queue using them.
Suppose:
FRONT ↓ 10 → 20 → 30 → NULL ↑ REAR
For a queue:
- Insert at the rear
- Remove from the front
21. Enqueue Using Linked List
Initially:
FRONT = NULL REAR = NULL
Insert 10:
FRONT ↓ 10 ↑ REAR
Insert 20:
FRONT REAR ↓ ↓ 10 → 20 → NULL
Insert 30:
FRONT REAR ↓ ↓ 10 → 20 → 30 → NULL
If we maintain both front and rear, insertion at the end is:
O(1)
22. Dequeue Using Linked List
Suppose:
FRONT ↓ 10 → 20 → 30 ↑ REAR
Remove from front:
10
Now:
FRONT ↓ 20 → 30 ↑ REAR
This is:
O(1)
So a linked-list queue can have:
enqueue → O(1) dequeue → O(1)
when front and rear pointers are maintained.
23. Real-Life Examples of Queues
Queues are everywhere.
1. Printer Queue
Suppose three documents are sent:
Document A Document B Document C
The printer generally processes:
A → B → C
First submitted, first processed.
2. CPU Scheduling
Processes may wait for CPU resources:
Process A → Process B → Process C
A scheduling algorithm decides which process gets CPU time.
Queues are fundamental to many scheduling systems.
3. Customer Service
Customer A Customer B Customer C
Usually:
A → B → C
4. Network Packets
Routers and network devices can queue packets when traffic arrives faster than it can be processed.
Packet 1 Packet 2 Packet 3 Packet 4 ↓ Processing
5. Breadth-First Search
This is extremely important for DSA.
BFS — Breadth-First Search uses a queue.
For example, in a graph:
A / \ B C / \ D E
BFS processes:
A → B → C → D → E
A queue helps maintain the order.
You'll encounter this later in your Graphs and Graph Traversal topics.
24. Queue and BFS
Suppose we start at A.
Initially:
Queue: A
Process A:
A is removed Queue: B C
Process B:
B is removed Queue: C D E
Process C:
C is removed Queue: D E
And so on.
That's why BFS naturally uses:
Queue
while DFS commonly uses:
Stack
or recursion.
25. Queue vs Stack
This is worth memorizing:
STACK TOP ↓ ┌────┐ │ 30 │ ← last in ├────┤ │ 20 │ ├────┤ │ 10 │ ← first in └────┘ Removal → 30
Queue:
QUEUE FRONT REAR ↓ ↓ ┌────┬────┬────┐ │ 10 │ 20 │ 30 │ └────┴────┴────┘ ↓ Removal → 10
Remember:
Stack → LIFO Queue → FIFO
26. Deque
There is a special type of queue called a:
Deque — Double-Ended Queue
Pronounced commonly as:
"deck"
Unlike a normal queue, a deque allows insertion and deletion from both ends.
FRONT REAR ↓ ↓ 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50 ↑ ↑ insert/delete insert/delete
So:
Queue: Insert → rear Delete → front
while:
Deque: Insert → front/rear Delete → front/rear
Deque is actually the next topic in your roadmap.
27. Priority Queue
Another important queue type is:
Priority Queue
A normal queue generally follows:
First In → First Out
A priority queue instead processes elements based on priority.
For example:
Patient A → priority 2 Patient B → priority 5 Patient C → priority 1
A higher-priority patient may be processed first.
In C++:
priority_queue<int> pq;
This will be covered later in your roadmap after Heap.
28. Queue Types
You should know these names:
Queue │ ├── Simple / Linear Queue │ ├── Circular Queue │ ├── Deque │ └── Priority Queue
Each has a different purpose.
29. Queue Overflow and Underflow
Just like stacks, queues can have:
Overflow
Trying to insert into a full fixed-size queue.
Queue full ↓ enqueue() ↓ Overflow
Underflow
Trying to remove from an empty queue.
Queue empty ↓ dequeue() ↓ Underflow
Remember:
Overflow → too much data / no available capacity Underflow → trying to remove when nothing exists
30. Important C++ queue Functions
For:
queue<int> q;
Remember:
q.push(x); // Add to rear q.pop(); // Remove from front q.front(); // First element q.back(); // Last element q.empty(); // Check empty q.size(); // Number of elements
Example:
q.push(10); q.push(20); q.push(30); cout << q.front(); // 10 cout << q.back(); // 30 q.pop(); cout << q.front(); // 20
31. A Complete Example
#include <iostream> #include <queue> using namespace std; int main() { queue<int> q; // Enqueue q.push(10); q.push(20); q.push(30); q.push(40); cout << "Front: " << q.front() << endl; cout << "Rear: " << q.back() << endl; // Dequeue q.pop(); cout << "After removing front: " << q.front() << endl; cout << "Size: " << q.size() << endl; return 0; }
Output:
Front: 10 Rear: 40 After removing front: 20 Size: 3
32. Important Complexity
For a properly implemented queue:
Enqueue → O(1) Dequeue → O(1) Front → O(1) Rear → O(1) Empty → O(1) Size → O(1)
But implementation matters.
For example, if you implement a queue using an ordinary array and shift every element after deletion:
[10][20][30][40] remove 10 [20][30][40]
and physically shift everything, deletion can become:
O(n)
A good queue implementation avoids unnecessary shifting, often using a circular array, linked list, or the STL queue.
33. The Most Important Mental Model
Think about a ticket counter:
SERVICE ↓ FRONT REAR ↓ ↓ ┌────┬────┬────┬────┐ │ A │ B │ C │ D │ └────┴────┴────┴────┘
A came first.
So:
A → removed first B → removed second C → removed third D → removed fourth
New people enter from the rear:
A B C D → E
They don't jump ahead.
That's exactly:
FIFO — First In, First Out.
Final Summary
Queue
FIFO First In → First Out
Main operations
push/enqueue → add at rear pop/dequeue → remove from front front() → first element back() → last element empty() → check empty size() → number of elements
Visual
QUEUE FRONT REAR ↓ ↓ ┌────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┴────┘ ↓ ↑ remove add
Important applications
- Printer queues
- CPU/process scheduling
- Customer service
- Network packet processing
- BFS / graph traversal
- Task scheduling
Important types
Queue ├── Linear Queue ├── Circular Queue ├── Deque └── Priority Queue
And the most important comparison:
STACK QUEUE LIFO FIFO Last In First In ↓ ↓ First Out First Out push/pop at top add at rear remove at front