## 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"]
[[], , , [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: 
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is 
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` 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` 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
# 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

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()
``````