【力扣】两个栈实现队列-化栈为队(TS)

今天药忘吃喽~ 2023-01-08 05:27 65阅读 0赞

## 题目 ##

实现一个MyQueue类，该类用两个栈来实现一个队列。

***示例：***

> MyQueue queue = new MyQueue();  
> queue.push(1);  
> queue.push(2);  
> queue.peek(); // 返回 1  
> queue.pop(); //返回 1  
> queue.empty(); // 返回 false

***说明：***

> 1.你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size 和 is empty操作是合法的。  
> 2.你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。  
> 3.假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

## 思路 ##

> 1.新建两个栈（数组），一个numStack用于存放插入的数，helpStack用于执行弹出操作。  
> 2.当push的时候，直接执行numStack.push操作即可  
> 3.当pop的时候，由于我们需要弹出先插入到栈中的元素，因此，我们可以再借助一个栈，将原有栈逆序即可。这里若helpStack为空，则需要将numStack中的元素全部取出压入到helpStack中，然后从helpStack中pop元素即可。否则直接从helpStack中pop元素即可。也就是说，只有helpStack为空的时候。才将numStack元素全部压入到helpStack中。  
> 4.由于pop操作与peek操作就多了一步弹出元素的操作，因此pop可以复用peek的代码。  
> 5.数组长度为0即为empty

## 解 ##

class MyQueue { 
        private numStack;
        private helpStack;
        constructor() { 
            this.numStack = [];
            this.helpStack = [];
        }
    
        push(x: number): void { 
            this.numStack.push(x);
        }
    
        pop(): number { 
            this.peek();
            return this.helpStack.pop();
        }
    
        peek(): number { 
            if (this.helpStack.length === 0) { 
                while (this.numStack.length !== 0) { 
                    this.helpStack.push(this.numStack.pop());
                }
            }
            return this.helpStack[this.helpStack.length-1];
        }
    
        empty(): boolean { 
            return this.numStack.length === 0 && this.helpStack.length === 0
        }
    }
    
    /** * Your MyQueue object will be instantiated and called as such: * var obj = new MyQueue() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.peek() * var param_4 = obj.empty() */