【LeetCode】225. 用队列实现栈（简单）——代码随想录算法训练营Day10

题目链接：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（双端队列）来模拟一个队列?, 只要是标准的队列操作即可。

示例：

输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

输出： [null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // 返回 2

myStack.pop(); // 返回 2

myStack.empty(); // 返回 False

提示：

• 1 <= x <= 9
• 最多调用100?次?push、pop、top?和?empty
• 每次调用?pop?和?top?都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

文章讲解：代码随想录

视频讲解：队列的基本操作！ | LeetCode：225. 用队列实现栈_哔哩哔哩_bilibili

题解1：使用两个队列模拟栈

思路：使用一个队列当主队列，另一个队列当备份队列。入栈操作即为主队列入队；出栈操作先将主队列最后一个元素前的元素都出队后入队到备份队列中，在将主队列最后一个元素出队，这个元素即为出栈的元素，最后交换主队列和备份队列；返回栈顶元素即为返回主队列的队尾元素。

var MyStack = function() {
    this.queue1 = [];
    this.queue2 = []; // 辅助队列，用于备份
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.queue1.push(x);
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    let size = this.queue1.length;
    size--;
    while (size--) {
        this.queue2.push(this.queue1.shift());
    }
    const num = this.queue1.shift();
    const _ = this.queue1;
    this.queue1 = this.queue2;
    this.queue2 = _;
    return num;
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    return this.queue1[this.queue1.length - 1];
};

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

/**
 * 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()
 */

分析：push、top、empty 的时间复杂度为 O(1)，pop 的时间复杂度为 O(n)。空间复杂度为 O(n)。

题解2：使用一个队列模拟栈

思路：入栈操作即为入队；出栈操作先将队列最后一个元素前面的元素先出队再入队，最后将第一个元素出队；返回栈顶元素即为返回队尾元素。

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

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.queue.push(x);
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    let size = this.queue.length;
    size--;
    while (size--) {
        this.queue.push(this.queue.shift());
    }
    return this.queue.shift();
};

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

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

/**
 * 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()
 */

分析：push、top、empty 的时间复杂度为 O(1)，pop 的时间复杂度为 O(n)。空间复杂度为 O(n)。

收获

学习了队列的基本知识，学会了使用队列来模拟栈。