Circular buffers

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

A circular buffer stores a queue in a fixed-capacity array. Head identifies the next removal; size distinguishes full from empty. The next insertion slot is (head+size)%capacity.

Work through an example

Capacity 3, enqueue A,B,C, dequeue A, enqueue D reuses slot zero. Logical order B,C,D differs from physical array [D,B,C].

Time and space complexity

O(1) operations/O(capacity) storage; reject or define overflow when full.

Why it works

The live queue occupies size slots starting at head with modular wraparound.

Common mistakes

head==tail is ambiguous without size or an unused slot.
Capacity zero cannot be used as a modulus.

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.