0225.用队列实现栈

难度：🟢 简单

标签：栈、设计、队列

链接：225. 用队列实现栈

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。

• int pop() 移除并返回栈顶元素。

• int top() 返回栈顶元素。

• boolean empty() 如果栈为空，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back, peek/pop from front, size 和 is empty 这些操作。

• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 ，只要是标准的队列操作即可。

解题思路

核心思想

本题的挑战在于，队列是“先进先出”（FIFO），而栈是“后进先出”（LIFO）。我们需要通过队列的操作来模拟出 LIFO 的效果。关键在于，如何让最新加入的元素能够被最先访问到（即移动到队首）。

思路选择

单队列法 是解决此问题的一种非常巧妙且高效的思路。

• 我们只用一个队列来存储数据。

• 在每次 push 新元素时，我们将其加入队尾，然后将队列中原有的所有元素依次从队首取出，再重新加入队尾。

• 这个过程完成后，最新加入的元素就被“顶”到了队首，从而使队列的队首成为了栈的“栈顶”。这样，pop 和 top 操作就变得非常简单了。

关键步骤

1. push(x) 操作: a. 记录当前队列的长度 size。 b. 将新元素 x 正常入队。 c. 循环 size 次，将队首的元素出队，再立即入队。完成这个“倒腾”后，新元素 x 就位于队首了。

2. pop() 操作: 直接对队列执行出队操作 (shift()) 并返回即可。

3. top() 操作: 直接返回队首元素 (queue[0])。

4. empty() 操作: 判断队列长度是否为 0。

代码实现

var MyStack = function () {
    this.queue = [];
};

/** * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
    const size = this.queue.length;
    this.queue.push(x);
    // 将队列前面的元素依次移到队尾
    for (let i = 0; i < size; i++) {
        this.queue.push(this.queue.shift());
    }
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
    return this.queue.shift();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
    return this.queue[0];
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
    return this.queue.length === 0;
};

复杂度分析

• 时间复杂度：

  • push: O(n)，需要移动 n-1 个元素。

  • pop: O(1)

  • top: O(1)

  • empty: O(1)

• 空间复杂度：O(n) 其中 n 是栈中元素的数量。队列需要存储所有 n 个元素。

相关题目

• 0232.用栈实现队列

总结

本题是数据结构设计类的经典题目，与“用栈实现队列”相映成趣。它考察了如何逆转一种数据结构的基本特性（FIFO -> LIFO）。单队列的解法通过在入队时进行额外操作，巧妙地维护了“栈顶”元素始终在队首的特性，是一种非常值得学习的设计思路。