How to implement a queue using stack?

1.	How to implement a queue using stack?
Answer» A queue can be implemented using two stacks. Let q be the queue andstack1 and stack2 be the 2 stacks for implementing q. We know that stack supports push, pop, and peek operations and using these operations, we need to emulate the operations of the queue - enqueue and dequeue. Hence, queue q can be implemented in two methods (Both the methods use auxillary space complexity of O(n)): 1. By making enqueue operation costly: Here, the oldest element is always at the top of stack1 which ensures dequeue operation occurs in O(1) time complexity. To place the element at top of stack1, stack2 is used. Pseudocode: Enqueue: Here time complexity will be O(n) enqueue(q, data): While stack1 is not empty: Push everything from stack1 to stack2. Push data to stack1 Push everything back to stack1. Dequeue: Here time complexity will be O(1) deQueue(q): If stack1 is empty then error else Pop an item from stack1 and return it 2. By making the dequeue operation costly: Here, for enqueue operation, the new element is pushed at the top of stack1. Here, the enqueue operation time complexity is O(1). In dequeue, if stack2 is empty, all elements from stack1 are moved to stack2 and top of stack2 is the result. Basically, reversing the list by pushing to a stack and returning the first enqueued element. This operation of pushing all elements to a new stack takes O(n) complexity. Pseudocode: Enqueue: Time complexity: O(1) enqueue(q, data): Push data to stack1 Dequeue: Time complexity: O(n) dequeue(q): If both stacks are empty then raise error. If stack2 is empty: While stack1 is not empty: push everything from stack1 to stack2. Pop the element from stack2 and return it.

Answer»

A queue can be implemented using two stacks. Let q be the queue andstack1 and stack2 be the 2 stacks for implementing q. We know that stack supports push, pop, and peek operations and using these operations, we need to emulate the operations of the queue - enqueue and dequeue. Hence, queue q can be implemented in two methods (Both the methods use auxillary space complexity of O(n)):

1. By making enqueue operation costly:

Here, the oldest element is always at the top of stack1 which ensures dequeue operation occurs in O(1) time complexity.

To place the element at top of stack1, stack2 is used.

Pseudocode:
- Enqueue: Here time complexity will be O(n)

enqueue(q, data):
While stack1 is not empty:
Push everything from stack1 to stack2.
Push data to stack1
Push everything back to stack1.

Dequeue: Here time complexity will be O(1)

deQueue(q):
If stack1 is empty then error else
Pop an item from stack1 and return it

2. By making the dequeue operation costly:

Here, for enqueue operation, the new element is pushed at the top of stack1. Here, the enqueue operation time complexity is O(1).

In dequeue, if stack2 is empty, all elements from stack1 are moved to stack2 and top of stack2 is the result. Basically, reversing the list by pushing to a stack and returning the first enqueued element. This operation of pushing all elements to a new stack takes O(n) complexity.

Pseudocode:
- Enqueue: Time complexity: O(1)

enqueue(q, data):
Push data to stack1

Dequeue: Time complexity: O(n)

dequeue(q):
If both stacks are empty then raise error.
If stack2 is empty:
While stack1 is not empty:
push everything from stack1 to stack2.
Pop the element from stack2 and return it.

How to implement a queue using stack?

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment