Leetcode 0225 Implement Stack using Queues

Problem statement

https://leetcode.com/problems/implement-stack-using-queues/

Solution

Let us use 2 queues. When we push we put element to the right of queue q1. When we pop, we first extract elements from q1 and put them to q2. Then we extract one more element out = q1.popleft() and change places of our queues, finally we return out.

Complexity

Time complexity for pop is O(n), for other operations complexity is O(1). Space complexity is O(n).

Code

class MyStack:
    def __init__(self):
        self.q1, self.q2 = deque(), deque()
        self._top = None
        
    def push(self, x):
        self.q1.append(x)
        self._top = x
        
    def pop(self):
        while len(self.q1) > 1:
            self._top = self.q1.popleft()
            self.q2.append(self._top)
            
        out = self.q1.popleft()
        self.q1, self.q2 = self.q2, self.q1
        return out
        
    def top(self):
        return self._top

    def empty(self):
        return not self.q1

Remark

We can actually use only one queue with the same complexities, we put this element to our queue and then rotate it n times: pop and push to itself. However there is no solution with O(1) complexities for all operations.