Leetcode 225. Implement Stack using Queues

Problem

Leetcode 225 - Implement Stack using Queues

Example:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Approach

Stack is LIFO (last element that gets added to list pops out first)

Queue is FIFO (first element that gets added to list pops out first)

Thus, if we wanted to implement Stack using Queue, we have to keep in mind that when we add we have to make sure that the added element is going to be popped out first.

Here is the Python code for the solution:

class myStack:
    def __init__(self):
        self.q = deque()
    
    def push(self, x: int) -> None:
        self.q.append(x)
        # because we want the element that gets added last to be popped out first we can shift the queue so 'x' is at the end.
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())
    
    # we don't have to worry about popping since we rearranged the queue
    def pop(self) -> int:
        return self.q.popleft()
    
    # we don't have to worry about top since we rearranged the queue
    def top(self) -> int:
        return q[0]
    
    def empty(self) -> bool:
        return len(self.q) == 0

Time Complexity and Space Complexity

Time Complexity: $O(1)$ for each operation but push, push will cost $O(n)$

Space Complexity: $O(n)$