Suppose we have two stacks and no other temporary variable.
Is to possible to "construct" a queue data structure using only the two stacks?
algorithmdata structuresqueuestack
Suppose we have two stacks and no other temporary variable.
Is to possible to "construct" a queue data structure using only the two stacks?
Best Answer
Keep 2 stacks, let's call them
inbox
andoutbox
.Enqueue:
inbox
Dequeue:
If
outbox
is empty, refill it by popping each element frominbox
and pushing it ontooutbox
Pop and return the top element from
outbox
Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.
Here's an implementation in Java: