leetcode232-用栈实现队列

leetcode 232

思路

由于栈：先进后出，队列：先进先出，所以push进去的元素，实际上是要先出的

要用栈实现队列的功能，需要两个栈来存放，一个栈存入栈的位置，一个是出栈的位置，两个栈的存放位置应该是相反的，假设inStack = [1,2]
我们希望出栈顺序是：1，2，但是数组的pop操作是2，1，所以我们设置outStack = [2,1]，入栈放到inStack中，出栈从outStack中取
有一个需要注意的点是，我们把栈中的元素都放入到outStack中以后，假设inStack = [], outStack = [2,1]，那么这时候再push(3)以后，inStack = [3]，下次执行pop操作的时候要再进行转换吗？

如果此时我在pop前再执行转换in2out操作，那么outStack = [2,1,3]，下次如果pop就不正确，所以只有当outStack中的内容都pop完以后才可以再把inStack中的内容放到outStack中，这样顺序才是正确的

实现

class MyQueue {
    private inStack;
    private outStack;
    constructor() {
        this.inStack = [];
        this.outStack = [];
    }

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

    pop(): number {
        if (!this.outStack.length) {
            this.in2out()
        }
        return this.outStack.pop()
    }

    peek(): number {
        if (!this.outStack.length) {
            this.in2out()
        }
        return this.outStack[this.outStack.length - 1]
    }

    empty(): boolean {
        return this.inStack.length === 0 && this.outStack.length === 0;
    }
    in2out(): void {
        while (this.inStack.length) {
            this.outStack.push(this.inStack.pop())
        }
    }
}