Easy

题目描述

使用队列实现栈的下列操作：

  • push(x) – 元素 x 入栈
  • pop() – 移除栈顶元素
  • top() – 获取栈顶元素
  • empty() – 返回栈是否为空

注意:

  • 你只能使用队列的基本操作– 也就是 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 都保证栈不为空

进阶: 你能否仅用一个队列来实现栈？

解题思路

解题思路

这道题要求用队列实现栈，关键在于理解两种数据结构的差异：

  • 栈是后进先出(LIFO)
  • 队列是先进先出(FIFO)

有两种主要方法：

方法一：双队列实现（推荐）

使用两个队列 q1 和 q2：

  • push操作：直接将元素加入 q1
  • pop操作：将 q1 中除最后一个元素外的所有元素转移到 q2，然后弹出 q1 的最后一个元素，最后交换两个队列
  • top操作：类似pop，但不删除元素，而是重新加入队列

方法二：单队列实现

使用一个队列，在push时进行调整：

  • push操作：先记录当前队列大小，将新元素入队，然后将之前的所有元素依次出队再入队，这样新元素就到了队首
  • 其他操作直接使用队列的front和pop操作

方法二更优雅，只需要一个队列，且push操作的复杂度虽然是O(n)，但在实际使用中往往更直观。

代码实现

class MyStack {
private:
    queue<int> q;
    
public:
    MyStack() {
        
    }
    
    void push(int x) {
        int size = q.size();
        q.push(x);
        for (int i = 0; i < size; i++) {
            q.push(q.front());
            q.pop();
        }
    }
    
    int pop() {
        int result = q.front();
        q.pop();
        return result;
    }
    
    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};

from collections import deque

class MyStack:

    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        size = len(self.q)
        self.q.append(x)
        for _ in range(size):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0

public class MyStack {
    private Queue<int> queue;

    public MyStack() {
        queue = new Queue<int>();
    }
    
    public void Push(int x) {
        int size = queue.Count;
        queue.Enqueue(x);
        for (int i = 0; i < size; i++) {
            queue.Enqueue(queue.Dequeue());
        }
    }
    
    public int Pop() {
        return queue.Dequeue();
    }
    
    public int Top() {
        return queue.Peek();
    }
    
    public bool Empty() {
        return queue.Count == 0;
    }
}

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

MyStack.prototype.push = function(x) {
    this.queue.push(x);
    for (let i = 0; i < this.queue.length - 1; i++) {
        this.queue.push(this.queue.shift());
    }
};

MyStack.prototype.pop = function() {
    return this.queue.shift();
};

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

MyStack.prototype.empty = function() {
    return this.queue.length === 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
pushO(n)O(1)
popO(1)O(1)
topO(1)O(1)
emptyO(1)O(1)
整体空间-O(n)

其中 n 是栈中元素的个数。push操作需要重新排列队列中的所有元素，所以时间复杂度为O(n)；其他操作都是O(1)。

相关题目