225. 用队列实现栈

简单设计一个队列（入队后把前面的元素轮转到队尾）力扣原题 ↗

题目描述

只用两个队列，实现一个后进先出的栈 MyStack，支持栈的四种基本操作。

- void push(int x)：把 x 放到栈顶。 - int pop()：删掉栈顶元素并返回它。 - int top()：返回栈顶元素，不删除。 - boolean empty()：栈为空时返回 true，否则返回 false。

对队列只能用标准操作：从队尾加入、查看或取出队首、获取大小、判断是否为空。如果语言没有现成的队列，可以用列表或双端队列模拟，但只能调用上述标准操作。

示例 1

输入：操作 = ["MyStack","push","push","top","pop","empty"]
参数 = [[],[1],[2],[],[],[]]
输出：[null,null,null,2,2,false]

解释：先压入 1、2，栈顶是 2；pop 弹出 2 后栈里还有 1，所以 empty 返回 false。

数据范围

1 <= x <= 9
push、pop、top、empty 合计最多调用 100 次。
调用 pop 和 top 时栈一定非空。

进阶：能否只用一个队列实现？

解题思路：一个队列（入队后把前面的元素轮转到队尾）

只用一个队列，并始终让队首就是栈顶。push(x) 时先把 x 放到队尾，再把它前面的 n-1 个元素依次从队首取出、重新放到队尾，这样 x 就转到了队首。pop 和 top 直接操作队首。

为什么正确

每次 push 完成后，队列从队首到队尾恰好是栈从栈顶到栈底的顺序。

复杂度分析

push O(n)，pop/top/empty O(1)；空间 O(n)。

易错点

旋转次数是 n-1 而不是 n：转 n 次会把新元素也转回队尾，等于没转。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

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

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            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 not self.q

class MyStack {
    private final Queue<Integer> q = new ArrayDeque<>();

    public MyStack() {
    }

    public void push(int x) {
        q.offer(x);
        for (int k = q.size() - 1; k > 0; k--)
            q.offer(q.poll());
    }

    public int pop() {
        return q.poll();
    }

    public int top() {
        return q.peek();
    }

    public boolean empty() {
        return q.isEmpty();
    }
}

class MyStack {
    queue<int> q;
public:
    MyStack() {}

    void push(int x) {
        q.push(x);
        for (int k = (int)q.size() - 1; k > 0; k--) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        int v = q.front();
        q.pop();
        return v;
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

type MyStack struct {
	q []int
}

func Constructor() MyStack {
	return MyStack{}
}

func (this *MyStack) Push(x int) {
	this.q = append(this.q, x)
	for k := len(this.q) - 1; k > 0; k-- {
		this.q = append(this.q[1:], this.q[0])
	}
}

func (this *MyStack) Pop() int {
	v := this.q[0]
	this.q = this.q[1:]
	return v
}

func (this *MyStack) Top() int {
	return this.q[0]
}

func (this *MyStack) Empty() bool {
	return len(this.q) == 0
}

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

MyStack.prototype.push = function(x) {
    this.q.push(x);
    for (let k = this.q.length - 1; k > 0; k--)
        this.q.push(this.q.shift());
};

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

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

MyStack.prototype.empty = function() {
    return this.q.length === 0;
};

class MyStack {
    private q: number[] = [];

    constructor() {
    }

    push(x: number): void {
        this.q.push(x);
        for (let k = this.q.length - 1; k > 0; k--)
            this.q.push(this.q.shift()!);
    }

    pop(): number {
        return this.q.shift()!;
    }

    top(): number {
        return this.q[0];
    }

    empty(): boolean {
        return this.q.length === 0;
    }
}

载入编辑器，自己跑一遍 →

其他解法

两种写法都在 push 时花 O(n) 把新元素调到队首，让队首始终是栈顶。双队列借助辅助队列重新排队，单队列把前面的元素依次移到队尾，省掉了一个队列。

解法 2：两个队列时间 push O(n)，其余 O(1)，空间 O(n)

q1 保存栈内元素，队首就是栈顶；q2 是辅助队列。push 时先把新元素放进空的 q2，再把 q1 的元素依次出队并放入 q2，这样新元素就排在了最前面；最后交换 q1 和 q2。pop、top、empty 都直接操作 q1 的队首。

思路更直观：用一个空队列“从新排队”。但多用了一个队列，代码也多一点；单队列写法通过轮转做到了同样的效果。

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

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

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

    def empty(self) -> bool:
        return not self.q1

class MyStack {
    private Queue<Integer> q1 = new ArrayDeque<>();
    private Queue<Integer> q2 = new ArrayDeque<>();

    public MyStack() {
    }

    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) q2.offer(q1.poll());
        Queue<Integer> t = q1;
        q1 = q2;
        q2 = t;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

class MyStack {
    queue<int> q1, q2;
public:
    MyStack() {}

    void push(int x) {
        q2.push(x);
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        swap(q1, q2);
    }

    int pop() {
        int v = q1.front();
        q1.pop();
        return v;
    }

    int top() {
        return q1.front();
    }

    bool empty() {
        return q1.empty();
    }
};

type MyStack struct {
	q1, q2 []int
}

func Constructor() MyStack {
	return MyStack{}
}

func (this *MyStack) Push(x int) {
	this.q2 = append(this.q2, x)
	for len(this.q1) > 0 {
		this.q2 = append(this.q2, this.q1[0])
		this.q1 = this.q1[1:]
	}
	this.q1, this.q2 = this.q2, this.q1[:0]
}

func (this *MyStack) Pop() int {
	v := this.q1[0]
	this.q1 = this.q1[1:]
	return v
}

func (this *MyStack) Top() int {
	return this.q1[0]
}

func (this *MyStack) Empty() bool {
	return len(this.q1) == 0
}

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

MyStack.prototype.push = function(x) {
    this.q2.push(x);
    while (this.q1.length) this.q2.push(this.q1.shift());
    [this.q1, this.q2] = [this.q2, this.q1];
};

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

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

MyStack.prototype.empty = function() {
    return this.q1.length === 0;
};

class MyStack {
    private q1: number[] = [];
    private q2: number[] = [];

    constructor() {
    }

    push(x: number): void {
        this.q2.push(x);
        while (this.q1.length) this.q2.push(this.q1.shift()!);
        [this.q1, this.q2] = [this.q2, this.q1];
    }

    pop(): number {
        return this.q1.shift()!;
    }

    top(): number {
        return this.q1[0];
    }

    empty(): boolean {
        return this.q1.length === 0;
    }
}

设计专题的其他题目

查看设计全部题目 →