algorithmdata-structuresstacktask-queueenqueue

Creating a queue using two stack, but make enqueuing O(1)


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()


Solution

  • 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).