## Leetcode Problem Statement

### Description

Implement 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.

### Examples

#### 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
```

### 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.

## Key Insights

A `queue`

is a (**FIFO**) **first in first out** data structure that can be visualized as a cashier lineup at a supermarket where customers are processed in the order they arrived. `Queues`

are very useful in iterative graph traversal implementations.

A `stack`

is a (**LIFO**) **last in first out** data structure that can be visualized as a *stack* of plates at a buffet. In **Python**, a `list`

is an `array`

of pointers stored as a contiguous memory block, which means that elements can be accessed and popped from the end in `O(1)`

time. Elements can be appended to the end as long as the index has not reached the end of the allocated block of memory. If an element is appended to a `list`

that has run out of space, an automatic operation allocates a new block of memory that is twice as long as the existing list and copies the values into the new `list`

in `O(N)`

time. Since this operation doesn’t happen all of the time, the **amortized** time complexity is actually `O(1)`

. Given this property, we can say that time complexity of an append operation is practically `O(1)`

.

Now that we have a solid grasp of `queues`

and `stacks`

, we need to figure out the little trick that will allow us to implement a `queue`

with two `stacks`

in `O(1)`

amortized time. Let’s define two stacks: `stack_1`

and `stack_2`

. We will always append `push()`

new values to `stack_1`

. If `stack_2`

is empty, we will take `stack_1[0]`

and save it for the time being. Then we will loop over `stack_2`

, `pop()`

elements `n-1`

to `1`

from `stack_1`

and `append()`

them to `stack_2`

. We will clear `stack_1`

and returned the `stack_1[0]`

value we save earlier. By implementing this little trick, we will be able to achieve `O(1)`

**amortized** time complexity.

## Python Solution

```
class MyQueue:
def __init__(self):
self.stack_1 = []
self.stack_2 = []
def push(self, x: int) -> None:
self.stack_1.append(x)
def pop(self) -> int:
# If stack_2 has values, pop() from the end.
# If stack_2 is empty, save the first value in
# stack_1 and then populate stack_2 by popping
# values n to 1 from the end of stack_1. Set
# stack_1 = [] and return the "top of the stack"
if self.stack_2:
return self.stack_2.pop()
else:
res = self.stack_1[0]
# Note: The "[::-1]" syntax reverses a list
self.stack_2 = self.stack_1[1:][::-1]
self.stack_1 = []
return res
def peek(self) -> int:
# If stack_2 has values, return it's tail value.
# If stack_2 is empty, return the head of stack_1.
if self.stack_2:
return self.stack_2[-1]
else:
return self.stack_1[0]
def empty(self) -> bool:
# If stack_1 or stack_2 have values, we need
# to return False, otherwise True
return not (self.stack_1 or self.stack_2)
# 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()
```