用栈实现队列(面试常考) 超、凢脫俗 2022-10-23 09:59 80阅读 0赞 # 一、题目描述 # 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: * void push(int x) 将元素 x 推到队列的末尾 * int pop() 从队列的开头移除并返回元素 * int peek() 返回队列开头的元素 * boolean empty() 如果队列为空,返回 true ;否则,返回 false **示例:** 输入: ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 1, 1, false] 解释: MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false **提示:** * 1 <= x <= 9 * 最多调用 100 次 push、pop、peek 和 empty * 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作) # 二、思路分析 # 首先看栈和队列的区别: * 栈:**先进后出(后进先出)** * 队列:**先进先出** * **push**:都是加到末尾,依次加入1、2、3 * **pop**:栈是删除并返回末尾元素3,队列是删除并返回开头元素1 ![750f9b2d07961c6424afb28cec918537.png][] 这一顿比较后发现,用栈实现队列的难度就在于如何将栈底的元素取出。 每次取元素都是需要从栈底开始取,那这刚好就是出栈操作的逆序。 我们再用一个栈来存储逆序元素,每次取出时去这个栈里正常出栈即可: ![0d274ef813b55a25eaf4440798254aec.png][] 维持这样一个**逆序栈**: * 正常入元素时push到stack1 * 取元素时先检查stack2是否为空: * stack2为空时,先将stack1中的元素逆序到stack2中,再从stack2中pop * stack2不为空时,直接从stack2中pop **peek()**:pop()实现了之后peek()的实现也就简单了: peek()与pop()的区别就是 peek没有将值出栈。 **empty**:检查两个栈是否为空即可。 # 三、AC 代码 # /** * Initialize your data structure here. */ var MyQueue = function() { this.stack1 = []; this.stack2 = []; }; /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function(x) { this.stack1.push(x); }; /** * Removes the element from in front of queue and returns that element. * @return {number} */ MyQueue.prototype.pop = function() { if(this.stack2.length <= 0){//如果stack2为空则先将stack1中的元素放进来 while(this.stack1.length > 0){ //将 stack1 出栈的元素再推入 stack2,实现逆序 this.stack2.push(this.stack1.pop()); } } return this.stack2.pop();//出栈 }; /** * Get the front element. * @return {number} */ MyQueue.prototype.peek = function() { if(this.stack2.length <= 0){//如果stack2为空则先将stack1中的元素放进来 while(this.stack1.length > 0){ //将 stack1 出栈的元素再推入 stack2,实现逆序 this.stack2.push(this.stack1.pop()); } } return this.stack2.length && this.stack2[this.stack2.length - 1];//返回栈顶元素 }; /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function() { return !this.stack1.length && !this.stack2.length; }; /** * 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() */ # 四、总结 # * 栈:先进后出、队列:先进先出;队列取出元素的顺序是栈的**逆序**,所以维持一个逆序栈。 [750f9b2d07961c6424afb28cec918537.png]: /images/20221023/2c3260d541e14af1ad23abd4fc443ef3.png [0d274ef813b55a25eaf4440798254aec.png]: /images/20221023/3ad8acf1098446f9938faa9620a79bb5.png
还没有评论,来说两句吧...