One interface, two internal orders
A first-in-first-out queue returns the oldest item still present. A stack instead removes the most recently pushed item. Using two stacks can reverse order twice, but only if a transfer happens at the right time. The queue's logical order must be specified independently of the arrays or linked structures used to implement its stacks.
Assume both stacks begin empty, each stack push or pop costs one elementary operation, and comparisons, emptiness tests and returning an item take constant time. An empty dequeue reports underflow; the cost bound below counts successful enqueues and dequeues.
Operations and an invariant
Definition 2.1.1
(Two-stack queue)
Call the input stack and output stack . Enqueue pushes the new item onto . To dequeue, if is empty, repeatedly pop from and push onto until is empty; then pop and return the top of . If both stacks are empty, report underflow instead.
Theorem 2.1.2
(Logical queue order)
At every operation boundary, the logical queue from oldest to newest is the sequence in read top to bottom, followed by the sequence in read bottom to top.
Proof
(Induction over operations)
Initially both sequences are empty. Enqueue puts the new item at the top of , which is the end of its bottom-to-top sequence, so it appends to the logical queue. If is nonempty, its top is the first logical item, and popping it removes exactly that item. If is empty and is nonempty, moving all items reverses their stack order: the old bottom of becomes the top of , so the old bottom-to-top input sequence becomes the new top-to-bottom output sequence. Popping it returns the oldest item. These cases prove the invariant and FIFO behavior by induction over operations.
Proof X-ray
Why transfer waits until the output stack is empty
Items already in arrived before all items currently in . Moving newer input items onto a nonempty would put them above older output items and change the next answer. For example, with holding and holding , transferring prematurely makes the top even though the queue order is . The empty-output condition preserves the boundary between the two age groups.
Common mistake
(Moving only one item at the transfer)
Let (bottom to top) and , so the queue order is . If the transfer moved only the top item of , then and the dequeue would return although is the oldest item. The transfer must move all of , which reverses its order, so that the old bottom ends on top of .
A trace
Worked example 2.1.3
(Interleaved enqueues and dequeues)
Write stacks from bottom to top. Enqueue : . A dequeue transfers the input to , then returns , leaving . Enqueue to obtain . The next two dequeues return and without transfer. Finally is empty, so is transferred and returned. The returned sequence is .
Counterexample mode
Amortized does not mean every operation is cheap
If items wait in and is empty, one dequeue performs pops from , pushes to , and one pop from : stack operations. That single operation is not worst-case constant time, even though an operation sequence can have constant amortized cost per successful operation.
Worked example 2.1.4
(Underflow and a single item)
Start with both stacks empty. A dequeue finds and both empty and reports underflow without any stack operation. Enqueue : . A dequeue now transfers one item, with one pop from and one push onto , then pops from : cost , and the stacks are empty again. A further dequeue reports underflow. The cost bound counts only the successful dequeue.
Worked example 2.1.5
(A sequence that attains the bound)
Enqueue : four pushes, and potential . The first dequeue transfers four items, then pops : operations, leaving . The next three dequeues cost one each, returning . The total is , and . Equality holds, because every item was transferred once and every item was dequeued.
Account for the transfers
Theorem 2.1.6
(Total cost of a sequence of operations)
Starting from two empty stacks, a sequence with enqueues and successful dequeues uses at most stack operations. Hence the cost per successful operation is amortized, although a single dequeue can cost when items wait in .
Proof
(Each item moves at most three times)
For a sequence with enqueues and successful dequeues, every item is pushed onto once and transferred at most once. The total is at most stack operations: one input push, at most one input pop and output push per enqueued item, and one output pop per successful dequeue. Some enqueued items may remain in either stack, so this is an upper bound rather than an assertion that every transfer occurs.
Equivalently, use potential , initially zero and always nonnegative. Enqueue has actual cost one and increases potential by two, giving amortized cost three. A dequeue without transfer costs one and leaves potential unchanged. A dequeue transferring items has actual cost and decreases potential by , giving amortized cost one. Summing actual costs plus changes in potential telescopes; since final potential is nonnegative, total actual stack cost is no more than . The initial-empty assumption matters: items preloaded in would contribute positive initial potential.
Common mistake
(Choosing a potential that is too small)
With instead of , enqueue has amortized cost , but a dequeue that transfers items has amortized cost , which is not constant. The argument would then prove nothing. The factor two pays for both later moves of an item, the pop from and the push onto ; with the transfer costs amortized.
Exercises with solutions
Quick check
(If bottom to top and bottom to top, write the logical queue.)
Solution · Answer
: read from top to bottom and then from bottom to top.
Quick check
(Starting empty, enqueue , dequeue once, enqueue , then dequeue twice. What is returned?)
Solution · Answer
The results are . After returning , remains at the top of and must precede newly enqueued .
Quick check
(If a dequeue transfers three items, give its actual stack-operation cost and potential change.)
Solution · Answer
The cost is ; falls by three, so and the amortized cost is one.
Quick check
(Why is transferring on every enqueue incorrect when is nonempty?)
Solution · Answer
It can place a newer item above an older output item. The proof example with in and in shows the order violation.