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.
