"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.
And here I was, patting myself on the back for getting to 90% comprehension for the regular amortized approach. (I feel like I just barely understand it, which means I probably don't!)
I haven't read the de-amortized approach yet other than skimming the article, but my initial feeling is the two-stack approach is quite a bit simpler/easier to understand. At least by the line count of the sample code, the de-amortized code is quite a bit longer. Whereas one of the merits of the two stacks is that you can sum up the approach in a paragraph and get over halfway there.
Thanks for the link! I'll have to come back to this when I have more time.
I think it's almost universally the case that, whenever there's a choice, the amortized approach is simpler and has better throughput; it's a textbook latency vs throughput trade-off. Think of something as basic as the classic table doubling algorithm for dynamic arrays, where push is amortized O(1) time but worst-case O(n) time, compared to the simplest worst-case O(1) time incrementalized design. Similarly, relaxed deletion is an entire genre of throughput vs latency trade-offs in data structure design that increases throughput (and average-case latency, like with O(1) amortized array push) and lowers implementation complexity at the expense of worst-case latency.
I only recently realized that the classic two-stack queue makes a great MPSC concurrent queue, where the "push" stack is lock-free, and the "pop" stack is sequential.
I think the missing citation here (alluded to in TFA) is the stronger guarantee (avoids latency spike) Hood & Melville's Real-time queue operations in pure LISP (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.
pervognsen | a day ago
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:
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.
bitshift | 17 hours ago
And here I was, patting myself on the back for getting to 90% comprehension for the regular amortized approach. (I feel like I just barely understand it, which means I probably don't!)
I haven't read the de-amortized approach yet other than skimming the article, but my initial feeling is the two-stack approach is quite a bit simpler/easier to understand. At least by the line count of the sample code, the de-amortized code is quite a bit longer. Whereas one of the merits of the two stacks is that you can sum up the approach in a paragraph and get over halfway there.
Thanks for the link! I'll have to come back to this when I have more time.
pervognsen | 9 hours ago
I think it's almost universally the case that, whenever there's a choice, the amortized approach is simpler and has better throughput; it's a textbook latency vs throughput trade-off. Think of something as basic as the classic table doubling algorithm for dynamic arrays, where push is amortized O(1) time but worst-case O(n) time, compared to the simplest worst-case O(1) time incrementalized design. Similarly, relaxed deletion is an entire genre of throughput vs latency trade-offs in data structure design that increases throughput (and average-case latency, like with O(1) amortized array push) and lowers implementation complexity at the expense of worst-case latency.
tobin_baker | 24 minutes ago
I only recently realized that the classic two-stack queue makes a great MPSC concurrent queue, where the "push" stack is lock-free, and the "pop" stack is sequential.
cblake | a day ago
I think the missing citation here (alluded to in TFA) is the stronger guarantee (avoids latency spike) Hood & Melville's Real-time queue operations in pure LISP (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.nimor/embist.nimor 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.