DSA The Monotonic Queue
A monotonic queue is a deque kept in decreasing order so its front always holds the largest live value. It serves a sliding window, where old values expire from the front and smaller values are dropped from the back.
Smaller values leave from the back
Each new value removes smaller values behind it. The front stays the largest value still present.
from collections import deque
dq = deque()
for value in [4, 2, 5, 1]:
while dq and dq[-1] < value:
dq.pop()
dq.append(value)
print(value, "->", list(dq), "front:", dq[0])Old indices expire from the front
The deque stores indices, not values. An index older than the window leaves before the front is read.
from collections import deque
window = deque()
data = [7, 3, 9, 2]
k = 3
for i, value in enumerate(data):
while window and window[0] <= i - k:
window.popleft()
while window and data[window[-1]] <= value:
window.pop()
window.append(i)
print("index", i, "holds indices", list(window), "max at front:", data[window[0]])Pops stay below pushes
Five values enter the deque. Only three back pops happen across the whole run.
from collections import deque
dq = deque()
pops = 0
for value in [1, 3, 2, 5, 4]:
while dq and dq[-1] < value:
dq.pop()
pops += 1
dq.append(value)
print("deque:", list(dq))
print("back pops:", pops, "for 5 pushes")Example
from collections import deque
def window_maxima(nums, k):
window = deque()
maxima = []
pushes = 0
pops = 0
for i, value in enumerate(nums):
while window and window[0] <= i - k:
window.popleft()
pops += 1
while window and nums[window[-1]] <= value:
window.pop()
pops += 1
window.append(i)
pushes += 1
if i >= k - 1:
maxima.append(nums[window[0]])
print("window ending at", i, "-> deque values",
[nums[j] for j in window], "max:", nums[window[0]])
return maxima, pushes, pops
nums = [1, 3, -1, -3, 5, 3, 6, 7]
maxima, pushes, pops = window_maxima(nums, 3)
print("maxima:", maxima)
print("pushes:", pushes, "pops:", pops, "for", len(nums), "values")Key points
- Monotonic queue: a deque whose values never increase from front to back
- A new value pops every smaller value behind it before joining
- A popped value can never lead any future window
- Indices are stored, so an expired front leaves by position, not by value
- Each index enters once and leaves once, so n values cost at most 2n moves
In this example, a window of size 3 slides over eight values. The deque contents are printed at each step, and the front value is always the window maximum. The maxima list matches a hand check of the six windows. Eight pushes and seven pops serve eight values, which shows the one-entry and one-exit rule in the counts.
Note
equal values may replace older equals, since the newer index expires later
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A value of 9 arrives at a monotonic queue holding [7, 5, 3]. What happens?