**An Introduction to Domain-Driven Design - Part 2**

A last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (`push`,`top` and`pop`) You must use only the standard operations of a queue, which means that only `push to back` and `peek/pop from front` are valid. Depending on language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Senior Software Engineer with 7+ YoE building massively scalable systems both from scratch and diving into a codebase

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (`push`

, `top`

, `pop`

, and `empty`

).

Implement the `MyStack`

class:

`void push(int x)`

Pushes element x to the top of the stack.`int pop()`

Removes the element on the top of the stack and returns it.`int top()`

Returns the element on the top of the stack.`boolean empty()`

Returns`true`

if the stack is empty,`false`

otherwise.

**Notes:**

- You must use
**only**standard operations of a queue, which means that only`push to back`

,`peek/pop from front`

,`size`

and`is empty`

operations are valid. - Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

```
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
```

**Constraints:**

`1 <= x <= 9`

- At most
`100`

calls will be made to`push`

,`pop`

,`top`

, and`empty`

. - All the calls to
`pop`

and`top`

are valid.

**Follow-up:** Can you implement the stack using only one queue?

Here will be two amazing variants. And you can discuss with the interviewer which variant is the best and discuss all pros and cons.

In the first variant we are going to use Two Queues, push - *O*(1), pop O(n)*.*

Ok, Lets start. Our class looks like:

```
class MyStack {
private Queue<Integer> current;
private Queue<Integer> tmp;
public MyStack() {
current = new ArrayDeque<>();
tmp = new ArrayDeque<>();
}
}
```

Then let’s implement **push** operation. For it, we just need to push the element into the queue

```
public void push(int x) {
current.add(x);
}
```

**Pop** operation can be tricky. Firstly we have to check the current queue. If it is empty, we can throw err or return **-1** for example. Then we have to **move all elements except one** to the tmp queue. After it we **remember the last element in a current queue** and finally swap the queues.

```
public int pop() {
if (current.isEmpty()){
return -1;
}
int size = current.size();
for (int i = 0; i < size - 1; i ++){
tmp.add(current.poll());
}
int ret = current.poll();
current = tmp;
return ret;
}
```

Let’s draw it. *For example:*

*1) we have in currentQ elements [3, 2, 1] -→ move to temp*

*2) currentQ [3, 2], tmpQ = [1]*

*3) currentQ [3], tmpQ = [2, 1]*

*4) remember 3*

*5) currentQ = tmpQ = [2, 1]*

*6) return 3*

Kinda the same algorithm we use for **top** operation:

```
public int top() {
if (current.isEmpty()){
return -1;
}
int size = current.size();
for (int i = 0; i < size - 1; i ++){
tmp.add(current.poll());
}
int ret = current.peek();
tmp.add(current.poll());
current = tmp;
return ret;
}
```

And a simple method to check if our stack is **empty:**

```
public boolean empty() {
return current.isEmpty();
}
```

Looks like wisdom to me.

**In the second solution, we use only one Queue, but the push operation will take - O(n) time and pop O(1).**

```
class MyStack2 {
private Queue<Integer> current;
public MyStack2() {
current = new ArrayDeque<>();
}
}
```

In this approach, the main trick will be in the **push** method:

```
public void push(int x) {
current.add(x);
int size = current.size();
for (int i = 0; i < size-1; i ++){
current.add(current.poll());
}
}
```

We push a new element to the end of the queue. Then we move all elements step by step to the end.

*For example:*

*1) push(1) → current add 1 = [1]*

*2) push(2) → current add [2, 1] → move [1, 2]*

*3) push(3) → current add [3, 1, 2] → move [2, 3, 1] → move [1, 2, 3]*

And… and that is it =)

All other operations use the current queue

```
public int pop() {
return current.poll();
}
public int top() {
return current.peek();
}
public boolean empty() {
return current.isEmpty();
}
```

Oh, do you like it? leave add your comments below.

link: https://leetcode.com/problems/implement-stack-using-queues/

L O A D I N G

. . . comments & more!

. . . comments & more!