Beginner·1 min read
Queues & Variants
Master FIFO queues, priority queues, and deques.
Queues & Variants
A queue follows First In, First Out (FIFO) - like a line at a store.
``
Enqueue(10), Enqueue(20), Enqueue(30):
Front → [10] [20] [30] ← Rear
Dequeue from here → Enqueue here
`
Queue Variants
Header Type Description Use Case
Header Simple Queue FIFO Print queue, BFS Circular Queue Wrap-around array Buffer, scheduling Priority Queue Highest priority first Dijkstra, heap sort Deque Double-ended queue Palindrome check, sliding window
Circular Queue
Uses modular arithmetic to reuse empty spaces at the front:
`
front = (front + 1) % capacity
rear = (rear + 1) % capacity
`
Deque (Double-Ended Queue)
Insert and delete from both ends in O(1):
`
Push_front(10) Push_back(20) Push_back(30)
[10] [20] [30]
Pop_front() → returns 10
[20] [30]
``
Applications
- BFS traversal: Process nodes level by level
- Sliding window maximum: Use deque to maintain window
- Task scheduling: OS process scheduling
- Web server request handling: FIFO request processing
Code Example
python
from collections import deque
# Simple Queue
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.is_empty():
raise IndexError("Dequeue from empty queue")
return self.items.popleft()
def front(self):
if self.is_empty():
raise IndexError("Front of empty queue")
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Sliding window maximum using deque
def max_sliding_window(nums, k):
dq = deque()
result = []
for i, num in enumerate(nums):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Output: [3, 3, 5, 5, 6, 7]Practice Problems
- 01Implement a circular queue using an array
- 02Generate binary numbers from 1 to n using a queue
- 03Implement a stack using two queues