Queues with deque
A queue serves the oldest item first: people join at the back and leave from the front. In Python use collections.deque:
from collections import deque line = deque(["Ana", "Bo", "Cy"]) first = line.popleft() # "Ana" leaves from the front line.append(first) # and rejoins at the back
Why not a plain list? list.pop(0) must shift every remaining item one place left, so taking n items from the front costs about n² work. deque.popleft() is instant. With 50,000 items that is the difference between a blink and a timeout.
Rules of thumb:
- Test
while line:before you take from it (an empty deque raises an error). - Round-robin means "take from the front, do a bit of work, put it back at the back if it is not finished".
- A deque of arrival times that you trim from the front is a handy "recent events" window.
In the visual, watch Ana leave the front and reappear at the back.
See it run
from collections import deque line = deque(["Ana", "Bo", "Cy"]) served = line.popleft() line.append(served) print(line)
A line of three people. The front is on the left.
Practice queues with deque
Exercise 1
A help desk logs the second each call arrives in times (whole seconds, never decreasing; several calls can share a second). For each call, count the calls in the last window seconds including itself: a call at time s counts when t - window < s ≤ t, where t is the current call's time.
Return the list of those counts, one per call, in order.
Constraints: 0 ≤ len(times) ≤ 10^5, 1 ≤ window ≤ 10^6.
Example: solution([1, 2, 5, 6, 6], 3) returns [1, 2, 1, 2, 3]. At the call at 5, only calls after second 2 count, so the calls at 1 and 2 have expired.
Exercise 2
Jobs wait in a line in index order 0, 1, 2, ... Job i needs work[i] units of work (each at least 1). A worker repeatedly takes the job at the front and runs it for min(quantum, units still needed) units. If the job still needs work afterwards it goes to the back of the line; otherwise it is finished.
Return the list of job indices in the order the jobs finish.
Constraints: 0 ≤ len(work) ≤ 1000, 1 ≤ quantum ≤ 100, 1 ≤ work[i] ≤ 1000.
Example: solution([5, 2, 3], 2) returns [1, 2, 0]. Job 0 runs (3 left) and goes to the back; job 1 finishes; job 2 runs (1 left) and goes back; job 0 runs (1 left) and goes back; job 2 finishes; job 0 finishes.
Exercise 3
A dealer holds a face-down deck (a list, top card first). They repeat until the deck is empty:
1. Deal the top card onto the table. 2. Then move the top card to the bottom of the deck, one card at a time, k times (if the deck is empty, nothing happens; if few cards remain the same cards may go around more than once).
Return the cards in the order they were dealt.
Constraints: 0 ≤ len(deck) ≤ 10^5, 0 ≤ k ≤ 5. Cards may repeat.
Example: solution([1, 2, 3, 4, 5], 1) returns [1, 3, 5, 4, 2]. Deal 1, move 2 to the bottom (3, 4, 5, 2); deal 3, move 4 (5, 2, 4); deal 5, move 2 (4, 2); deal 4, move 2; deal 2.
Large inputs are tested for speed.
The explanation and tasks are public. Running this lesson requires an account with course access.
Practice
Loading Python…Visualizer Watch your code run line by line
Run your code, then choose Play to follow its execution.