DSA course menu
Queues and Deques in Python: FIFO, collections.deque and Circular Queues
Learn the queue data structure: first in, first out, why list.pop(0) is slow, collections.deque, a circular array queue, queues from two stacks and the sliding window maximum with a deque.
On this page
A queue removes items in the order they arrived: first in, first out (FIFO), like people waiting in line. Items join at the back (enqueue) and leave from the front (dequeue).
Queues appear wherever work must be handled in order: print jobs, requests to a web server, messages between programs, and breadth-first search.
Do not use list.pop(0)#
pop(0) removes the first item of a list, but every other item then shifts left: O(n) per dequeue. Python's collections.deque (double-ended queue) adds and removes at both ends in O(1):
from collections import deque
queue = deque()
queue.append("Asha") # enqueue at the back
queue.append("Ravi")
queue.append("Meera")
print(queue.popleft()) # dequeue from the front
print(queue.popleft())
print(queue, len(queue))Asha
Ravi
deque(['Meera']) 1A deque can also be used as a stack (append / pop) and from the left (appendleft), which is why it is the standard tool for both.
A circular queue on a fixed array#
Without deque, a fixed-size array can act as a queue if the front and back wrap around to the start when they reach the end. This is how queues are built in memory-limited systems:
class CircularQueue:
def __init__(self, capacity):
self.items = [None] * capacity
self.front = 0
self.count = 0
def enqueue(self, value):
if self.count == len(self.items):
raise OverflowError("queue is full")
back = (self.front + self.count) % len(self.items)
self.items[back] = value
self.count += 1
def dequeue(self):
if self.count == 0:
raise IndexError("queue is empty")
value = self.items[self.front]
self.items[self.front] = None
self.front = (self.front + 1) % len(self.items)
self.count -= 1
return value
q = CircularQueue(3)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue(), q.items)
q.enqueue(4) # wraps into slot 0
print(q.items, "front at index", q.front)
print(q.dequeue(), q.dequeue(), q.dequeue())1 [None, 2, 3]
[4, 2, 3] front at index 1
2 3 4The % (modulo) makes index 3 wrap back to 0. Every operation is O(1) and no item ever shifts.
A queue from two stacks#
A classic interview question: build a queue using only stacks. Push onto an inbox; to dequeue, pour the inbox into an outbox (which reverses the order) only when the outbox is empty:
class TwoStackQueue:
def __init__(self):
self.inbox, self.outbox = [], []
def enqueue(self, x):
self.inbox.append(x)
def dequeue(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
return self.outbox.pop()
q = TwoStackQueue()
for x in [1, 2, 3]:
q.enqueue(x)
print(q.dequeue())
q.enqueue(4)
print(q.dequeue(), q.dequeue(), q.dequeue())1
2 3 4Each item moves from inbox to outbox at most once, so dequeue is amortized O(1).
Sliding window maximum with a deque#
For every window of k consecutive numbers, report the maximum. Keep a deque of indexes whose values are in decreasing order; the front is always the current maximum. Drop indexes that leave the window from the front, and drop smaller values from the back (they can never be a maximum again):
from collections import deque
def window_max(nums, k):
dq, result = deque(), []
for i, x in enumerate(nums):
if dq and dq[0] <= i - k: # front fell out of the window
dq.popleft()
while dq and nums[dq[-1]] < x: # smaller values are useless now
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))[3, 3, 5, 5, 6, 7]Each index enters and leaves the deque once: O(n) total, instead of O(n·k) by checking every window. This "keep it sorted by throwing away useless items" idea is the monotonic stack applied to a deque.
Priority queues#
Sometimes the next item should be the most important, not the oldest: the emergency patient, the cheapest route, the earliest deadline. That is a priority queue, usually built with a heap.
Common mistakes#
Practice#
Practice exercise
A "hot potato" game: n players stand in a circle numbered 1 to n. Counting starts at player 1; every k-th player is removed until one remains. Write last_player(n, k) using a deque. For n = 5, k = 2 players leave in the order 2, 4, 1, 5 and player 3 wins.
Show hint
Rotate the deque: move the first k - 1 players from the front to the back, then remove the player now at the front. deque.rotate(-(k - 1)) does the moving in one call.
Show solution
from collections import deque
def last_player(n, k):
players = deque(range(1, n + 1))
order = []
while len(players) > 1:
players.rotate(-(k - 1)) # skip k - 1 players
order.append(players.popleft())
return players[0], order
print(last_player(5, 2))
print(last_player(7, 3))(3, [2, 4, 1, 5])
(4, [3, 6, 2, 7, 5, 1])This is the Josephus problem.
Key takeaway#
Next: stacks that stay sorted, the Monotonic Stack.
Finished this lesson?