4 ms·
If you're wondering, the "two stacks queue" is an easy way to write a simple immutable queue for a functional programming language. You use one functional stack
by cynicalkane 13y ago
If you're wondering, the "two stacks queue" is an easy way to write a simple immutable queue for a functional programming language. You use one functional stack for enqueueing and one for dequeueing. When the dequeue stack is exhausted the enqueue stack is "flipped" into the dequeue. Amortized runtime is O(1) per operation.
- dpiers 13y agoOnce they told me to use one stack for enqueueing and one for dequeueing, I immediately solved the problem. What I didn't understand is why you would a.) implement your own queue structure and b.) implement it in such a non-intuitive way. Now that I know this would be for a functional language, it makes way more sense. At the time I couldn't get over why you wouldn't just use a doubly-linked list like the standard implementation in most OO languages.