*2.1K*

A queue is a linear data structure which maintains the order in which the elements appear. You need to implement a queue, using two stacks such that it behaves in the same way.

If you are unfamiliar with the queue data structure and the stack data structure, it would be a good idea to learn them before approaching this problem.

#### Problem Statement:

The basic crux of the problem is that you are to implement a queue and its operations using stacks. It may seem unnecessary in the beginning, as a data structure for queue already exists. Sometimes you have a limited architecture and still need a solution that supports your use case.

If you look at the operations will still behave like a queue:

```
enqueue ( 4 )
enqueue ( 8 )
enqueue ( 15 )
enqueue ( 16 )
```

```
dequeue ( ) => 4
dequeue ( ) => 8
peek ( ) => 15
dequeue ( ) => 15
```

Code language: PHP (php)

For all the operations the desired output is same as if you are operating on a queue.

#### Solution:

This problem does not have a brute force method. Just a common understanding of how both the data structures work should be helpful in approaching this. Just need to make sure that you are following the FIFO (First in First out). Let us see how that would look.

Let us start by creating 2 stacks as desired. One stack is `In`

and the other is named as `Out`

. Apart from those, also create a queue that is mimicking the actual operations.

```
Queue:
--------------------------------------------------------------------------
| | | | |
--------------------------------------------------------------------------
Stacks:
| | | |
------------- -------------
| | | |
------------- -------------
| | | |
------------- -------------
| | | |
------------- -------------
In Out
```

Code language: plaintext (plaintext)

#### Enqueue:

Now, let us try to perform 3 operations on the queue:

```
- enqueue ( 4 )
- enqueue ( 8 )
- enqueue ( 15 )
```

Code language: Java (java)

For every `enqueue( )`

operation, you `push( )`

the element in the `In`

stack. As per this our data structures would look like:

```
Queue:
--------------------------------------------------------------------------
| | | 15 | 8 | 4
--------------------------------------------------------------------------
Stacks:
| | | |
------------- -------------
| 15 | | |
------------- -------------
| 8 | | |
------------- -------------
| 4 | | |
------------- -------------
In Out
```

Code language: plaintext (plaintext)

This takes care of one part of the problem. How do you remove elements now? If you perform a `dequeue ()`

operation on the queue, you would get the value `4`

. However, if you observe carefully you cannot extract the value `4`

from the `In`

stack. As soon as you do a `pop()`

, you would get the element `15`

. This is not what we desired, it breaks the rules of a queue.

That is where the `Out`

stack comes in handy. As soon as you receive a `dequeue ()`

request, check the `Out`

stack. If it is not empty, do a `pop()`

operation and return the element. If it is empty. Transfer all the elements from `In`

stack to the `Out`

stack. Let us see how that works.

#### Dequeue:

It is a 2-step process. First we `pop()`

all the elements from `In`

stack and `push()`

it in the `Out`

stack.

```
Queue:
--------------------------------------------------------------------------
| | | 15 | 8 | 4
--------------------------------------------------------------------------
Stacks:
| | | |
------------- -------------
| | | 4 |
------------- -------------
| | | 8 |
------------- -------------
| | | 15 |
------------- -------------
In Out
```

Now, if you look closely stack `Out`

looks very similar to the queue. If you `pop`

an element from it, you will get the same element that you will get from the `queue`

.

If we now perform a `dequeue`

operation, we just need to pop an element from the other stack. The data structures now look like:

```
Queue:
--------------------------------------------------------------------------
| | | 15 | 8 |
--------------------------------------------------------------------------
Stacks:
| | | |
------------- -------------
| | | |
------------- -------------
| | | 8 |
------------- -------------
| | | 15 |
------------- -------------
In Out
```

#### Algorithm:

We can now write the algorithm for all the 3 operations:

- Create two stacks
`In`

and`Out`

**enqueue( )**: Push elements in stack`In`

**dequeue( )**: If stack`Out`

is not empty, pop an element from the stack. If the stack is empty, pop all elements of stack`In`

in the`Out`

stack and then again pop from`Out`

.**peek ( )**: Same as`dequeue`

, but instead of`pop`

just perform the`pee`

k operation.

#### Code:

```
private Stack input = new Stack();
private Stack output = new Stack();
public void enqueue(int x) {
input.push(x);
}
public int dequeue() {
peek();
return output.pop();
}
public int peek() {
if (output.empty())
while (!input.empty())
output.push(input.pop());
return output.peek();
}
public boolean isEmpty() {
return input.empty() && output.empty();
}
```

Code language: Java (java)

The problem statement can be found at HackerRank : Queue using two Stacks.

You can also find the complete solution and the test cases on GitHub as well.