Queue Implementation and Deque
Build a queue with Python's deque, implement a circular queue, and solve sliding-window maximum using a monotonic deque.
Queue Implementation and Deque is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Queue Data Structure
A queue is a first-in, first-out (FIFO) data structure. The first element enqueued is the first element dequeued — like a checkout line at a store. Core operations are enqueue (add to rear) and dequeue (remove from front). Both must be O(1) for the queue to be efficient.
Using a Python list as a queue is tempting but wrong: list.pop(0) is O(n) because it shifts all elements. The correct tool is collections.deque, which provides O(1) appendleft, append, popleft, and pop.
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])Queue Class Using deque
Wrap deque in a Queue class with named operations to match what interviewers expect. Internally enqueue calls append and dequeue calls popleft. The peek operation reads queue[0] without removing it.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2BFS with a Queue
The classic application of a queue is Breadth-First Search (BFS). Enqueue the root; while the queue is non-empty, dequeue a node, process it, and enqueue its unvisited neighbours. Because we process nodes level by level, BFS naturally finds the shortest path in an unweighted graph. The queue always holds nodes from at most two adjacent levels.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Circular Queue (LeetCode 622)
LeetCode 622 'Design Circular Queue': implement a fixed-capacity queue that wraps around. Use an array of size k and two pointers: head and tail. Enqueue at tail, dequeue at head, and compute positions modulo k. A count variable distinguishes full from empty (both have head == tail modulo k otherwise).
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # TrueSliding Window Maximum with Monotonic Deque
LeetCode 239 'Sliding Window Maximum': for each window of size k, find the maximum element. The brute force is O(n*k). The O(n) approach uses a monotonic decreasing deque that stores indices. For each new element: remove indices outside the window from the front; remove indices with smaller values from the back (they can never be the maximum in any future window). The front always holds the maximum.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Why Deque Not Just a List for Queue?
Python's list.pop(0) removes the first element in O(n) because every remaining element must shift one position left. For n insertions and n deletions this gives O(n²) total. collections.deque is a doubly-linked list of fixed-size blocks; popleft is O(1) because it only adjusts a pointer. For BFS on a graph with 10^5 nodes, the difference between O(n) and O(n²) is the difference between 100 ms and 100 seconds.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')Binary Tree Level Order Traversal (LeetCode 102)
LeetCode 102 'Binary Tree Level Order Traversal': return all node values level by level. Use a queue; at the start of each level record the queue size (that is how many nodes are at this level). Dequeue exactly that many nodes, collecting their values and enqueueing their children. Repeat until the queue is empty.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]Priority Queue with heapq
Python's heapq module provides a min-heap (priority queue): the smallest element is always dequeued first. heapq.heappush(h, item) adds an element in O(log n) and heapq.heappop(h) removes the minimum in O(log n). For tasks like Dijkstra's algorithm and top-k problems, heapq replaces the simple queue.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')Wallpaper Pattern: Queue for Word Ladder
LeetCode 127 'Word Ladder': find the minimum number of single-character substitutions to transform one word to another, using only dictionary words. Model as a graph where edges connect words differing by one character. BFS on this graph finds the shortest path (minimum steps) in O(n * L²) where n is the dictionary size and L is word length.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5deque as a Double-Ended Queue
collections.deque is a double-ended queue (deque): you can efficiently add and remove from both ends. Methods: appendleft and popleft for the front; append and pop for the rear. This lets deque serve as both a FIFO queue (appendright + popleft) and a LIFO stack (append + pop). The sliding window maximum uses both ends: remove old indices from left, remove smaller values from right.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]Summary: Queue vs Deque vs Heap
Choose the right tool for the problem. Use a simple queue (deque) for FIFO processing and BFS. Use a monotonic deque when you need the sliding maximum or minimum — it maintains a sorted invariant by removing dominated elements. Use a priority queue (heapq) when you need the global minimum or maximum regardless of order, such as in Dijkstra's or top-k problems. Knowing which to reach for and why is a key skill interviewers test.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: collections.deque provides O(1) enqueue and dequeue making it the correct queue implementation in Python, BFS uses a queue to process nodes level by level, finding shortest paths in unweighted graphs, and a monotonic decreasing deque solves sliding window maximum in O(n) by removing dominated indices. Next up we explore the monotonic stack pattern in depth.
Frequently asked questions
Is the “Queue Implementation and Deque” lesson free?
Yes — the full text of “Queue Implementation and Deque” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Queue Implementation and Deque”?
Build a queue with Python's deque, implement a circular queue, and solve sliding-window maximum using a monotonic deque. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Queue Implementation and Deque” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Stack Implementation and Applications
- Queue Implementation and Deque
- Monotonic Stack Pattern
- Stack and Queue Mutual Simulation