Chapter 17: DSA Queues
DSA Queues – Let’s understand this topic properly, like I’m sitting next to you explaining it step by step with a whiteboard, real-life examples, memory visuals, different implementations, code, common mistakes, and most importantly — when and why queues are actually used in programming and interviews.
What is a Queue?
A Queue is a linear data structure that follows FIFO (First In, First Out) principle.
Very simple meaning:
The first element that enters the queue is the first one that leaves the queue.
It behaves exactly like a normal queue/line of people in real life:
- New person joins at the back (called rear or tail)
- Person who gets served leaves from the front (called front or head)
- You cannot remove someone from the middle or serve someone who came later first
Real-life examples of Queue (very important to build intuition)
| Situation | How it works like a queue | Operation mapping |
|---|---|---|
| People standing in line at a ticket counter | First person who came gets ticket first | Enqueue = new person joins back, Dequeue = person at front leaves |
| Printer jobs | First document sent to printer is printed first | Enqueue = send document, Dequeue = print next |
| Customer support call center | First caller in line gets answered first | Enqueue = new call arrives, Dequeue = answer call |
| Breadth-First Search (BFS) | Visit nodes level by level | Enqueue = add neighbors, Dequeue = process current |
| Streaming video buffer | Oldest frames are played first | Enqueue = new data arrives, Dequeue = play next frame |
| Operating system process scheduling (FCFS) | First process in ready queue gets CPU | Enqueue = process becomes ready, Dequeue = CPU assigned |
| WhatsApp message queue (simplified) | Messages are delivered in the order sent | Enqueue = send message, Dequeue = deliver next |
Core Operations of Queue (must know perfectly)
| Operation | Description | Common Name | Time Complexity (good implementation) |
|---|---|---|---|
| Enqueue | Add element to the rear | enqueue / add / offer | O(1) |
| Dequeue | Remove & return element from front | dequeue / poll / remove | O(1) |
| Front / Peek | Look at the front element (without removing) | front / peek | O(1) |
| isEmpty | Check if queue has no elements | isEmpty | O(1) |
| Size | Number of elements currently in queue | size / length | O(1) |
Queue Implementations – Most important ones for interviews
1. Using Array (Naive version – bad for repeated dequeue)
Python
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# This version is WRONG for serious use (shown only to explain problem) class BadQueue: def __init__(self): self.items = [] def enqueue(self, value): self.items.append(value) # add to end def dequeue(self): if not self.is_empty(): return self.items.pop(0) # remove from front → O(n) !!! return "Queue is empty" |
Problem: pop(0) in Python (or shifting in C++/Java) is O(n) because all elements must move forward.
2. Circular Queue using Array (best for interviews – O(1) for both)
Python
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
class CircularQueue: def __init__(self, capacity): self.capacity = capacity self.queue = [None] * capacity self.front = 0 self.rear = -1 self.current_size = 0 def enqueue(self, value): if self.current_size == self.capacity: print("Queue is full") return False self.rear = (self.rear + 1) % self.capacity self.queue[self.rear] = value self.current_size += 1 return True def dequeue(self): if self.is_empty(): print("Queue is empty") return None value = self.queue[self.front] self.front = (self.front + 1) % self.capacity self.current_size -= 1 return value def get_front(self): if self.is_empty(): return None return self.queue[self.front] def is_empty(self): return self.current_size == 0 def is_full(self): return self.current_size == self.capacity def display(self): if self.is_empty(): print("Queue is empty") return print("Queue (front → rear): ", end="") i = self.front for _ in range(self.current_size): print(self.queue[i], end=" ") i = (i + 1) % self.capacity print() |
Memory view after some operations (capacity = 5)
text
|
0 1 2 3 4 5 6 7 8 9 10 11 |
front = 2, rear = 0, size = 4 Index: 0 1 2 3 4 Value: 40 - 10 20 30 ↑front ↑rear (wrapped around) |
This is why it’s called circular — rear wraps around to beginning when it reaches end.
3. Best in practice (Python) – collections.deque
Python
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
from collections import deque q = deque() # Enqueue q.append(10) # add to right (rear) q.append(20) q.appendleft(5) # add to left (front) – if needed # Dequeue print(q.popleft()) # 5 → remove from front print(q.pop()) # 20 → remove from rear print(list(q)) # [10] |
deque is double-ended queue — gives O(1) operations on both ends.
Very Common Interview Questions on Queue
| Level | Question examples (very frequently asked) |
|---|---|
| Easy | Implement queue using array / linked list |
| Easy | Implement circular queue |
| Medium | Implement stack using queue (and vice-versa) |
| Medium | Level order traversal of binary tree |
| Medium | First non-repeating character in stream |
| Medium | Sliding window maximum |
| Medium | Rotten Oranges / Multi-source BFS |
| Hard | Design Circular Queue (LeetCode 622) |
| Hard | Moving Average from Data Stream |
| Hard | Generate Binary Numbers from 1 to n using queue |
Queue vs Stack – Quick Comparison (very common interview question)
| Feature | Queue | Stack |
|---|---|---|
| Principle | FIFO | LIFO |
| Real-life example | Ticket queue | Pile of plates |
| Add operation | Enqueue (rear) | Push (top) |
| Remove operation | Dequeue (front) | Pop (top) |
| Main algorithm usage | BFS, level order | DFS, recursion, undo |
| Typical implementation | Circular array / deque | Array / Linked List |
| Access point | Front & Rear | Only Top |
Summary – Queue in one line each
- Follows FIFO (First In First Out) rule
- Main operations: enqueue, dequeue, front, isEmpty
- All core operations should be O(1) in good implementation
- Used everywhere: BFS, level order traversal, scheduling, buffering, producer-consumer problems
- Most practical implementation: circular array or deque
- One of the first data structures you should master deeply
- Basis for many medium & hard interview problems (especially graph/tree traversal)
Would you like to continue with any of these next topics?
Popular follow-ups:
- Implement Queue using Stack (classic interview question)
- Implement Stack using Queue
- Level Order Traversal of Binary Tree (very common queue application)
- Sliding Window Maximum (deque pattern)
- Circular Queue detailed dry run with all cases (full, empty, wrap-around)
- Difference between normal queue vs circular queue vs priority queue
Just tell me which one you want next — I’ll explain it in the same detailed, friendly way! 😊
