Implement Stack using Two Queues
algorithm, data-structures, stack
Solution
Version A (efficient push):
- push:
- enqueue in queue1
- pop:
- while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
- dequeue and return the last item of queue1, then switch the names of queue1 and queue2
Version B (efficient pop):
- push:
- enqueue in queue2
- enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2
- pop:
- deqeue from queue1
Problem
A similar question was asked earlier there, but the question here is the reverse of it, using two queues as a stack. The question... Given two queues with their standard operations (`enqueue`, `dequeue`, `isempty`, `size`), implement a stack with its standard operations (`pop`, `push`, `isempty`, `size`). There should be two versions of the solution. - Version A: The stack should be efficient when pushing an item; and - Version B: The stack should be efficient when popping an item. I am interested in the algorithm more than any specific language implementations. However, I welcome solutions expressed in languages which I am familiar (java,c#,python,vb,javascript,php).