edited by
24,135 views
22 votes
22 votes

What is the minimum number of stacks of size $n$ required to implement a queue of size $n$?

  1. One
  2. Two
  3. Three
  4. Four
edited by

7 Answers

4 votes
4 votes
  • During Enqueue operation, we can straight away push the element into the stack.

  • During Dequeue operation,

    • Pop all the elements from Main Stack recursively until Stack size is equal to 1.
    • If Stack size = 1, Pop item from Stack, and return the same item.
    • Push all popped element back to Stack.

Using this method we can use only Single Stack to implement a queue

0 votes
0 votes
Two. One stack is used for enqueue operations, and the other stack is used for dequeue operations. The enqueue stack is used to push elements onto the queue, and the dequeue stack is used to pop elements off of the queue. To implement a queue using stacks, the elements are first pushed onto the enqueue stack. When a dequeue operation is performed, the elements are popped from the enqueue stack and pushed onto the dequeue stack. The top element of the dequeue stack is then returned as the dequeued element. This process ensures that the first element pushed onto the queue is also the first element to be popped off of the queue, which is the behavior of a queue.
–5 votes
–5 votes
Just one stack is needed to implement queue.

If stack is implemented using single link list then, we can traverse till the bottom of stack and return the value which should be returned for pop() operation.
Answer:

Related questions

25 votes
25 votes
2 answers
2