Queues with deque, and Why Not list.pop(0)
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A queue is a line: the first to arrive is the first to be served. Printers, support desks and schedulers all work this way. In Python the right tool is a deque, because a list is slow at the front.
First in, first out
Queue is a collection where items join at the back and leave from the front. The first item added is the first item removed, which is called first in, first out (FIFO).
A line at a ticket counter is a queue. People join at the back and the person at the front is served first. The item that waited longest leaves first.
Why not list.pop(0)?
A list can act as a queue with append and pop(0), and the answers are right. But pop(0) moves every other item one place left, so each call costs O(n).
queue = []queue.append("A")queue.append("B")queue.append("C")print(queue.pop(0))print(queue)Example 1 · A list as a queue
queue = []for customer in ["Asha", "Ben", "Carla"]: queue.append(customer)
while queue: print("serving", queue.pop(0))serving Asha serving Ben serving Carla
What this code does
- Customers are served in the order they joined. The answer is right, but each
pop(0)shifts the rest of the list. - It is fine for a few items. The next section shows why it fails for many.
Example 2 · How much shifting is that?
n = 1000shifted = sum(size - 1 for size in range(n, 0, -1))print(shifted)499500
What this code does
- Serving 1000 items with
pop(0)moves 999 + 998 + ... + 0 items in total. - The total is about n squared / 2, so the cost grows as O(n squared). A
dequemoves nothing.
This works for three items. For a million items the shifting makes the loop far too slow.
deque: fast at both ends
Deque, short for double-ended queue, is a sequence in collections that adds and removes items at both ends in O(1) time. It is the standard Python queue.
collections.deque adds and removes at either end in O(1). Use append to join at the back and popleft to serve from the front.
from collections import deque
queue = deque()queue.append("A")queue.append("B")queue.append("C")print(queue.popleft())print(queue)print(len(queue), queue[0])Example 3 · The same queue with deque
from collections import deque
queue = deque()for customer in ["Asha", "Ben", "Carla"]: queue.append(customer)
while queue: print("serving", queue.popleft())serving Asha serving Ben serving Carla
What this code does
- Only the ends change, so every
appendandpopleftis O(1) and the whole loop is O(n). - The output matches the list version, so only the speed changes.
queue[0] peeks at the front. As with a list, an empty deque is falsy and popleft() on it raises IndexError.
maxlen, rotate and sliding windows
deque(maxlen=3) drops the oldest item when a fourth arrives. rotate(-1) moves the front item to the back. A deque of indexes also gives a window maximum in O(n).
from collections import deque
recent = deque(maxlen=3)for order in [101, 102, 103, 104, 105]: recent.append(order)print(list(recent))recent.rotate(-1)print(list(recent))Example 4 · Keep only the last 3 orders
from collections import deque
recent = deque(maxlen=3)for order in range(1, 7): recent.append(order) print(list(recent))[1] [1, 2] [1, 2, 3] [2, 3, 4] [3, 4, 5] [4, 5, 6]
What this code does
- Once the deque holds 3 items, each
appendpushes the oldest item out of the front. - No manual check is needed.
Example 5 · Round robin scheduling
from collections import deque
tasks = deque([("report", 5), ("backup", 2), ("email", 3)])slice_time = 2while tasks: name, left = tasks.popleft() left -= slice_time if left > 0: tasks.append((name, left)) else: print(name, "done")backup done email done report done
What this code does
- Each task runs for 2 units. If it is not finished it goes to the back of the line.
backupneeds only 2 units, so it finishes first.emailfinishes beforereport.
Example 6 · Elimination circle
from collections import deque
players = deque(["Ria", "Sam", "Tia", "Uma", "Vik"])step = 3while len(players) > 1: players.rotate(-(step - 1)) print("out:", players.popleft())print("winner:", players[0])out: Tia out: Ria out: Vik out: Sam winner: Uma
What this code does
- Rotating by
step - 1puts the player to remove at the front.popleftremoves that player. - Each round is O(step), so the whole game is O(n * step).
Example 7 · Maximum of every window of 3
from collections import deque
def window_max(nums, size): result = [] window = deque() for i, value in enumerate(nums): while window and nums[window[-1]] <= value: window.pop() window.append(i) if window[0] <= i - size: window.popleft() if i >= size - 1: result.append(nums[window[0]]) return result
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))[3, 3, 5, 5, 6, 7]
What this code does
- The deque holds indexes whose values fall from front to back, so the front is always the window maximum.
- A smaller value behind a larger one can never be a maximum, so it is dropped. The time is O(n).
Example 8 · First letter that has not repeated
from collections import deque
queue = deque()counts = {}for ch in "aabcbd": counts[ch] = counts.get(ch, 0) + 1 queue.append(ch) while queue and counts[queue[0]] > 1: queue.popleft() print(queue[0] if queue else "-")a - b b c c
What this code does
- The queue keeps letters in arrival order. Repeated letters are dropped from the front.
- After each letter the front is the first letter that has appeared only once.
rotate(-1) turns [103, 104, 105] into [104, 105, 103]. A positive number rotates the other way.
Next step
Check your understanding
11 quick questions