# 0232 Implement Queue using Stacks

Solved at: 2022-11-28

## Question​

Implement a first in, first out (FIFO) queue using only two stacks. The implemented queue should support a regular queue's functions (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.
• 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. Using only a stack's standard operations, you may simulate a stack using a list or deque (double-ended queue).

## Solution​

class MyQueue:    front = []    back = []    def __init__(self):        self.front = []        self.back = []    def push(self, x: int) -> None:        self.back.append(x) # push to top    def pop(self) -> int:        if not self.front:            while self.back:                self.front.append(self.back.pop())        return self.front.pop()    def peek(self) -> int:        if not self.front:            while self.back:                self.front.append(self.back.pop())        return self.front[-1]    def empty(self) -> bool:        return not self.front and not self.back

## Results​

• Runtime: 46 ms, Beats 72.73%
• Memory, 14 MB Beats 76.5%

Accepted on the first try? Let's go!

## Complexity Analysis​

• Push - $O(1)$ per operation,
• Pop - Amortized $O(1)$ per operation.
• Space: $O(n)$

Depending on the policy of moving elements in the queue, either moving ahead of time or just in time, the time complexity can vary from $O(1)$ to $O(n)$.