> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/40implement-queue-by-two-stacks.md).

# 232. Implement Queue using Stacks (E)

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:**

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

 

**Constraints:**

* `1 <= x <= 9`
* At most `100` calls will be made to `push`, `pop`, `peek`, and `empty`.
* All the calls to `pop` and `peek` are valid.

**Follow-up:** Can you implement the queue such that each operation is [**amortized**](https://en.wikipedia.org/wiki/Amortized_analysis) `O(1)` time complexity? In other words, performing `n` operations will take overall `O(n)` time even if one of those operations may take longer

[**Challenge**](https://www.lintcode.com/en/problem/implement-queue-by-two-stacks/#challenge)

implement it by two stacks, do not use any other data structure and push, pop and top should be O(1) by *AVERAGE*.

## 2.Code

首先，队列的 API 如下：

```java
class MyQueue {
    
    /** 添加元素到队尾 */
    public void push(int x);
    
    /** 删除队头的元素并返回 */
    public int pop();
    
    /** 返回队头元素 */
    public int peek();
    
    /** 判断队列是否为空 */
    public boolean empty();
}
```

我们使用两个栈 `s1, s2` 就能实现一个队列的功能（这样放置栈可能更容易理解）：

[![](https://labuladong.github.io/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/2.jpg)](https://labuladong.github.io/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/2.jpg)

```java
class MyQueue {
    private Stack<Integer> s1, s2;
    
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    // ...
}
```

当调用 `push` 让元素入队时，只要把元素压入 `s1` 即可，比如说 `push` 进 3 个元素分别是 1,2,3，那么底层结构就是这样：

[![](https://labuladong.github.io/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/3.jpg)](https://labuladong.github.io/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/3.jpg)

```java
/** 添加元素到队尾 */
public void push(int x) {
    s1.push(x);
}
```

那么如果这时候使用 `peek` 查看队头的元素怎么办呢？按道理队头元素应该是 1，但是在 `s1` 中 1 被压在栈底，现在就要轮到 `s2` 起到一个中转的作用了：当 `s2` 为空时，可以把 `s1` 的所有元素取出再添加进 `s2`，**这时候 `s2` 中元素就是先进先出顺序了**。

[![](https://labuladong.github.io/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/4.jpg)](https://labuladong.github.io/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/4.jpg)

```java
/** 返回队头元素 */
public int peek() {
    if (s2.isEmpty())
        // 把 s1 元素压入 s2
        while (!s1.isEmpty())
            s2.push(s1.pop());
    return s2.peek();
}
```

同理，对于 `pop` 操作，只要操作 `s2` 就可以了。

```java
/** 删除队头的元素并返回 */
public int pop() {
    // 先调用 peek 保证 s2 非空
    peek();
    return s2.pop();
}
```

最后，如何判断队列是否为空呢？如果两个栈都为空的话，就说明队列为空：

```java
/** 判断队列是否为空 */
public boolean empty() {
    return s1.isEmpty() && s2.isEmpty();
}
```

至此，就用栈结构实现了一个队列，核心思想是利用两个栈互相配合。

值得一提的是，这几个操作的时间复杂度是多少呢？有点意思的是 `peek` 操作，调用它时可能触发 `while` 循环，这样的话时间复杂度是 O(N)，但是大部分情况下 `while` 循环不会被触发，时间复杂度是 O(1)。由于 `pop` 操作调用了 `peek`，它的时间复杂度和 `peek` 相同。

像这种情况，可以说它们的**最坏时间复杂度**是 O(N)，因为包含 `while` 循环，**可能**需要从 `s1` 往 `s2` 搬移元素。

但是它们的**均摊时间复杂度**是 O(1)，这个要这么理解：对于一个元素，最多只可能被搬运一次，也就是说 `peek` 操作平均到每个元素的时间复杂度是 O(1)。

Version 2:

```
class MyQueue {
    Stack<Integer> temp=new Stack<Integer>();
	Stack<Integer> value=new Stack<Integer>();
	
	 // Push element x to the back of queue.
    public void push(int x) {
    	
    	if(value.isEmpty())
    	{
    		value.push(x);
    	}
    	else
    	{
    		while(!value.isEmpty())
    		{
    			int tempnum=value.pop();
    			temp.push(tempnum);    			
    		}
    		value.push(x);
    		while(!temp.isEmpty())
    		{
    			int tempnum=temp.pop();
    			value.push(tempnum);
    		}
    	}       
    }


    
    // Removes the element from in front of queue.
    public void pop() {
    	
    	value.pop();
        
    }

    // Get the front element.
    public int peek()
    {
    	
    	return value.peek();
        
    }

    // Return whether the queue is empty.
    public boolean empty() 
    {    	
       return value.isEmpty(); 
    }
}
```