**Get up to 6 months free of Notion + unlimited AI!**

429 reads

by Sergey GolitsynSeptember 15th, 2022

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.

**Example 1:**

```
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
```

**Solution:**

Oh, that is an amazing problem. I like it so much. This problem made me change my thinking.

In the first solution, I’m going to use additional memory.

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

We need the additional Queue for this solution. And let’s start with push. For push operation, we just add a new element to our current queue.

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

The main trick you will see is in the pop method. Here we **put all elements except the last one** in the **tmp queue**.

And the

last element in the queue will be the first element that was pushed.

```
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;
}
```

And what about **top** method? This method is kinda the same as **pop**

```
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 for the last **empty** method, we should just check the current queue

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

In this variant, we will not use additional memory.

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

The main work for this idea will be in the push method. We add the current element and then move elements in front of the current to the end of the queue. Does it clear?

For example, if we have a queue with elements [2,1] and push 3 →

we have queue [3,2,1], then → [1,3,2] → [2,1,3] and… and that is it.

```
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 already have the correct element and the start of the queue for all other methods.

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

Hope these solutions were clear enough for you.

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

L O A D I N G

. . . comments & more!

. . . comments & more!