Two-Stack Sliding-Window Aggregation

See also @pkhuong's https://pvk.ca/Blog/2025/08/19/monoid-augmented-fifos/ for a deamortized approach. As a lead-in, he summarizes the classic two-stack approach in a paragraph (and goes on to explain why it's a dead-end for deamortization):

"There’s a cute construction in the purely functional (strict or lazy, doesn’t matter) data structure folklore for a FIFO queue augmented with a monoid. The construction builds on two observations:

• It’s trivial to augment a stack with a monoid such that we can always get the product of all the values in the stack: multiply the previous product by the new value when pushing, and keep a pointer to the previous (cons-)stack. Pop dereferences the CDR.
• We can construct an amortised queue from two stacks, an ingestion stack that accepts new values and an excretion stack for exiting values: popping from stack A and pushing onto stack B ends up reversing the contents of A on top of B."

The non-augmented two-stack queue by itself is of course even more classic, including outside of the purely functional world. I remember first learning about it as a kid when doing the exercises in Knuth, where it shows up in at least one exercise, so I assume its vintage dates back to the 1960s. But as Paul says, the augmented two-stack queue is just that plus the even simpler idea of stack augmentation; I'm not sure when that specific combination first showed up in the folklore, but I wouldn't be shocked if it's ancient history as well.

I think the missing citation here (alluded to in TFA) is the stronger guarantee (avoids latency spike) Hood & Melville (1981) or the follow-up in Tarjan's quite famous textbook Data Structures and Network Algorithms 1983 (a little past the article's 1970s and not "obscure" at all). I was amused that all 3 are "Robert"s.

For the more general case of efficient non-aggregative (i.e. histogram/full distro-sensitive) incremental/online (i.e. push & pop) quantiles/etc., the fastest algos I know are in https://github.com/c-blake/adix/ , specifically adix/bist.nim (or /lmbist.nim or /embist.nim or etc.) (though I cannot find any citation pointing that out). They do have limited "resolution" (i.e. quantization error might be 3..6 significant figures depending upon CPU cache budgets), but in my experience that is already far more accurate than statistics are stable.