FIFO operations

Understand the idea

FIFO means first-in-first-out. Enqueue at the back and dequeue at the front. This order supports fair work processing and breadth-first search.

Work through an example

Enqueue A,B,C then dequeue returns A, leaving B,C. A stack would return C and process tasks in a different order.

Time and space complexity

Deque endpoint operations O(1); n pending items use O(n) memory.

Why it works

The front is the oldest pending item.

Common mistakes

• list.pop(0) costs O(n) shifting.
• Empty queues need a defined error or sentinel behavior.

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]