# Queue By Two Stacks

**Queue By Two Stacks:**

The Queue data structure follows the First-In-First-Out (FIFO) principle, where the element that has been in the queue for the longest time is the first one to be removed. In this implementation, we use two stacks to simulate the behavior of a queue.

**Approach:**

- We use one stack, called the
`input_stack`

, to handle the enqueue operation. - We use another stack, called the
`output_stack`

, to handle the dequeue operation. - When we enqueue an element, we simply push it onto the
`input_stack`

. - When we dequeue an element, we check if the
`output_stack`

is empty. If it is empty, we transfer all elements from the`input_stack`

to the`output_stack`

in reversed order. Then we pop the top element from the`output_stack`

and return it.

This approach ensures that the elements in the `output_stack`

are in the correct order to simulate the behavior of a queue.

**Example:**

Here's an example of implementing a Queue using two Stacks in Python:

```
class Queue:
def __init__(self):
self.input_stack = []
self.output_stack = []
def enqueue(self, value):
self.input_stack.append(value)
def dequeue(self):
if not self.output_stack:
while self.input_stack:
self.output_stack.append(self.input_stack.pop())
return self.output_stack.pop()
def is_empty(self):
return len(self.input_stack) == 0 and len(self.output_stack) == 0
def size(self):
return len(self.input_stack) + len(self.output_stack)
```

In this code, we define the `Queue`

class. It has two stacks as instance variables: `input_stack`

and `output_stack`

. The `enqueue`

method appends elements to the `input_stack`

, simulating the enqueue operation. The `dequeue`

method checks if the `output_stack`

is empty. If it is, it transfers elements from the `input_stack`

to the `output_stack`

in reversed order. Then, it pops and returns the top element from the `output_stack`

, simulating the dequeue operation.

The `is_empty`

method checks if both stacks are empty, indicating an empty queue. The `size`

method returns the total number of elements in the queue.

Now, let's solve a question using this concept.

**Question: Implement Queue using Stacks**

Implement a Queue data structure using stacks. The implementation should support the following operations: `push`

, `pop`

, `peek`

, and `empty`

.

Here's the solution:

```
class Queue:
def __init__(self):
self.input_stack = []
self.output_stack = []
def enqueue(self, value):
self.input_stack.append(value)
def dequeue(self):
if not self.output_stack:
while self.input_stack:
self.output_stack.append(self.input_stack.pop())
return self.output_stack.pop()
def is_empty(self):
return len(self.input_stack) == 0 and len(self.output_stack) == 0
def size(self):
return len(self.input_stack) + len(self.output_stack)
```

In this solution, we implement the `MyQueue`

class, which has the same methods as the standard Queue. The `push`

operation appends elements to the `input_stack`

. The `pop`

operation calls the `peek`

method to ensure that the `output_stack`

is updated, then pops and returns the top element from the `output_stack`

. The `peek`

operation checks if the `output_stack`

is empty, transfers elements from the `input_stack`

if necessary, and returns the top element. The `empty`

operation checks if both stacks are empty.

**Time and Space Complexity Analysis:**

The time complexity for the enqueue operation is O(1) since we directly append elements to the `input_stack`

.

The time complexity for the dequeue operation is O(n), where n is the number of elements in the queue. In the worst case, when the `output_stack`

is empty, we need to transfer all elements from the `input_stack`

to the `output_stack`

. However, subsequent dequeue operations will be O(1) until the `output_stack`

becomes empty again.

The time complexity for the peek operation is O(1) since we access the top element directly.

The time complexity for the empty operation is O(1) since we only check if both stacks are empty.

The space complexity is O(n), where n is the number of elements in the queue. This is because we store all elements in either the `input_stack`

or the `output_stack`

.

Overall, this implementation provides the required queue operations with a reasonable time complexity, making it suitable for most scenarios.

Let's solve a question using the concept of implementing a Queue using two Stacks and analyze its time and space complexity.

**Question: Implement Queue using Stacks**

Implement a Queue data structure using stacks. The implementation should support the following operations: `push`

, `pop`

, `peek`

, and `empty`

.

**Solution:**

```
class MyQueue:
def __init__(self):
self.input_stack = []
self.output_stack = []
def push(self, x):
self.input_stack.append(x)
def pop(self):
self.peek()
return self.output_stack.pop()
def peek(self):
if not self.output_stack:
while self.input_stack:
self.output_stack.append(self.input_stack.pop())
return self.output_stack[-1]
def empty(self):
return not self.input_stack and not self.output_stack
```

In this solution, we implement the `MyQueue`

class, which utilizes two stacks: `input_stack`

and `output_stack`

. The `push`

operation appends elements to the `input_stack`

. The `pop`

operation calls the `peek`

method to ensure that the `output_stack`

is updated, then pops and returns the top element from the `output_stack`

. The `peek`

operation checks if the `output_stack`

is empty, transfers elements from the `input_stack`

if necessary, and returns the top element. The `empty`

operation checks if both stacks are empty.

**Time Complexity Analysis:**

The time complexity for the `push`

operation is O(1) since we directly append elements to the `input_stack`

.

The time complexity for the `pop`

operation is O(1) in the average case. However, in the worst case, when the `output_stack`

is empty, we need to transfer all elements from the `input_stack`

to the `output_stack`

, resulting in a time complexity of O(n), where n is the number of elements in the queue. Subsequent `pop`

operations will be O(1) until the `output_stack`

becomes empty again.

The time complexity for the `peek`

operation is O(1) in the average case. Similar to the `pop`

operation, the worst-case time complexity is O(n) when the `output_stack`

is empty and requires transferring elements from the `input_stack`

. Subsequent `peek`

operations will be O(1) until the `output_stack`

becomes empty again.

The time complexity for the `empty`

operation is O(1) since we only check if both stacks are empty.

**Space Complexity Analysis:**

The space complexity is O(n), where n is the number of elements in the queue. This is because we store all elements in either the `input_stack`

or the `output_stack`

.

**Overall:**

This implementation provides a way to simulate a queue using two stacks. While the worst-case time complexity for `pop`

and `peek`

operations is O(n), the average-case time complexity is O(1). The space complexity is reasonable at O(n). This approach is suitable for scenarios where the number of enqueue and dequeue operations is balanced and the number of elements in the queue is not excessively large.

Let's solve another question using the concept of implementing a Queue using two Stacks and analyze its time and space complexity.

**Question: Implement Stack using Queues**

Implement a Stack data structure using queues. The implementation should support the following operations: `push`

, `pop`

, `top`

, and `empty`

.

**Solution:**

```
class MyStack:
def __init__(self):
self.queue = []
def push(self, x):
self.queue.append(x)
size = len(self.queue)
# Move all previous elements to the end
for _ in range(size - 1):
self.queue.append(self.queue.pop(0))
def pop(self):
return self.queue.pop(0)
def top(self):
return self.queue[0]
def empty(self):
return len(self.queue) == 0
```

In this solution, we implement the `MyStack`

class, which uses a single queue to simulate a stack. The `push`

operation appends the new element to the end of the queue and then moves all previous elements to the end, effectively making the new element the top of the stack. The `pop`

operation removes and returns the front element of the queue, which corresponds to the top of the stack. The `top`

operation returns the front element without removing it. The `empty`

operation checks if the queue is empty.

**Time Complexity Analysis:**

The time complexity for the `push`

operation is O(n), where n is the number of elements in the stack. This is because, after adding the new element, we need to move all previous elements to the end of the queue. In the worst case, we iterate through all elements in the queue.

The time complexity for the `pop`

, `top`

, and `empty`

operations is O(1) since we directly access the front element of the queue or check if the queue is empty.

**Space Complexity Analysis:**

The space complexity is O(n), where n is the number of elements in the stack. This is because we store all elements in the queue.

**Overall:**

This implementation provides a way to simulate a stack using a single queue. The `push`

operation has a time complexity of O(n) due to the need to move elements, while the other operations have a time complexity of O(1). The space complexity is reasonable at O(n). This approach is suitable for scenarios where the number of push operations is balanced with the number of pop operations, and the number of elements in the stack is not excessively large.

** **