232. 用栈实现队列

题目描述

只用两个栈，实现一个先进先出的队列类 MyQueue。栈上只允许这几种操作：压入栈顶、查看栈顶、弹出栈顶、获取大小、判断是否为空。语言没有现成的栈时，可以用列表或双端队列模拟，但只能使用上述操作。

MyQueue()：创建一个空队列。

void push(int x)：把 x 加到队尾。int pop()：移除队头元素并返回它。int peek()：返回队头元素，但不移除。boolean empty()：队列为空时返回 true，否则返回 false。

输入由两个数组组成：第一个是依次调用的方法名，第二个是每次调用的参数。输出数组按顺序给出每次调用的返回值，没有返回值的调用记为 null。

示例 1

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

解释：依次放入 1、2 后，队头是 1，所以 peek 和 pop 都返回 1；此时队列里还剩 2，empty 返回 false。

数据范围

1 <= x <= 9
push、pop、peek、empty 合计最多调用 100 次。
所有调用都合法，例如不会对空队列执行 pop 或 peek。

进阶：能否让每个操作的均摊时间为 O(1)？也就是连续执行 n 次操作总共只花 O(n) 时间，个别操作可以慢一些。

解题思路：双栈均摊倒栈

一个输入栈 inp 只管接收 push；一个输出栈 out 只管提供 pop/peek。当 out 空了才把 inp 里的元素全部倒进 out，倒一次顺序反转，最早进来的元素就到了 out 栈顶。

为什么正确

out 从栈顶到栈底、再接 inp 从栈底到栈顶，恰好是队列从队首到队尾的顺序。

复杂度分析

每个元素最多被压入、倒过去、弹出各一次，均摊 O(1)；空间 O(n)。

易错点

只有 out 为空时才能倒栈；如果 out 里还有元素就把 inp 倒进去，新元素会压在旧元素上面，顺序就乱了。

参考代码

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

class MyQueue:
    def __init__(self):
        self.inp, self.out = [], []

    def push(self, x: int) -> None:
        self.inp.append(x)

    def move(self):
        if not self.out:
            while self.inp:
                self.out.append(self.inp.pop())

    def pop(self) -> int:
        self.move()
        return self.out.pop()

    def peek(self) -> int:
        self.move()
        return self.out[-1]

    def empty(self) -> bool:
        return not self.inp and not self.out

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();

    public MyQueue() {
    }

    public void push(int x) {
        in.push(x);
    }

    private void move() {
        if (out.isEmpty())
            while (!in.isEmpty())
                out.push(in.pop());
    }

    public int pop() {
        move();
        return out.pop();
    }

    public int peek() {
        move();
        return out.peek();
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

class MyQueue {
    stack<int> in, out;
    void move() {
        if (out.empty())
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
    }
public:
    MyQueue() {}

    void push(int x) {
        in.push(x);
    }

    int pop() {
        move();
        int v = out.top();
        out.pop();
        return v;
    }

    int peek() {
        move();
        return out.top();
    }

    bool empty() {
        return in.empty() && out.empty();
    }
};

type MyQueue struct {
	in, out []int
}

func Constructor() MyQueue {
	return MyQueue{}
}

func (this *MyQueue) Push(x int) {
	this.in = append(this.in, x)
}

func (this *MyQueue) move() {
	if len(this.out) == 0 {
		for len(this.in) > 0 {
			this.out = append(this.out, this.in[len(this.in)-1])
			this.in = this.in[:len(this.in)-1]
		}
	}
}

func (this *MyQueue) Pop() int {
	this.move()
	v := this.out[len(this.out)-1]
	this.out = this.out[:len(this.out)-1]
	return v
}

func (this *MyQueue) Peek() int {
	this.move()
	return this.out[len(this.out)-1]
}

func (this *MyQueue) Empty() bool {
	return len(this.in) == 0 && len(this.out) == 0
}

var MyQueue = function() {
    this.in = [];
    this.out = [];
};

MyQueue.prototype.push = function(x) {
    this.in.push(x);
};

MyQueue.prototype.move = function() {
    if (this.out.length === 0)
        while (this.in.length)
            this.out.push(this.in.pop());
};

MyQueue.prototype.pop = function() {
    this.move();
    return this.out.pop();
};

MyQueue.prototype.peek = function() {
    this.move();
    return this.out[this.out.length - 1];
};

MyQueue.prototype.empty = function() {
    return !this.in.length && !this.out.length;
};

class MyQueue {
    private inp: number[] = [];
    private out: number[] = [];

    constructor() {
    }

    push(x: number): void {
        this.inp.push(x);
    }

    private move(): void {
        if (this.out.length === 0)
            while (this.inp.length)
                this.out.push(this.inp.pop()!);
    }

    pop(): number {
        this.move();
        return this.out.pop()!;
    }

    peek(): number {
        this.move();
        return this.out[this.out.length - 1];
    }

    empty(): boolean {
        return !this.inp.length && !this.out.length;
    }
}

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

其他解法

入队时倒栈把代价放在每次 push 上，是 O(n)；双栈均摊倒栈只在输出栈为空时搬动，每个元素只搬一次，均摊 O(1)。

解法 2：入队时倒栈时间 push O(n)，其余 O(1)，空间 O(n)

始终让主栈 s 的栈顶是队首。push 时先把 s 全部倒入辅助栈 tmp，把 x 压入 s，再把 tmp 全部倒回 s。这样 x 落在栈底，pop 和 peek 直接操作栈顶。

实现简单，pop 和 peek 都是严格 O(1)。每次 push 都要搬动整个栈，入队多时明显慢于均摊做法。

class MyQueue:
    def __init__(self):
        self.s, self.tmp = [], []

    def push(self, x: int) -> None:
        while self.s:
            self.tmp.append(self.s.pop())
        self.s.append(x)
        while self.tmp:
            self.s.append(self.tmp.pop())

    def pop(self) -> int:
        return self.s.pop()

    def peek(self) -> int:
        return self.s[-1]

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

class MyQueue {
    private final Deque<Integer> s = new ArrayDeque<>(), tmp = new ArrayDeque<>();

    public MyQueue() {
    }

    public void push(int x) {
        while (!s.isEmpty()) tmp.push(s.pop());
        s.push(x);
        while (!tmp.isEmpty()) s.push(tmp.pop());
    }

    public int pop() {
        return s.pop();
    }

    public int peek() {
        return s.peek();
    }

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

class MyQueue {
    stack<int> s, tmp;
public:
    MyQueue() {}

    void push(int x) {
        while (!s.empty()) {
            tmp.push(s.top());
            s.pop();
        }
        s.push(x);
        while (!tmp.empty()) {
            s.push(tmp.top());
            tmp.pop();
        }
    }

    int pop() {
        int v = s.top();
        s.pop();
        return v;
    }

    int peek() {
        return s.top();
    }

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

type MyQueue struct {
	s, tmp []int
}

func Constructor() MyQueue {
	return MyQueue{}
}

func (this *MyQueue) Push(x int) {
	for len(this.s) > 0 {
		this.tmp = append(this.tmp, this.s[len(this.s)-1])
		this.s = this.s[:len(this.s)-1]
	}
	this.s = append(this.s, x)
	for len(this.tmp) > 0 {
		this.s = append(this.s, this.tmp[len(this.tmp)-1])
		this.tmp = this.tmp[:len(this.tmp)-1]
	}
}

func (this *MyQueue) Pop() int {
	v := this.s[len(this.s)-1]
	this.s = this.s[:len(this.s)-1]
	return v
}

func (this *MyQueue) Peek() int {
	return this.s[len(this.s)-1]
}

func (this *MyQueue) Empty() bool {
	return len(this.s) == 0
}

var MyQueue = function() {
    this.s = [];
    this.tmp = [];
};

MyQueue.prototype.push = function(x) {
    while (this.s.length) this.tmp.push(this.s.pop());
    this.s.push(x);
    while (this.tmp.length) this.s.push(this.tmp.pop());
};

MyQueue.prototype.pop = function() {
    return this.s.pop();
};

MyQueue.prototype.peek = function() {
    return this.s[this.s.length - 1];
};

MyQueue.prototype.empty = function() {
    return !this.s.length;
};

class MyQueue {
    private s: number[] = [];
    private tmp: number[] = [];

    constructor() {
    }

    push(x: number): void {
        while (this.s.length) this.tmp.push(this.s.pop()!);
        this.s.push(x);
        while (this.tmp.length) this.s.push(this.tmp.pop()!);
    }

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

    peek(): number {
        return this.s[this.s.length - 1];
    }

    empty(): boolean {
        return !this.s.length;
    }
}

设计专题的其他题目

查看设计全部题目 →