A deque (pronounced “deck”) is a double-ended queue, a data structure that lets you add and remove items at either end. A monotonic queue uses those operations to keep the candidates for a running maximum or minimum in value order. A market-data monitor can use one to track the largest trade size in its last few observations without scanning the whole window on every trade.
Choose the end to match the job
Add on the right and remove on the left for first-in, first-out (FIFO). Add and remove at the same end for last-in, first-out (LIFO). The deque gives you both choices. Your application decides when to use each one. Java SE deque interface
Suppose a fictional market-data repair worker appends routine jobs A and B to the right, in that order. It prepends urgent job U to the left, giving U, A, B from left to right. The worker takes the next job from the left and gets U. An operator then withdraws the most recently queued routine job from the right and gets B. A is the only job left.
The worker serves U first because the application chose where to put it and which end to serve. Two successive urgent arrivals placed on the left would put the newer one ahead of the older one. A priority queue instead selects the next job by a priority key, with a separate tie-breaker if arrival order matters. Python priority queue notes
Keep only possible window maxima
Take the last three trade sizes, including the current trade, and assume observations arrive in the order the monitor uses. Store each candidate's arrival index and size. At each arrival:
- Remove expired indices from the left. For arrival and width , discard any index at or before .
- Remove superseded candidates from the right. Pop while the rightmost size is at most the new size. The newcomer is at least as large and will stay in the window longer, so the older candidate cannot win a future window.
- Append the new observation on the right. The remaining sizes decrease from left to right, so the leftmost size is the maximum. Dropping equal older candidates makes the most recent trade win ties if you also report the maximum's location.
The left end removes expired trades. The right end removes trades superseded by a newer size. Each row shows the deque after appending the new trade.
When the fourth trade arrives, 8 lots falls out of the window. The 5-lot candidate is still in range and moves to the front. When the sixth trade arrives, 5 lots expires and the incoming 6 lots supersedes both 2 and 4 lots. Those smaller trades are still in the window, but neither can be its maximum. Reverse the size comparison to track the minimum.
Each observation enters the deque once and can leave at most once. With constant-time end operations and size comparisons, processing observations takes total time and stores at most candidates, even though one arrival can remove several candidates. Expiry comes from observation indices. For a time-based window with ordered timestamps, expire candidates by the time cutoff instead. Lemire, Streaming Maximum-Minimum Filter, §4
What Python provides
The deque interface specifies the end operations. A circular array can implement that interface by wrapping its end indices around the array. CPython 3.14 stores its
collections.deque in a chain of doubly linked fixed-size blocks with a reference to each end. Its appends and pops take approximately constant time at either end. Indexing into the middle can take linear time. Python deque documentation · CPython implementationOn a full Python deque with a positive
maxlen, appending evicts an item at the opposite end. If it holds A and B from left to right, appending C on the right leaves B and C. That's useful for retaining recent observations. A queue of pending jobs needs an explicit policy for a full queue, since eviction would silently discard a job. In a monotonic queue, length also gives the wrong expiry signal because many observations never remain as candidates. Python bounded deque behaviourFurther reading
Compare FIFO and LIFO and see how their operation costs depend on the underlying storage in Arrays, Linked Lists, Stacks, and Queues (public preview, full lesson with membership).