Queue-based simulations

What is a queue?

A queue is a collection where you add at the back and remove from the front. Enqueue means add an item; dequeue means remove the oldest waiting item. This order is called first in, first out, or FIFO. A deque lets you add and remove at either end.

Example: Enqueue 4, then 8, then 15. The next dequeue returns 4. The remaining queue is 8, 15.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays

Understand the idea

Queue simulations should define event order and time progression. A pending item can create future work; enqueue that work only when the event occurs. Avoid repeated full scans when only the next event is needed.

Work through an example

A service queue receives jobs at times 0,2,2. If the server is idle, jump to the next arrival; at equal times apply a documented arrival-before-selection rule.

Time and space complexity

O(events) queue work; sorting unsorted events adds O(n log n).

Why it works

Queued jobs are arrived, unprocessed work in the required order.

Common mistakes

Equal timestamps need deterministic tie rules.
Advancing time one unit at a time may be wasteful.

Chapter lab · Python implementation

Queues process the oldest pending item first. Python deque supports efficient operations at both ends; list.pop(0) shifts a packed list. The lab maintains a decreasing deque of candidate indices for each fixed-size window maximum, keeping expiration separate from dominance.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def window_max(values,k):
    if not 1<=k<=len(values):
        raise ValueError('invalid k')
    candidates=deque()
    output=[]
    for i,x in enumerate(values):
        while candidates and candidates[0]<=i-k:
            candidates.popleft()
        while candidates and values[candidates[-1]]<=x:
            candidates.pop()
        candidates.append(i)
        if i>=k-1:
            output.append(values[candidates[0]])
    return output

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert window_max([1,3,-1,-3,5,3,6,7],3)==[3,3,5,5,6,7]
assert window_max([2,2,2],2)==[2,2]
assert window_max([-4],1)==[-4]

CHECK YOUR UNDERSTANDING

What is a queue?

First candidate.