A Queue is a linear data structure that follows the principle of First In, First Out (FIFO).
Table of Contents
Introduction
A Queue is a linear data structure that follows the principle of First In, First Out (FIFO). This means that the first element inserted into the queue will be the first one to be removed — just like a line at a movie ticket counter.
Example analogy:
Imagine people standing in a queue for bus tickets. The person who arrives first is served first, and the last person waits until everyone ahead has been served.
Characteristics of a Queue
- FIFO Order – First element added is the first to be removed.
- Two Main Operations:
- Enqueue: Add an element to the end of the queue.
- Dequeue: Remove an element from the front of the queue.
- Front & Rear:
- Front (Head) – Position from which elements are removed.
- Rear (Tail) – Position where new elements are added.
- Limited Access – Unlike arrays/lists, you can only insert at one end and remove from the other.
Basic Queue Operations
| Operation | Description | Time Complexity |
|---|---|---|
| Enqueue | Insert an element at the rear of the queue | O(1) |
| Dequeue | Remove an element from the front of the queue | O(1) |
| Peek / Front | View the element at the front without removing it | O(1) |
| isEmpty | Check if the queue is empty | O(1) |
| Size | Get the number of elements in the queue | O(1) |
Types of Queues
Queues come in several variations, depending on usage:
- Simple Queue (Linear Queue)
- Standard FIFO queue.
- Once the queue is full, no more insertions are possible without dequeuing elements.
- Example: Printer job queue.
- Circular Queue
- The last position connects back to the first position, forming a circle.
- Avoids wastage of space from repeated enqueues/dequeues in a fixed-size array.
- Example: Round-robin CPU scheduling.
- Priority Queue
- Each element has a priority.
- Elements with higher priority are dequeued before lower-priority ones.
- Example: Emergency room in hospitals (critical patients treated first).
- Deque (Double-Ended Queue)
- A deque (pronounced “deck“), or double-ended queue, is a linear data structure
- Allows insertion and deletion from both ends.
- Two main variations:
- Input-restricted deque – insertion at one end only.
- Output-restricted deque – deletion at one end only.
- Example: Browser history (can go back or forward).
Summary
| Type | Insertion | Deletion | Example |
|---|---|---|---|
| Simple Queue | Rear | Front | Print queue |
| Circular Queue | Rear (wraps around) | Front | CPU scheduling |
| Priority Queue | Based on priority | Based on priority | Hospital |
| Deque | Both ends | Both ends | Browser history |
Various Queue Implementations in Python
1. Using collections.deque (Most Efficient)
from collections import deque
# Create a queue
queue = deque()
# Enqueue
queue.append("A")
queue.append("B")
queue.append("C")
print("Queue after enqueue:", queue)
# Dequeue
print("Dequeued:", queue.popleft())
print("Queue after dequeue:", queue)
# Peek
print("Front element:", queue[0])
# Check if empty
print("Is queue empty?", len(queue) == 0)Why deque?
It is part of Python’s built-in collections module and is designed for fast, O(1) appends and pops from both ends, unlike a Python list where pop(0) is O(n).
The reason comes down to how Python internally stores data in list vs collections.deque.
Python List Internals
- A Python list is backed by a dynamic array (contiguous memory block in RAM).
- This means:
- append() at the end → O(1) (amortized) because it just places the item in the next free slot.
- pop() at the end → O(1) because it just removes the last element.
- insert(0, x) or pop(0) → O(n) because all elements need to be shifted one position in memory.
Example:
list = [A, B, C, D]
pop(0) → remove A
shift B → position 0
shift C → position 1
shift D → position 2Here, every shift is a memory copy, so the time grows with n.
collections.deque Internals
- A deque is implemented as a doubly linked list of blocks (sometimes called a linked block array).
- It does not store all elements in one contiguous block — instead, it uses multiple fixed-size memory blocks connected together.
- This allows:
- append() at the right end → O(1) (just add to the last block or allocate a new one if full).
- appendleft() at the left end → O(1) (just add to the first block or allocate a new one if full).
- pop() / popleft() → O(1) because it just updates pointers without shifting any elements.
Example of deque pop from left:
deque = [A][B][C][D]
popleft() → just move the "start" pointer from A to B
No shifting at all.
Summary
| Operation | Python List | collections.deque |
|---|---|---|
| append() | O(1) | O(1) |
| appendleft() | O(n) | O(1) |
| pop() | O(1) | O(1) |
| popleft() | O(n) | O(1) |
| Random access | O(1) | O(n) |
When to Use Which
Use list if:
- You need random access by index often.
- Most operations happen at the end of the list.
Use deque if:
- You need fast insertions/removals at both ends.
- You’re implementing queues, BFS, or sliding windows.
2. Using queue.Queue (Thread-Safe)
from queue import Queue
q = Queue()
# Enqueue
q.put("A")
q.put("B")
# Dequeue
print("Dequeued:", q.get())
# Size
print("Queue size:", q.qsize())When to use: In multi-threaded applications (e.g., producer-consumer problems).
3. Custom Queue using List
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item) # O(1)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0) # O(n)
return None
def peek(self):
return self.items[0] if not self.is_empty() else None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Usage
q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue()) # 10Drawback: pop(0) is O(n), making it inefficient for large queues.
Real-World Applications of Queues
- Operating Systems: CPU task scheduling (Round Robin, FCFS).
- Networking: Packet scheduling in routers.
- Printing: Print job management.
- Customer Service: Call center waiting lists.
- Simulation: Traffic systems, ticket counters.
Play with collections.deque
Creating a Deque
from collections import deque
# Empty deque
dq = deque()
# From iterable
dq = deque(["A", "B", "C"])
dq.extend([1, 2, 3])
dq.append(4) # Oldest (1) is discarded
print(dq) # deque([2, 3, 4], maxlen=3)Key Operations
| Method | Description | Complexity |
|---|---|---|
append(x) | Add to right end | O(1) |
appendleft(x) | Add to left end | O(1) |
pop() | Remove from right end | O(1) |
popleft() | Remove from left end | O(1) |
extend(iterable) | Append multiple items to right end | O(k) |
extendleft(iterable) | Append multiple items to left end (reversed order) | O(k) |
rotate(n) | Rotate deque n steps right (negative for left) | O(k) |
clear() | Remove all items | O(1) |
count(x) | Count occurrences | O(n) |
remove(value) | Remove first occurrence | O(n) |
deque as a Queue
Using append() for enqueue and popleft() for dequeue:
from collections import deque
queue = deque()
# Enqueue
queue.append("Task1")
queue.append("Task2")
queue.append("Task3")
print("Queue:", queue)
# Dequeue
print("Processing:", queue.popleft())
print("Queue after dequeue:", queue)
'''
Output
Queue: deque(['Task1', 'Task2', 'Task3'])
Processing: Task1
Queue after dequeue: deque(['Task2', 'Task3'])
'''deque as a Stack
Using append() for push and pop() for pop:
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop()) # 3
print(stack.pop()) # 2deque as a Sliding Window
deque is perfect for problems like sliding window maximum:
def sliding_window_max(nums, k):
dq = deque()
res = []
for i, num in enumerate(nums):
# Remove out-of-window indices
if dq and dq[0] <= i - k:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# Add to results once window is full
if i >= k - 1:
res.append(nums[dq[0]])
return res
print(sliding_window_max([1,3,-1,-3,5,3,6,7], 3)) #[3, 3, 5, 5, 6, 7]
Fixed-Size Buffer (maxlen)
log = deque(maxlen=5)
for i in range(10):
log.append(i)
print(log)Behavior: Automatically discards oldest entries once full.
Rotation
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2) # Right rotation
print(dq) # deque([4, 5, 1, 2, 3])
dq.rotate(-1) # Left rotation
print(dq) # deque([5, 1, 2, 3, 4])Thread-Safety
deque operations like append() and popleft() are thread-safe, making it suitable for multi-threaded producer-consumer problems without extra locking.
from collections import deque
from threading import Thread
import time
q = deque()
def producer():
for i in range(5):
q.append(i)
print("Produced", i)
time.sleep(0.5)
def consumer():
while True:
if q:
item = q.popleft()
print("Consumed", item)
time.sleep(0.5)
Thread(target=producer).start()
Thread(target=consumer).start()When NOT to Use deque
- If you need random indexing often — lists are faster for direct index access.
- If you must store millions of items with minimal memory — arrays or NumPy arrays are more memory-efficient.
Practice
Sliding Window & Monotonic Queue
- Leet 239: Sliding Window Maximum – Classic monotonic deque problem.
- Leet 1438: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit – Maintaining min and max with two deques.
- Leet 862: Shortest Subarray with Sum at Least K – Prefix sums with deque for optimization.
- Leet 1696: Jump Game VI – Deque for max sliding window in DP.
BFS & Graph Traversals
- Leet 994: Rotting Oranges – Multi-source BFS queue simulation.
- Leet 542: 01 Matrix – Multi-source BFS using deque.
- Leet 1293: Shortest Path in a Grid with Obstacles Elimination – BFS with state tracking.
- Leet 847: Shortest Path Visiting All Nodes –BFS with bitmask states.
Double-Ended Queue Logic
- Leet 641: Design Circular Deque – Direct deque implementation.
- Leet 1670: Design Front Middle Back Queue – Complex deque manipulations.
Other Deque-based Patterns
- Leet 2390: Removing Stars From a String – Stack-like use of deque.
- Leet 649: Dota2 Senate – Simulating queue turns.
- Leet 862: Shortest Subarray with Sum at Least K – Deque optimization for prefix sums.
Conclusion
The collections.deque is one of Python’s most efficient and versatile data structures for queue-like behavior. It delivers O(1) time complexity for appending and popping from both ends, making it ideal for implementing queues, stacks, deques, sliding windows, and fixed-size buffers. It is also thread-safe, which simplifies concurrent producer–consumer scenarios without additional locking.
While it’s not optimized for random access or heavy index-based operations (where lists perform better), its speed, flexibility, and built-in features make it the go-to choice whenever you need frequent insertions and deletions at both ends of a collection. In short: if your problem is about order and movement, deque is your best friend in Python.