Is there a way to implement a queue using two stacks, but with enqueuing 0(1)?
I have been learning how to do a queue and one of the questions that I've been trying to find an answer for is how can I optimise a queue using two stacks. The code that I've impemented seems to have a worst runtime.
Below is my code, could I've approached this differently?
class Queue:
def __init__(self):
self.s1 = []
self.s2 = []
def enqueue(self, item):
while len(self.s1) != 0:
self.s2.append(self.s1.pop())
self.s1.append(item)
while len(self.s2) != 0:
self.s1.append(self.s2.pop())
def dequeue(self):
if len(self.s1) == 0:
raise IndexError("Cannot pop from an empty queue")
return self.s1.pop()
Queue()
Actually you can implement queue using 2 stacks with enqueuing O(1), by dequeuing O(n). Here is an example, using your code:
def enqueue(self, item):
self.s1.append(item)
def dequeue(self):
if len(self.s1) == 0:
raise IndexError("Cannot pop from an empty queue")
queue_head = None
# Search for the first item put in queue
while len(self.s1) != 1:
self.s2.append(self.s1.pop())
# Save the item while we restore s1's data
queue_head = self.s1.pop()
while len(self.s2) != 0:
self.s1.append(self.s2.pop())
return queue_head
If you can't make both enqueuing and dequeuing to be O(1), and must choose one to be with higher complexity(Usually the one you will use the most).