stack using two queues

Question

Possible Duplicate:
Implement Stack using Two Queues

I want the most efficient way in terms of time complexity to implement stack using two queues

Answer 1

I may be wrong, but to me this does not compute.

A Queue is (typically) a FIFO structure, a Stack is a LIFO structure. I cannot off the top of my head envisage any simple combination of 2 FIFO's that will yield a LIFO, though I simply may not have had enough coffee yet today.

It may be possible, but I suspect that an implementation of a stack involving 2 queues is almost certainly going to take longer to implement and be more error prone than a simple implementation of a stack.

However, having said that...

If you already have a Queue implementation and if that Queue allows you to remove items from it's TAIL rather than from the HEAD (actual terms may differ in your implementation) then you can simply use the Queue as if it were a stack by retrieving items from the TAIL.

Answer 2

It is simple, Let's say you have Queue A and Queue B u use one queue to hold data, and other as a temporary container... BUT A and B interchange roles all the time:

When you first insert data, you insert into Queue A. To POP the last Item you inserted, you DEQUE all of Queue A elements except the last one and ENQUEUE them in Queue B. DEQUEUE the only element from Queue A and you've got what you want: The TOP of the stack, the last element... etc...

Now to POP the latest item, you re-do the same work but A and B interchange roles

Answer 3

I don't get why you'd ever need two queues. I've seen the answers here and in the dupe thread, and you can do it with just one queue.

From the dupe thread, this has two versions, one that optimizes push, and one that optimizes pop.

Push optimized:

push:  
    enqueue in queue  
pop:  
    n = queue size.
    dequeue an object, and enqueue it immediately after. Do this n - 1 times.
    dequeue object, and return this.

Pop optimized:

push:
    enqueue in queue
    n = queue size.
    dequeue an object, and enqueue it immediately after. Do this n - 1 times.
pop:
    dequeue from queue and return.

Then again, I don't get why you'd ever want to do this ever. Lambast your professor for making you waste your time with pointless programming questions.