## Introduction

The “Implement Queue using Stacks” is a classical problem which can be found on LeetCode. It falls under the category of data structures and is often asked in coding interviews. The task focuses on testing one’s ability to manipulate and efficiently use fundamental data structures. In this extensive article, we will discuss the problem statement, understand the concept of queue and stack, and explore various approaches to implement a queue using stacks in Python. Additionally, we will evaluate the time and space complexities of each approach.

## Problem Statement

The problem requires you to implement a queue using instances of stack data structure. Specifically, the problem states:

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`

, `pop`

, `peek`

, and `empty`

).

### Input

`push(x)`

: Add an element x to the back of the queue.`pop()`

: Remove the element from the front of the queue and return it.`peek()`

: Return the element at the front of the queue without removing it.`empty()`

: Return`True`

if the queue is empty,`False`

otherwise.

## Understanding Queue and Stack

Before we delve into the solutions, let’s briefly discuss what queues and stacks are:

**Queue**: A queue is a linear data structure that follows a First In First Out (FIFO) order for accessing elements. Elements are added (enqueued) to the back and removed (dequeued) from the front.**Stack**: A stack is a linear data structure that follows a Last In First Out (LIFO) order for accessing elements. Elements are added (pushed) and removed (popped) from the top.

## Approach 1: Two Stacks with Amortized O(1) Push Operation

We can use two stacks, namely `inputStack`

and `outputStack`

. `inputStack`

is used to make the `push`

operation efficient, while `outputStack`

is used for the `pop`

and `peek`

operations.

- For
`push(x)`

, simply push`x`

onto`inputStack`

. - For
`pop()`

, if`outputStack`

is empty, pop all elements from`inputStack`

and push them onto`outputStack`

. Then, pop the top element from`outputStack`

. - For
`peek()`

, similar to`pop()`

, but instead of popping, return the top element of`outputStack`

. - For
`empty()`

, return`True`

if both stacks are empty,`False`

otherwise.

```
class MyQueue:
def __init__(self):
# Initialize two stacks
self.inputStack = []
self.outputStack = []
def push(self, x):
# Push element x to the inputStack
self.inputStack.append(x)
def pop(self):
# If outputStack is empty, pop all elements from inputStack and push them onto outputStack
if not self.outputStack:
while self.inputStack:
self.outputStack.append(self.inputStack.pop())
# Pop the top element from outputStack
return self.outputStack.pop()
def peek(self):
# Similar to pop, but instead of popping return the top element of outputStack
if not self.outputStack:
while self.inputStack:
self.outputStack.append(self.inputStack.pop())
return self.outputStack[-1]
def empty(self):
# Return True if both stacks are empty, False otherwise
return not self.inputStack and not self.outputStack
```

### Time Complexity

`push(x)`

has an amortized time complexity of O(1).`pop()`

and`peek()`

have an amortized time complexity of O(1) because each element is moved from`inputStack`

to`outputStack`

once.`empty()`

has a time complexity of O(1).

### Space Complexity

The space complexity is O(n), where n is the number of elements in the queue.

## Approach 2: Two Stacks with O(1) Pop Operation

This approach is the reverse of the first approach. The idea is to make the `pop`

operation efficient instead of the `push`

operation.

- For
`push(x)`

, pop all elements from`inputStack`

and push them onto`outputStack`

. Push`x`

onto`inputStack`

. Pop all elements from`outputStack`

and push them back onto`inputStack`

. - For
`pop()`

, simply pop the top element from`inputStack`

. - For
`peek()`

, return the top element of`inputStack`

. - For
`empty()`

, return`True`

if`inputStack`

is empty,`False`

otherwise.

```
class MyQueue:
def __init__(self):
# Initialize two stacks
self.inputStack = []
self.outputStack = []
def push(self, x):
# Pop all elements from inputStack and push them onto outputStack
while self.inputStack:
self.outputStack.append(self.inputStack.pop())
# Push x onto inputStack
self.inputStack.append(x)
# Pop all elements from outputStack and push them back onto inputStack
while self.outputStack:
self.inputStack.append(self.outputStack.pop())
def pop(self):
# Pop the top element from inputStack
return self.inputStack.pop()
def peek(self):
# Return the top element of inputStack
return self.inputStack[-1]
def empty(self):
# Return True if inputStack is empty, False otherwise
return not self.inputStack
```

### Time Complexity

`push(x)`

has a time complexity of O(n).`pop()`

and`peek()`

have a time complexity of O(1).`empty()`

has a time complexity of O(1).

### Space Complexity

The space complexity is O(n), where n is the number of elements in the queue.

## Conclusion

In this article, we examined the “Implement Queue using Stacks” problem, understood the fundamental characteristics of queue and stack data structures, and explored two distinct approaches to implement a queue using stacks. The first approach optimizes the `push`

operation, whereas the second approach optimizes the `pop`

operation. The choice between the approaches depends on the expected usage patterns of the queue. It’s important to understand the trade-offs between different approaches and choose the one that best fits the problem’s requirements. This problem exemplifies how one can build sophisticated data structures by combining simpler ones in innovative ways.