🍡232. Implement Queue using Stacks

Easy | Grind 75 | September 7th Wednesday, 2022

mplement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.

• int pop() Removes the element from the front of the queue and returns it.

• int peek() Returns the element at the front of the queue.

• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Constraints:

• 1 <= x <= 9

• At most 100 calls will be made to push, pop, peek, and empty.

• All the calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Example 1

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

SOLUTION

Stacks are Last In First Out (LIFO) whereas queues are First In First Out. The fact that the question asks you to use two stacks is a huge giveaway. What we need to realize is the pattern created by popping items from a stack and then appending items immediately. When you pop and append, the order of the elements is reversed. The oldest item that was in the original stack will now be the top item in the stack after popping and appending. Given this intuition, when new items come, push them to the first stack. Pop the first stack and append the popped items to the second stack. This reverses the order, making the second stack like a queue. The oldest element will now be at the top of the second stack.

The coding implementation is as follows: we will pop items from the first stack(variabler stack) and append them to the second stack(variable queue) only when the second stack is empty. This will result in a better-amortized runtime. Whenever the function peek or pop is called, we check to see if there are elements in the second stack. If there are, we can pop from the second stack and return it. However, if the second stack is empty, we need to pop from the first stack and append it to the second stack and return the topmost element of second stack.

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

    def push(self, x: int) -> None:
        # push will always append the item to our stack list
        self.stack.append(x)

    def pop(self) -> int:
        # need to check if our queue list is empty
        if not self.queue: 
            
            #if empty, move all the elments from stack to queue
            while self.stack: 
                self.queue.append(self.stack.pop())
                
        return self.queue.pop()

    def peek(self) -> int:
        # similar to pop. Check if queue is empty
        if not self.queue: 
            while self.stack: 
                self.queue.append(self.stack.pop())
        
        return self.queue[-1]
        

    def empty(self) -> bool:
        return not self.stack and not self.queue


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

TIME AND SPACE COMPLEXITY

TIME: O(n) in the worst case but O(1) amortized runtime. In the worst case, the runtime will be O(n). This happens in cases where we need to pop elements from the first stack and append them to the second stack for every single pop or peek operation. However, on average, most pop function calls will be O(1) because the second stack will contain elements, given that we are popping all the elements from the first stack and appending them to the second stack when it is empty. I honestly am not explaining amortized runtime properly so I suggest you read about it elsewhere.

SPACE: O(n) where n is the number of elements. Out two stacks combined will atmost store n number of elements.