Queues — FIFO, Priority & Deque Guide
In this tutorial, you'll learn about Queues. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle — the first element added is the first one removed. Think of a line at a ticket counter: the first person in line gets served first.
What You'll Learn
You will learn queue operations (enqueue, dequeue, front), array-based and linked-list-based implementations, circular queues, priority queues, and deques with real-world applications.
Why It Matters
Queues manage tasks in order of arrival — print spools, message brokers, BFS traversal, and request handling all rely on queues. Understanding queues helps you design fair and predictable systems.
Real-World Use
The Doda Browser's event loop uses a task queue. When you click a button, the click event is enqueued and processed in FIFO order. Network requests are managed via a priority queue — critical requests (page loads) jump ahead of non-critical ones (image prefetching).
Queue Operations
All operations are O(1) amortized with an efficient implementation:
from collections import deque
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 from empty queue")
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print("Front:", q.front())
print("Dequeue:", q.dequeue())
print("Dequeue:", q.dequeue())
print("Size:", q.size())
Expected output:
Front: 10
Dequeue: 10
Dequeue: 20
Size: 1
class Queue {
constructor() { this.items = []; }
enqueue(item) { this.items.push(item); }
dequeue() {
if (this.isEmpty()) throw new Error("dequeue from empty queue");
return this.items.shift();
}
front() {
if (this.isEmpty()) throw new Error("front from empty queue");
return this.items[0];
}
isEmpty() { return this.items.length === 0; }
size() { return this.items.length; }
}
let q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
console.log("Front:", q.front());
console.log("Dequeue:", q.dequeue());
console.log("Dequeue:", q.dequeue());
console.log("Size:", q.size());
Expected output:
Front: 10
Dequeue: 10
Dequeue: 20
Size: 1
Linked List Queue Implementation
Using a Linked List avoids the O(n) shift() cost in JavaScript arrays:
class QueueNode:
def __init__(self, data):
self.data = data
self.next = None
class LinkedListQueue:
def __init__(self):
self.front = None
self.rear = None
self.length = 0
def enqueue(self, data):
node = QueueNode(data)
if self.is_empty():
self.front = self.rear = node
else:
self.rear.next = node
self.rear = node
self.length += 1
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty queue")
data = self.front.data
self.front = self.front.next
self.length -= 1
if self.is_empty():
self.rear = None
return data
def peek_front(self):
if self.is_empty():
raise IndexError("empty queue")
return self.front.data
def is_empty(self):
return self.front is None
def size(self):
return self.length
Queue Flow Diagram
graph LR
A[Enqueue 10] --> B[Enqueue 20] --> C[Enqueue 30]
D[Front: 10] --> E[Dequeue: 10] --> F[New Front: 20]
style D fill:#4a90d9,stroke:#333,color:#fff
style E fill:#e67e22,stroke:#333,color:#fff
Circular Queue
A circular queue reuses array space by wrapping around. When the tail reaches the end, it continues from index 0.
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.items = [None] * capacity
self.head = 0
self.tail = 0
self.count = 0
def enqueue(self, item):
if self.count == self.capacity:
raise OverflowError("queue is full")
self.items[self.tail] = item
self.tail = (self.tail + 1) % self.capacity
self.count += 1
def dequeue(self):
if self.count == 0:
raise IndexError("empty queue")
item = self.items[self.head]
self.head = (self.head + 1) % self.capacity
self.count -= 1
return item
def is_full(self):
return self.count == self.capacity
def is_empty(self):
return self.count == 0
cq = CircularQueue(3)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print("Dequeue:", cq.dequeue())
cq.enqueue(4)
print("Dequeue:", cq.dequeue())
print("Dequeue:", cq.dequeue())
print("Dequeue:", cq.dequeue())
Expected output:
Dequeue: 1
Dequeue: 2
Dequeue: 3
Dequeue: 4
Priority Queue
A priority queue dequeues elements based on priority, not arrival order. High-priority elements are processed first.
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
def enqueue(self, item, priority):
heapq.heappush(self.heap, (priority, item))
def dequeue(self):
if self.is_empty():
raise IndexError("empty priority queue")
priority, item = heapq.heappop(self.heap)
return item
def is_empty(self):
return len(self.heap) == 0
def size(self):
return len(self.heap)
pq = PriorityQueue()
pq.enqueue("low", 3)
pq.enqueue("medium", 2)
pq.enqueue("high", 1)
print("Dequeue:", pq.dequeue())
print("Dequeue:", pq.dequeue())
print("Dequeue:", pq.dequeue())
Expected output:
Dequeue: high
Dequeue: medium
Dequeue: low
Deque (Double-Ended Queue)
A deque allows insertions and deletions from both ends. Python's collections.deque is optimized for this.
from collections import deque
dq = deque()
dq.append(10) # Add to right
dq.appendleft(20) # Add to left
dq.append(30)
print("Deque:", list(dq))
print("Pop right:", dq.pop())
print("Pop left:", dq.popleft())
Expected output:
Deque: [20, 10, 30]
Pop right: 30
Pop left: 20
Common Pitfalls
1. O(n) Dequeue with Array-Based JavaScript Queue
JavaScript's shift() removes the first element and shifts all others — O(n). Use an index-based circular buffer or a proper deque.
2. Not Handling Full Queue in Circular Buffer
Always check if the queue is full before enqueuing. Overwriting unread data causes silent data loss.
3. Forgetting to Update Both Head and Tail
In linked-list queues, when dequeuing the last element, set both front and rear to None. Forgetting this leaves stale references.
4. Integer Overflow in Priority Comparisons
Priority values should fit within your language's integer range. Python handles arbitrary integers, but JavaScript's bitwise operations truncate to 32 bits.
5. Unbounded Queue Growth
Queues that grow without limit consume all available memory. Always set a maximum size or use a bounded buffer.
Practice Questions
1. Implement a stack using two queues.
2. Generate binary numbers from 1 to n using a queue.
def generate_binary(n):
q = deque(["1"])
result = []
for _ in range(n):
front = q.popleft()
result.append(front)
q.append(front + "0")
q.append(front + "1")
return result
print(generate_binary(5))
Expected output: ['1', '10', '11', '100', '101']
3. Implement a recent counter that returns the number of requests in the last 5 seconds.
4. Challenge: Design a task scheduler that runs tasks at specific intervals using a priority queue. Used in Doda Browser's background task manager.
5. Real-world task: DodaZIP uses a queue to Process files during archive extraction. Write a function that takes a list of file paths and a concurrency limit, then processes them in FIFO order without exceeding the limit.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro