To implement a stack using two queues

[preethis]

Hi,

How to implement a stack using two queues ? Help pls!

Regards,
Preethi

[Dogtree]

Think of it this way: For each new value that's pushed onto the 'stack', you pop all of the values from queue1 onto queue2, then push the new value onto queue1. Taking a simple example, say you have queue1 with a single value, 1, and you want to push 2 onto it so that the next pop gives you 2 instead of 1:

queue1: * 1
queue2: *

Empty queue1 onto queue2:

queue1: *
queue2: * 1

Push 2 onto queue 1:

queue1: * 2
queue2: * 1

Then empty queue2 onto queue1:

queue1: * 1 2
queue2: *

So now, by pushing 1 and then 2 onto the queue this way, popping them both off would give you 2 1, just like a stack, instead of 1 2, like a queue.

[preethis]

Hi,

Is there a mistake in the last step ?

The last step that is given is:
Then empty queue2 onto queue1:
queue1: * 1 2
queue2: *
I think the last step is :
queue1: * 2 1
queue2: *
Is it right ??

[Dogtree]

> Is it right ??
No, you're thinking that the left side of my queues designate the front, which wasn't the intention. It works like this in the example that I gave:

New values go in here -> 1 2 -> Old values come out here

If you want to think of it the other way around, that's okay too, just reverse the values.

[absolutely]

implementing stack using two queues

initially q1 is full and q2 empty
1] tranfer elements from q1 to q2 till last element left in q1
2] loop till q2 is not empty
deque element from q2 and again push in q2 till last element is left in q2
transfer this last element in q1
reduce size of q2 by 1
3]finally q1 contains all elements in reverse order as in stack
eg

1]
q1 = 1 2 3 4
q2 =
2]
3 deques till last element left in q1
q1 = 4
q2 = 1 2 3
3]
deque and again queue q2 till last element left
q1 = 4
q2 = 3 1 2
4] deque q2 and queue q1
q1 = 4 3
q2 = 1 2
5] again
deque and queue q2 till last element left
q1= 4 3
q2= 2 1
6] queue q1
q1= 4 3 2
7] queue last element of q2 to q1
q1= 4 3 2 1