Problem statement

https://leetcode.com/problems/implement-queue-using-stacks/

Solution

We need to use two stacks, so called StackIn and StackOut. We always push to StackIn, and pop from StackOut. If StackOut is empty, we push all elements from StackIn to StackOut.

Complexity

Complexity of push, peek, empty is O(1). Complexity of pop can be O(n), however amortized complexity is O(1).

Code

class MyQueue:
    def __init__(self):
        self.s1, self.s2 = [], []
        
    def push(self, x):
        self.s1.append(x)
        
    def pop(self):
        self.peek()
        return self.s2.pop()

    def peek(self):
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2[-1]    

    def empty(self):
        return not self.s1 and not self.s2