DSA Queues
DSA Queues – Complete Beginner Guide
(Concept • Types • Operations • Implementation • Examples • Complexity)
A Queue is a fundamental linear data structure in DSA that follows the FIFO principle.
FIFO = First In, First Out
1️⃣ What is a Queue?
A Queue is a data structure where:
-
Insertion happens at the rear
-
Deletion happens from the front
Real-Life Examples
-
People standing in a line
-
Ticket booking system
-
CPU task scheduling
-
Printer queue
2️⃣ Queue Terminology
| Term | Meaning |
|---|---|
| Front | First element |
| Rear | Last element |
| Enqueue | Insert element |
| Dequeue | Remove element |
| Overflow | Queue full |
| Underflow | Queue empty |
3️⃣ Basic Queue Operations
-
Enqueue – Insert element at rear
-
Dequeue – Remove element from front
-
Peek / Front – View front element
-
isEmpty – Check if empty
-
isFull – Check if full
4️⃣ Simple Queue (Array Implementation)
Code (C++)
5️⃣ Limitations of Simple Queue ❌
❌ Wastage of space after dequeuing
❌ Rear reaches end even if front has space
📌 Solution → Circular Queue
6️⃣ Circular Queue
Concept
-
Rear connects back to front
-
Uses modulo operation
%
Code (C++)
7️⃣ Queue Using Linked List
8️⃣ Types of Queues
| Type | Description |
|---|---|
| Simple Queue | Linear FIFO |
| Circular Queue | Last connects to first |
| Priority Queue | Higher priority served first |
| Deque | Insert/delete both ends |
9️⃣ Deque (Double Ended Queue)
-
Insert & delete from both ends
-
Two types:
-
Input Restricted
-
Output Restricted
-
📌 Used in sliding window problems.
🔟 Time Complexity of Queue Operations
| Operation | Time |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
| Search | O(n) |
1️⃣1️⃣ Queue Applications
✔ CPU scheduling
✔ BFS (Breadth First Search)
✔ Printer scheduling
✔ Network buffering
✔ Producer–Consumer problem
Interview Questions (Queue)
Q1. What is FIFO?
👉 First In First Out
Q2. Why circular queue is better than simple queue?
👉 Prevents memory wastage
Q3. Difference between queue & stack?
👉 FIFO vs LIFO
Final Summary
✔ Queue follows FIFO
✔ Insert at rear, delete from front
✔ Circular queue improves efficiency
✔ Linked list queue is dynamic
✔ Very important for DSA interviews
