Queue is a First In First Out (FIFO) data structure whereas Stack is a Last In First Out (LIFO) data structure. However, we can implement a Queue using two Stacks.
Here’s how:
- Let’s say we have two stacks: S1 and S2.
- Enqueue operation (insert operation) is implemented using the S1 stack.
- When performing a Dequeue operation (delete operation), if the S2 stack is empty, pop all elements from S1 and push them to S2. Then pop the top element from S2.
- If the S2 stack is not empty during the Dequeue operation, simply pop the top element from the S2 stack.
Below is a Python implementation of the aforementioned:
class Queue:
def __init__(self):
self.s1 = []
self.s2 = []
def enqueue(self, item):
self.s1.append(item)
def dequeue(self):
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()To explain the above code:
- Enqueue operation: A new element is always added to S1 stack.
- Dequeue operation: If S2 is not empty then the top of the stack is returned, else all the elements from S1 are moved to S2 and finally top of S2 is returned.
The complexity of the enqueue operation (i.e., adding an item) is O(1), and dequeue operation varies:
- If S2 already contains elements, the complexity is O(1).
- If S2 is empty, we have to transfer n elements from S1 to S2, which gives a complexity of O(n).
However, in Amortized Complexity analysis, which is the total time taken for n operations or the average time per operation, the dequeue operation is O(1). This is because for n insertions there will be n deletions. Therefore, every element is transferred from S1 to S2 only 2 times. Hence the amortized complexity is O(1).