🥉easy - 🥉225. 用队列实现栈 - 《算法与LeetCode题解》

题解

请你使用队列实现一个后入先出（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 都保证栈不为空

进阶：
你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

题解

这道题要两个队列实现，其实用一个就完全足够了，还容易理解。如果用一个队列实现,push直接用队列push即可，pop要将队列中最后一个元素输出，那么可以将该元素之前的元素全部弹出，再加入队列末尾，pop出来的就是栈顶的元素。top是输出栈顶元素，其实就是队列最后一个元素，可以用一个变量来记录，减少每次top的时间复杂度。

Python

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = collections.deque()


    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        n = len(self.queue)
        self.queue.append(x)
        for _ in range(n):
            self.queue.append(self.queue.popleft())


    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.queue.popleft()


    def top(self) -> int:
        """
        Get the top element.
        """
        return self.queue[0]


    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.queue

JavaScript

/**
 * Initialize your data structure here.
 */
var MyStack = function() {
    this.queue=[]
    this.mytop = 0
};

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

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
    let index=0
    while(this.queue[index]!==this.mytop){
        this.queue.push(this.queue.shift())
    }
    this.mytop = this.queue[this.queue.length - 1]
    return this.queue.shift()

};

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

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    if (this.queue.length === 0){
        return true
    }
    return false

};

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

复杂度分析

时间复杂度：入栈操作 O(n)，其余操作都是 O(1)。

入栈操作需要将队列中的 n 个元素出队，并入队 n+1 个元素到队列，共有 2n+1 次操作，每次出队和入队操作的时间复杂度都是O(1)，因此入栈操作的时间复杂度是 O(n)。
出栈操作对应将队列的前端元素出队，时间复杂度是 O(1)。
获得栈顶元素操作对应获得队列的前端元素，时间复杂度是 O(1)。
判断栈是否为空操作只需要判断队列是否为空，时间复杂度是 O(1)。

空间复杂度：O(n)，其中 n 是栈内的元素。需要使用一个队列存储栈内的元素。