Question

The queue data structure is to be realized by using stack. The number of stacks needed would be
1. It cannot be implemented
2. 2 stacks
3. 4 stacks 
4. 1 stack

Answer 1

Correct Answer - Option 2 : 2 stacks

The correct answer is option 2:

Method 1 (efficient push):

• push:
  • enqueue in queue1
• pop:
  • while the 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

Method 2 (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