Deques and operations at both ends

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 deque supports insertion/removal at both ends. It can act as a stack, queue, or ordered candidate buffer. Specify which end corresponds to newest and oldest data.

Work through an example

append adds newest at the right; popleft removes oldest at the left. appendleft and pop support the opposite direction.

Time and space complexity

O(1) endpoint work; arbitrary middle indexing/removal is not the same guarantee.

Why it works

Endpoint operations preserve the order of remaining items.

Common mistakes

Do not treat a deque as an O(1) random-access array.
Mixing end conventions accidentally reverses processing.

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.