# 队列实现栈|栈实现队列

<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
<a href="https://labuladong.online/algo/" target="_blank"><img class="my_header_icon" src="https://img.shields.io/static/v1?label=精品课程&message=查看&color=pink&style=flat"></a>
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

![](https://labuladong.github.io/pictures/souyisou1.png)

**通知：算法可视化编辑器上线，[点击体验](https://labuladong.online/algo/intro/visualize/)！另外，建议你在我的 [网站](https://labuladong.online/algo/) 学习文章，体验更好。**



读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [225. Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) | [225. 用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues/) | 🟢
| [232. Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) | [232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/) | 🟢
| - | [剑指 Offer 09. 用两个栈实现队列](https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/) | 🟢
| - | [剑指 Offer 09. 用两个栈实现队列](https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/) | 🟢

**-----------**

队列是一种先进先出的数据结构，栈是一种先进后出的数据结构，形象一点就是这样：

![](https://labuladong.github.io/pictures/栈队列/1.jpg)

这两种数据结构底层其实都是数组或者链表实现的，只是 API 限定了它们的特性，那么今天就来看看如何使用「栈」的特性来实现一个「队列」，如何用「队列」实现一个「栈」。

### 一、用栈实现队列

力扣第 232 题「用栈实现队列」让我们实现的 API 如下：

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

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

![](https://labuladong.github.io/pictures/栈队列/2.jpg)

<!-- muliti_language -->
```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/pictures/栈队列/3.jpg)

<!-- muliti_language -->
```java
class MyQueue {
    // 为了节约篇幅，省略上文给出的代码部分...

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

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

![](https://labuladong.github.io/pictures/栈队列/4.jpg)

<!-- muliti_language -->
```java
class MyQueue {
    // 为了节约篇幅，省略上文给出的代码部分...

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

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

<!-- muliti_language -->
```java
class MyQueue {
    // 为了节约篇幅，省略上文给出的代码部分...

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

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

<!-- muliti_language -->
```java
class MyQueue {
    // 为了节约篇幅，省略上文给出的代码部分...

    /** 判断队列是否为空 */
    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)。

### 二、用队列实现栈

如果说双栈实现队列比较巧妙，那么用队列实现栈就比较简单粗暴了，只需要一个队列作为底层数据结构。

力扣第 225 题「用队列实现栈」让我们实现如下 API：

<!-- muliti_language -->
```java
class MyStack {
    
    /** 添加元素到栈顶 */
    public void push(int x);
    
    /** 删除栈顶的元素并返回 */
    public int pop();
    
    /** 返回栈顶元素 */
    public int top();
    
    /** 判断栈是否为空 */
    public boolean empty();
}
```

先说 `push` API，直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要 `top` 查看栈顶元素的话可以直接返回：

<!-- muliti_language -->
```java
class MyStack {
    Queue<Integer> q = new LinkedList<>();
    int top_elem = 0;

    /** 添加元素到栈顶 */
    public void push(int x) {
        // x 是队列的队尾，是栈的栈顶
        q.offer(x);
        top_elem = x;
    }
    
    /** 返回栈顶元素 */
    public int top() {
        return top_elem;
    }
}
```

我们的底层数据结构是先进先出的队列，每次 `pop` 只能从队头取元素；但是栈是后进先出，也就是说 `pop` API 要从队尾取元素：

![](https://labuladong.github.io/pictures/栈队列/5.jpg)

解决方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了：

![](https://labuladong.github.io/pictures/栈队列/6.jpg)

<!-- muliti_language -->
```java
class MyStack {
    // 为了节约篇幅，省略上文给出的代码部分...

    /** 删除栈顶的元素并返回 */
    public int pop() {
        int size = q.size();
        while (size > 1) {
            q.offer(q.poll());
            size--;
        }
        // 之前的队尾元素已经到了队头
        return q.poll();
    }
}
```

这样实现还有一点小问题就是，原来的队尾元素被提到队头并删除了，但是 `top_elem` 变量没有更新，我们还需要一点小修改：

<!-- muliti_language -->
```java
class MyStack {
    // 为了节约篇幅，省略上文给出的代码部分...
    
    /** 删除栈顶的元素并返回 */
    public int pop() {
        int size = q.size();
        // 留下队尾 2 个元素
        while (size > 2) {
            q.offer(q.poll());
            size--;
        }
        // 记录新的队尾元素
        top_elem = q.peek();
        q.offer(q.poll());
        // 删除之前的队尾元素
        return q.poll();
    }
}
```

最后，API `empty` 就很容易实现了，只要看底层的队列是否为空即可：

<!-- muliti_language -->
```java
class MyStack {
    // 为了节约篇幅，省略上文给出的代码部分...

    /** 判断栈是否为空 */
    public boolean empty() {
        return q.isEmpty();
    }
}
```

很明显，用队列实现栈的话，`pop` 操作时间复杂度是 O(N)，其他操作都是 O(1)。

个人认为，用队列实现栈是没啥亮点的问题，但是**用双栈实现队列是值得学习的**。

![](https://labuladong.github.io/pictures/栈队列/4.jpg)

从栈 `s1` 搬运元素到 `s2` 之后，元素在 `s2` 中就变成了队列的先进先出顺序，这个特性有点类似「负负得正」，确实不太容易想到。

希望本文对你有帮助。




<hr>
<details class="hint-container details">
<summary><strong>引用本文的题目</strong></summary>

<strong>安装 [我的 Chrome 刷题插件](https://labuladong.online/algo/intro/chrome/) 点开下列题目可直接查看解题思路：</strong>

| LeetCode | 力扣 |
| :----: | :----: |
| - | [剑指 Offer 09. 用两个栈实现队列](https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/?show=1) |

</details>
<hr>



**＿＿＿＿＿＿＿＿＿＿＿＿＿**

**《labuladong 的算法笔记》已经出版，关注公众号查看详情；后台回复「**全家桶**」可下载配套 PDF 和刷题全家桶**：

![](https://labuladong.github.io/pictures/souyisou2.png)

======其他语言代码======

[232.用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks)

[225.用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues)



### javascript

[232.用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks)

```js
/**
 * Initialize your data structure here.
 */
var MyQueue = function () {
    this.inStack = [];
    this.outStack = [];
};

/**
 * Push element x to the back of queue.
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
    this.inStack.push(x);
};


/**
 * 检查outStack
 */
MyQueue.prototype.checkOutStack = function () {
    // // 把 inStack 元素压入 outStack
    if (!this.outStack.length) {
        while (this.inStack.length) {
            this.outStack.push(this.inStack.pop());
        }
    }
};


/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function () {
    this.checkOutStack();
    return this.outStack.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    this.checkOutStack();
    return this.outStack[this.outStack.length - 1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    return (!this.inStack.length && !this.outStack.length);
};
```

[225.用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues)

```js
// --------------------------------
/**
 * Initialize your data structure here.
 */
var MyStack = function () {
    this.q = []
    this.top_elem = 0;
};

/**
 * Push element x onto stack.
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
    // x 是队列的队尾，是栈的栈顶
    this.q.push(x);
    this.top_elem = x;
};


/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function () {
    let size = this.q.length;

    // 留下队尾 2 个元素
    while (size > 2) {
        // peek()都是用来返回队列的头元素, 相当于[0]
        //  poll()都是用来从队列头部删除一个元素 相当于js的shift()
        this.q.push(this.q.shift());
        size--;
    }

    // 记录新的队尾元素
    this.top_elem = this.q[0];
    this.q.push(this.q.shift());

    // 删除之前的队尾元素
    return this.q.shift();
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function () {
    return this.top_elem;
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
    return !this.q.length;
};

/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */
```