# Queue On Pseudo Stack

### Queue on Pseudo Stack

A queue is a data structure that follows the FIFO (First-In-First-Out) principle. It has two main operations: enqueue, which adds an element to the back of the queue, and dequeue, which removes and returns the element at the front of the queue.

The "Queue on Pseudo Stack" concept involves implementing a queue using two stacks. A stack is a data structure that follows the LIFO (Last-In-First-Out) principle, with push and pop operations.

The idea is to use one stack (let's call it the "push_stack") for enqueueing elements, and another stack (let's call it the "pop_stack") for dequeueing elements. When we need to enqueue an element, we simply push it onto the push_stack. When we need to dequeue an element, we first check if the pop_stack is empty. If it is, we transfer all the elements from the push_stack to the pop_stack in reversed order. This way, the element at the top of the pop_stack becomes the front of the queue, and we can pop it. If the pop_stack is not empty, we can directly pop the top element.

This approach ensures that the elements are dequeued in the correct order, maintaining the FIFO property of a queue.

### Implementation

Here's an example implementation of a queue using two stacks in Python:

```
class Queue:
def __init__(self):
self.push_stack = []
self.pop_stack = []
def enqueue(self, value):
self.push_stack.append(value)
def dequeue(self):
if not self.pop_stack:
# Transfer elements from push_stack to pop_stack
while self.push_stack:
self.pop_stack.append(self.push_stack.pop())
if not self.pop_stack:
raise IndexError("Queue is empty")
return self.pop_stack.pop()
def is_empty(self):
return not self.push_stack and not self.pop_stack
def size(self):
return len(self.push_stack) + len(self.pop_stack)
```

In this implementation, we initialize two empty lists, `push_stack`

and `pop_stack`

, in the constructor. The `enqueue`

method simply appends the value to the `push_stack`

.

The `dequeue`

method first checks if the `pop_stack`

is empty. If it is, it transfers all the elements from the `push_stack`

to the `pop_stack`

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

. If both stacks are empty, an `IndexError`

is raised.

The `is_empty`

method checks if both stacks are empty and returns a boolean indicating the result.

The `size`

method returns the combined size of both stacks, which corresponds to the number of elements in the queue.

### Time and Space Complexity

The time complexity of enqueue and dequeue operations in this implementation is O(1) on average. Enqueueing an element simply involves appending it to the `push_stack`

, which is an O(1) operation. Dequeueing an element requires transferring elements from the `push_stack`

to the `pop_stack`

, which is also an O(1) operation on average.

The space complexity of the implementation is O(N), where N is the number of elements in the queue. This is because we use two stacks to store the elements, and the maximum combined size of the stacks is equal to the number of elements in the queue.

Let's solve the "Implement Queue using Stacks" question from LeetCode using the "Queue on Pseudo Stack" concept.

Problem: Implement a queue using two stacks.

Here's the solution code in Python with proper comments explaining each step:

```
class MyQueue:
def __init__(self):
self.push_stack = []
self.pop_stack = []
def push(self, x: int) -> None:
# Push the element onto the push_stack
self.push_stack.append(x)
def pop(self) -> int:
# If pop_stack is empty, transfer elements from push_stack
if not self.pop_stack:
while self.push_stack:
self.pop_stack.append(self.push_stack.pop())
# Pop the top element from pop_stack
return self.pop_stack.pop()
def peek(self) -> int:
# If pop_stack is empty, transfer elements from push_stack
if not self.pop_stack:
while self.push_stack:
self.pop_stack.append(self.push_stack.pop())
# Return the top element from pop_stack without removing it
return self.pop_stack[-1]
def empty(self) -> bool:
# Check if both stacks are empty
return not self.push_stack and not self.pop_stack
```

In this implementation, we create two empty stacks: `push_stack`

and `pop_stack`

.

The `push`

method simply appends the element to the `push_stack`

.

The `pop`

method first checks if the `pop_stack`

is empty. If it is, it transfers all the elements from the `push_stack`

to the `pop_stack`

by popping from `push_stack`

and pushing onto `pop_stack`

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

. This ensures that elements are dequeued in the correct order.

The `peek`

method is similar to `pop`

, but instead of removing the top element from `pop_stack`

, it returns it without removing it.

The `empty`

method checks if both stacks are empty and returns a boolean indicating the result.

### Time and Space Complexity

The time complexity of the `push`

operation is O(1) since it involves appending an element to the `push_stack`

.

The time complexity of the `pop`

and `peek`

operations is O(1) on average. If the `pop_stack`

is empty, we need to transfer elements from the `push_stack`

to the `pop_stack`

. This operation takes O(N), where N is the number of elements in the queue. However, since we only need to transfer elements once for every N operations, the amortized time complexity is O(1).

The space complexity of the implementation is O(N), where N is the number of elements in the queue. This is because we use two stacks to store the elements, and the maximum combined size of the stacks is equal to the number of elements in the queue.