The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Queue Exercises

Next ►
►

Time to consolidate. In this module you have learned four structures (FIFO queue, circular queue, priority queue, and deque), and this lesson brings no new theory: it brings six progressive exercises that put them to work together — along with the stacks from module 3 — on real TaskFlow problems. We recommend the usual method: read the statement, decide first which structure fits and why (the choice is half the exercise), write your solution, test it against the given cases, and only then compare it with the commented solution. The solutions reuse the module's classes: Queue (04-02), UrgentInbox (04-04), and collections.deque (04-05).

Contents

  1. Exercise 1: notifications with retries
  2. Exercise 2: round-robin scheduler with a quantum
  3. Exercise 3: urgent inbox with interleaved extractions
  4. Exercise 4: maximum of completed tasks in a sliding window
  5. Exercise 5: generating the binaries from 1 to n with a queue
  6. Exercise 6: reversing the first k elements of a queue
  7. Commented solutions

Exercises

Exercise 1: notifications with retries

Sending TaskFlow notifications sometimes fails (the mail server does not respond). Extend the idea of the NotificationQueue from 04-02: write a function process_with_retries(notifications, send, max_attempts=3) that receives a list of notifications (dicts with at least message) and a function send(notif) that returns True (success) or False (failure). Rules:

  • Notifications are processed in FIFO order.
  • If a send fails, the notification goes back to the end of the queue (no hot retry: that way a downed server does not block the others).
  • Each notification is attempted at most max_attempts times; past the limit, it goes to a discarded list.
  • Return the tuple (sent, discarded) with the notifications in the order they were resolved.

Test it with a send that always fails for messages containing "@down" and succeeds for the rest.

Exercise 2: round-robin scheduler with a quantum

In module 2, the TaskDispatcher spun over a CircularList to hand out turns. Operating systems do something finer: round-robin with a quantum. Write round_robin_schedule(tasks, quantum) where each task is a dict with id, title, and remaining (units of work pending). Rules:

  • Tasks wait in a FIFO queue.
  • The first one is dequeued, worked on for at most quantum units, and:
    • if it still has work left, it goes back to the end of the queue;
    • if it finishes, it is added to the finished list.
  • Return the list of ids in completion order and the turn log as a list of (id, units_worked) tuples.

With tasks = [{id: 1, remaining: 5}, {id: 2, remaining: 2}, {id: 3, remaining: 8}] and quantum = 3, the completion order must be [2, 1, 3].

Exercise 3: urgent inbox with interleaved extractions

Using heapq with the (priority, counter, task) idiom from 04-04 (you may use the UrgentInbox class or rewrite it by hand), simulate this support shift and predict before running the order of service:

arrives  ("Broken backup",      priority 2)
arrives  ("Slow website",       priority 3)
SERVE one task
arrives  ("Server down",        priority 1)
arrives  ("Login failing",      priority 1)
SERVE one task
SERVE one task
arrives  ("Secondary backup",   priority 2)
SERVE all remaining

Write the code that reproduces the simulation and prints the order of service. Check your prediction, paying attention to the priority 1 tie.

Exercise 4: maximum of completed tasks in a sliding window

In 04-05 we computed the moving average with a maintained sum. The window maximum is harder: when the day falling off was precisely the maximum, what is the new one? Recomputing it every day is O(k). There is an amortized O(1)-per-day technique: the monotonically decreasing deque (it keeps maximum candidates from largest to smallest; relatives of the min-stack from module 3).

Write window_maximums(completed_per_day, k) that returns, for each day from day k onward, the maximum of tasks completed in the last k days. Rules of the monotonic deque (it stores day indices):

  1. Before adding day i, remove from the back every index whose value is <= day i's (they can never be maximums once i, more recent and larger, has arrived).
  2. Add i at the back.
  3. Remove from the front the index i - k if it is still there (it has expired: it is no longer in the window).
  4. The window's maximum is the value at the front index.

With completed = [3, 5, 2, 4, 6, 1, 0, 7] and k = 3, the result is [5, 5, 6, 6, 6, 7].

Exercise 5: generating the binaries from 1 to n with a queue

A surprising classic: generate the binary representations of the numbers 1 to n without converting numbers (no bin()), using only a queue of strings. The seed is "1"; at each step a string b is dequeued, emitted as a result, and b + "0" and b + "1" are enqueued. Write binaries_up_to(n) and explain why the FIFO queue produces exactly the order 1, 10, 11, 100, 101... What would come out if you used a stack? (Preview: this "process and enqueue the descendants" pattern is exactly the level-order/BFS traversal you will see in trees and graphs, modules 6 and 7.)

Exercise 6: reversing the first k elements of a queue

Integration with module 3: write reverse_first(queue, k) that reverses the order of the first k elements of a Queue, leaving the rest in their original order, using only the queue's contract, one auxiliary Stack, and O(1) extra variables. With the queue 1, 2, 3, 4, 5 (front on the left) and k = 3, the result must be 3, 2, 1, 4, 5. Hint: the stack reverses; to reposition the rest without disturbing their order, the full rotation we used in recent_activity (04-03) will serve you. Handle the error cases: k larger than the size, or negative.

Solutions

Solution 1: notifications with retries

from collections import deque

def process_with_retries(notifications, send, max_attempts=3):
    queue = deque()                         # deque as a FIFO queue (04-05)
    for notif in notifications:
        queue.append({**notif, "attempts": 0})   # copy + attempt counter

    sent, discarded = [], []
    while queue:
        notif = queue.popleft()             # FIFO: the longest-waiting one
        notif["attempts"] += 1
        if send(notif):
            sent.append(notif)
        elif notif["attempts"] < max_attempts:
            queue.append(notif)             # to the END: doesn't block the others
        else:
            discarded.append(notif)         # out of chances
    return sent, discarded


# --- Test ---
def simulated_send(notif):
    return "@down" not in notif["message"]

notifs = [
    {"message": "Task 1 assigned to anna"},
    {"message": "Alert to server @down"},
    {"message": "Task 2 completed"},
]
ok, ko = process_with_retries(notifs, simulated_send)
print([n["message"] for n in ok])   # the two good ones, in arrival order
print([n["attempts"] for n in ko])  # [3]: the failing one used up its 3 attempts

Commentary: the three substantial points are (1) the attempts counter travels inside the notification (with a {**notif, ...} copy so the caller's input is not mutated); (2) re-enqueuing at the end implements the "don't block" policy: between one retry and the next, the rest of the queue gets served, giving the server time to recover; (3) the loop always terminates, because each notification passes through popleft at most max_attempts times — total cost O(n · max_attempts).

Solution 2: round-robin with a quantum

from collections import deque

def round_robin_schedule(tasks, quantum):
    queue = deque(dict(t) for t in tasks)   # copies: we don't mutate the input
    finished, turns = [], []

    while queue:
        task = queue.popleft()
        worked = min(quantum, task["remaining"])      # never more than pending
        task["remaining"] -= worked
        turns.append((task["id"], worked))
        if task["remaining"] > 0:
            queue.append(task)              # its turn is over: back of the line
        else:
            finished.append(task["id"])
    return finished, turns


tasks = [
    {"id": 1, "title": "Import data", "remaining": 5},
    {"id": 2, "title": "Send summary", "remaining": 2},
    {"id": 3, "title": "Generate report", "remaining": 8},
]
done, turns = round_robin_schedule(tasks, quantum=3)
print(done)    # [2, 1, 3]
print(turns)   # [(1, 3), (2, 2), (3, 3), (1, 2), (3, 3), (3, 2)]

Commentary: let's follow the trace to verify the [2, 1, 3]. Turn for 1 (works 3, 2 left → re-enqueued), turn for 2 (works 2, finishes), turn for 3 (works 3, 5 left → re-enqueued), turn for 1 (works 2, finishes), turns for 3 (3 and 2, finishes). The beauty of round-robin is fairness: the short task (id 2) does not wait for the long one (id 3) to finish, and no task monopolizes the processor for more than quantum in a row. It is the TaskDispatcher from module 2 with a queue contract instead of a circular list: re-enqueuing at the back is the spin of the ring. The min(quantum, remaining) avoids "overworking" and logging negative turns — an easy edge case to forget.

Solution 3: interleaved urgencies

import heapq
from itertools import count

heap, c, served = [], count(), []

def arrive(title, priority):
    heapq.heappush(heap, (priority, next(c),
                   {"title": title, "priority": priority}))

def serve():
    task = heapq.heappop(heap)[2]
    served.append(task["title"])

arrive("Broken backup", 2)
arrive("Slow website", 3)
serve()                         # 1st
arrive("Server down", 1)
arrive("Login failing", 1)
serve(); serve()                # 2nd and 3rd
arrive("Secondary backup", 2)
while heap:
    serve()                     # the rest

print(served)
# ['Broken backup', 'Server down', 'Login failing', 'Secondary backup', 'Slow website']

Commentary, service by service: (1) at the first one, only priorities 2 and 3 are present → Broken backup comes out; the priority 1 emergencies had not arrived yet — a priority queue orders what is present, it does not predict the future. (2) and (3): with the two priority 1 tasks now inside, both come out, and the tie is resolved by the counter: Server down arrived before Login failing (stability). (4) Secondary backup (priority 2) overtakes Slow website (priority 3) even though it arrived much later: in a priority queue, seniority only breaks ties, it never rules. If your prediction failed, it was almost certainly at the first service or in the tie order: those are the two spots where FIFO intuition betrays you.

Solution 4: window maximum with a monotonic deque

from collections import deque

def window_maximums(completed_per_day, k):
    candidates = deque()        # day indices, with DECREASING values
    maximums = []

    for i, value in enumerate(completed_per_day):
        # (1) Evict from the back the candidates 'value' renders obsolete:
        #     they are older than i AND not larger → they can never be the max.
        while candidates and completed_per_day[candidates[-1]] <= value:
            candidates.pop()
        # (2) Day i enters as a candidate at the back.
        candidates.append(i)
        # (3) Expire at the front the day leaving the window.
        if candidates[0] <= i - k:
            candidates.popleft()
        # (4) Once the window is complete, the front is the maximum.
        if i >= k - 1:
            maximums.append(completed_per_day[candidates[0]])
    return maximums


print(window_maximums([3, 5, 2, 4, 6, 1, 0, 7], k=3))
# [5, 5, 6, 6, 6, 7]

Commentary: the invariant is that candidates holds indices whose values run from largest (front) to smallest (back), all inside the window. Step (1) maintains it: if the new day equals or exceeds the last candidate, that candidate can never be the maximum again (the new one is just as large and will expire later), so it is removed — the same "discard the dominated" logic as the MinStack from module 3, now at both ends. Step (3) uses the front as an expiry date. The cost? Each index enters once and leaves at most once (at the back or the front): O(n) total, amortized O(1) per day — the concept from 04-02 reappears. The naive solution with a daily max(window) would be O(n·k); with k = 30 days and years of history, the difference shows.

Solution 5: binaries with a queue

from collections import deque

def binaries_up_to(n):
    result = []
    queue = deque(["1"])                # seed
    for _ in range(n):
        b = queue.popleft()             # the oldest = the shortest pending
        result.append(b)
        queue.append(b + "0")           # its two "descendants"
        queue.append(b + "1")
    return result

print(binaries_up_to(10))
# ['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010']

Commentary: why does the correct numeric order come out? Because the FIFO queue processes the strings by increasing length (all the 1-bit ones, then all the 2-bit ones...), and within each length, in the order they were generated, which is numeric order (from "10" come "100" and "101" before "11" generates "110" and "111"). It is a level-order traversal of the implicit binary tree of strings — literally the BFS we will formalize in modules 6 and 7; this exercise is your first BFS without knowing it. With a stack (LIFO) the traversal would be depth-first: 1, 11, 111, 1111... — it would sink down the branch of ones and, with infinite generation, never come back; capped at n elements it would produce a completely different order.

Solution 6: reversing the first k with a stack

def reverse_first(queue, k):
    if k < 0 or k > queue.size():
        raise ValueError("k out of range")
    if k <= 1:
        return                          # nothing to reverse

    stack = Stack()                     # the Stack from module 3

    # Phase 1: the first k move onto the stack (they end up reversed).
    for _ in range(k):
        stack.push(queue.dequeue())

    # Phase 2: the stack goes back into the queue AT THE BACK, now reversed.
    while not stack.is_empty():
        queue.enqueue(stack.pop())

    # Phase 3: the remaining n-k are now IN FRONT of the reversed block;
    # a full rotation of n-k elements sends them behind it (04-03).
    for _ in range(queue.size() - k):
        queue.enqueue(queue.dequeue())


# --- Test ---
queue = Queue()
for x in [1, 2, 3, 4, 5]:
    queue.enqueue(x)
reverse_first(queue, 3)
output = [queue.dequeue() for _ in range(queue.size())]
print(output)                           # [3, 2, 1, 4, 5]

Commentary, following the example 1..5 with k = 3: after phase 1, the queue is 4, 5 and the stack [1, 2, 3] (3 on top). Phase 2 pops 3, 2, 1 and enqueues them: the queue becomes 4, 5, 3, 2, 1 — the block is reversed, but in the wrong place. Phase 3 rotates the n - k = 2 front elements to the back: 5, 3, 2, 1, 4 → 3, 2, 1, 4, 5. Done. Each element moves a constant number of times → O(n). The exercise distills the whole module: the stack as a reverser (module 3), the queue as an order keeper (this module), and rotation as a way to reposition without leaving the contract. Typical mistakes: forgetting phase 3 (leaves the reversed block at the end), or doing phase 3 with k rotations instead of n - k.

Common Mistakes and Tips

  • Re-enqueuing without a limit (exercises 1 and 2): every while queue: loop that re-enqueues must have a progress guarantee — an attempt counter, a decreasing remaining. Without it, one "immortal" element turns the program into an infinite loop. Always check: what quantity strictly decreases on each pass?
  • Mutating the caller's dicts: solutions 1 and 2 copy ({**notif, ...}, dict(t)) before adding fields or subtracting work. Returning modified data the caller did not expect is a classic source of hard-to-trace bugs.
  • In the monotonic deque, comparing with < instead of <=: with <, ties pile up as redundant candidates; it works, but the deque grows more than necessary. With <= the invariant stays strict. The serious mistake would be evicting from the front by value instead of by expired index: mixing the two criteria breaks the algorithm.
  • Choosing the structure by inertia: before coding, say out loud what the problem needs: arrival order (queue)? the most urgent (priority)? both ends (deque)? reversal (stack)? All six exercises are solved badly with the wrong structure and almost by themselves with the right one.
  • Final tip of the module: keep your solutions. The scheduler (ex. 2) and the inbox (ex. 3) will reappear in the module 8 projects, and the pattern of exercise 5 is the heart of the BFS in module 7.

Conclusion

End of module 4. You have applied the FIFO queue to retries and round-robin scheduling (closing the circle with the TaskDispatcher from module 2), the priority queue with heapq to a support shift with stable ties, the deque to the monotonic-deque technique for window maximums, and you have combined stack and queue to reverse by blocks — besides discovering, with the binary numbers, that "enqueue the descendants of what I process" generates level-order traversals: the seed of the BFS that will germinate in module 7. The three restricted-access structures (stack, queue, deque) are now yours, contract and costs included. But notice something we have done all module without questioning it: every TaskFlow task is a dict, and inside it we jump from task["id"] to task["priority"] taking for granted that the lookup is instantaneous. Why does a dict find a key among thousands in constant time, when searching a list is O(n)? The answer — hash functions, collisions, and one of the most influential ideas in computer science — is the syllabus of module 5: hash tables and dictionaries. See you there.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved