How do you implement a stack using two queues?

Answer 1

implementing stack using two queues

initially q1 is full and q2 empty

1] transfer 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

Answer 2

If this is a homework assignment, please consider doing this yourself first, otherwise you will lose the value of the reinforcement of the lesson that doing the homework provides.

To reverse the elements of a stack, you do not need two additional queues. You either need one additional queue, or you need a second stack.

The algorithm using an additional queue is to pop the elements off of the stack and place them in a queue. Once the stack is empty, read the queue and push the elements back onto the stack. When done, the stack will be in reverse order.

The algorithm using a second stack is very similar. Pop the elements off of the first stack and push them onto the second stack. When done, replace the first stack with the second stack.

Answer 3

A stack is a last-in-first-out type of data structure. A queue is a first-in-first-out type of data structure. The two types are sufficiently inconsistent to make the question unanswerable - the question does not make sense.

If anyone knows an acceptable alternative usage, please feel free to refine the answer.

Answer 4

It is not possible to efficiently construct a queue (first in, first out storage structure) using two or more stacks (last in, first out storage structures). I leave the proof of this as an exercise, but the generalized pidgeonhole principle may be useful in understanding why this is so.

However, a queue can be implemented using stacks in an inefficient way as follows: when items are pushed onto the queue, put them on top of stack #1. When an item is retrieved from the queue, (1) repeatedly pop items off of stack #1 and push them onto stack #2, thereby reversing their order; (2) pop the top item off stack #2 and return it to the caller; (3) set a boolean flag for future reference so you know to reverse step #1, when items needs to be pushed onto the queue again.

Does that answer your homework question?

Answer 5

You could store the data in an array, and maintain a variable that points to the bottom of stack (i.e., the array index of the last element you added).

You could store the data in an array, and maintain a variable that points to the bottom of stack (i.e., the array index of the last element you added).

You could store the data in an array, and maintain a variable that points to the bottom of stack (i.e., the array index of the last element you added).

You could store the data in an array, and maintain a variable that points to the bottom of stack (i.e., the array index of the last element you added).

Answer 6

Consider two stacks p1 and p2 of same size.

Enqueue:

Push element into p1. If p1 is full, then pop all elements from p1 and push it into p2. Now push the new element into p1.

Dequeue:

Pop element from p2. If p2 is empty, the pop all elements from p1 and push it into p2. Now pop element from p2.

Answer 7

There are two methods on how to implement queue by using two stacked in Java. First by making enqueue operation cost and second one by making dequeue operation costly.

Answer 8

Implement a generic stack-type, and create two instances of it.

Answer 9

Please don't quote homework assignments as questions.

Answer 10

You could store the data in an array, and maintain a variable that points to the bottom of stack (i.e., the array index of the last element you added).