author: Sergei Golitsyn

link: <https://leetcode.com/problems/implement-queue-using-stacks/>

\
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`, `peek`, `pop`, and `empty`).

Implement the `MyQueue` class:

* `void push(int x)` Pushes element x to the back of the queue.
* `int pop()` Removes the element from the front of the queue and returns it.
* `int peek()` Returns the element at the front of the queue.
* `boolean empty()` Returns `true` if the queue is empty, `false` otherwise.

**Notes:**

* You must use **only** standard operations of a stack, which means only `push to top`, `peek/pop from top`, `size`, and `is empty` operations are valid.
* Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

 

**Example 1:**

```javascript
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
```

\
## Solution

In this problem, I will show you only one solution. The main trick will be in **pop** and **peak** operations. But hold on. Let’s do it step by step. First of all, we have to prepare a class and needed data structures:

\
```javascript
static class MyQueue {

    Stack<Integer> current;
    Stack<Integer> tmp;

    public MyQueue() {
        current = new Stack<>();
        tmp = new Stack<>();
    }
static class MyQueue {

        Stack<Integer> current;
        Stack<Integer> tmp;

        public MyQueue() {
            current = new Stack<>();
            tmp = new Stack<>();
        }
}
```

\
And now, let’s add a **push** method:

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

\
Simple and clear, just add an element into the stack.

And what about **pop?** For pop operation, we 

> have to move all elements from the current stack to the tmp stack

\
And before it, we should check out **tmp** stack. If **tmp** stack contains an elements we can simply return an element from this stack.

\
```javascript
public int pop() {
    if (!tmp.isEmpty()) {
        return tmp.pop();
    }
    while (!current.isEmpty()) {
        tmp.push(current.pop());
    }
    return tmp.pop();
}
```

\
Let’s try to draw a picture. 


1. push 1. → 1
2. push 2. → 2, 1
3. push 3. → 3, 2, 1
4. pop. → move to tmp -→ cur: 2, 1, tmp: 3

                                             cur: 1,     tmp: 2, 3

                                             cur:         tmp: 1, 2, 3
5.  do you see it? after moving elements, all elements in the **tmp** stack are in the correct order.

\
Ahh, I was a bit shocked, but it is true. If you move elements from one stack into another, you will have elements in insert order, like in a queue.

\
Now, let’s implement **peek** function:

\
```javascript
public int peek() {
    if (!tmp.isEmpty()) {
        return tmp.peek();
    }
    while (!current.isEmpty()) {
        tmp.push(current.pop());
    }
    return tmp.peek();
}
```

\
Same logic as in the **pop** method.

\
And finally isEmpty method. Don’t forget that we have to check two queues. 

\
```javascript
public boolean empty() {
    if (!tmp.isEmpty()) {
        return tmp.isEmpty();
    }
    return current.isEmpty();
}
```

\
#### Complexity Analysis

* Time complexity: Amortized O(1)*O*(1), Worst-case O(n)*O*(*n*). In the worst case scenario when stack `s2` is empty, the algorithm pops n*n* elements from stack s1 and pushes n*n* elements to `s2`, where n*n* is the queue size. This gives 2n2*n* operations, which is O(n)*O*(*n*). But when stack `s2` is not empty the algorithm has O(1)*O*(1) time complexity. So what does it mean by Amortized O(1)*O*(1)? Please see the next section on Amortized Analysis for more information.
* Space complexity : O(1)*O*(1).

\


The writer is smart, but don't just like, take their word for it. #DoYourOwnResearch

Stacks

2021 - HackerNoon Contributor of the Year - INNOVATION

2022 - HackerNoon Contributor of the Year - Design

2022 - HackerNoon Contributor of the Year - Software Architecture

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

2021 - Rick Sanchez of the Year

Nominated for 2022 - HackerNoon Contributor of the Year - Design

Nominated for 2022 - HackerNoon Contributor of the Year - Software Architecture

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

Implement Queue using Stacks

Too Long; Didn't Read

Coin Mentioned

@deft

Credibility

RELATED STORIES