Following Okasaki's lead, we design our first functional queue by using two stacks. One stack will be used to to store the data, while the second stack will be used for temporary storage for the dequeue operation.
Note
Cornell's CS3110 Recitation 7 on Functional stacks and queues, dictionaries, fractions is an informative and recommended reading on functional data structures. For more information, go to www.cs.cornell.edu/Courses/cs3110/2011sp/recitations/rec07.htm.
In the following algorithm, you will see this data structure unfold. Let StackQ be the stack in which we store the data, and let StackTemp be a temporary data structure.
The Enqueue operation is essentially just a stack push.
Enqueue(o): StackQ.push(o)
However, the dequeue operation requires a bit more work. While dequeueing, we pop items off the StackQ until we get to the bottom (first-entered) element, using stackTemp as a temporary store which conveniently gives back the items in the correct order...