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

Question

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

Answer 1

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

Answer 2

It is possible to have both enqueue and dequeue run in amortized O(1) (assuming append and pop are both O(1)). The idea is being lazy and not moving elements from s1 to s2 unless you absolutely have to.

def enqueue(self, item):
  self.s1.append(item)

def dequeue(self):
  if len(self.s2) == 0:
    while (len(self(s1)) > 0):
      s2.append(s1.pop())
  if len(self.s2) == 0:
    raise IndexError("Cannot pop from an empty queue")
  return s2.pop()

An element is appended to s1, gets moved to s2 exactly once, and gets popped from s2. A sequence of N enqueue and dequeue operations takes O(N) time.