Leetcode 232. Implement Queue using Stacks

Problem

Leetcode 232 - Implement Queue using Stacks

Example:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Approach

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

Stack is LIFO (last 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 first added element is going to be popped out first.

Here is the Python code for the solution:

class myQueue:
    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> int:
        val = self.stack[0]
        new_stack = self.stack[1:]
        self.stack = new_stack
        return val

    def peek(self) -> int:
        return self.stack[0]

    def empty(self) -> bool:
        return len(self.stack) == 0     

Time Complexity and Space Complexity

Time Complexity: $O(1)$ for each operation

Space Complexity: $O(n)$