Loading...
墨滴

CYF

2021/04/25  阅读:27  主题:默认主题

用两个栈实现队列

用两个队列实现栈

来源:力扣(LeetCode)

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail(添加) 和 deleteHead(删除) ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]

示例 2:

输入:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]

什么意思呢?起初看得我也是一懵一懵的

["CQueue","appendTail","deleteHead","deleteHead"] :代表的就是要执行的顺序

[[],[3],[],[]]:表示上面执行操作的参数

[null,null,3,-1]:表示操作的结果(返回值)

  1. 先创建队列,返回null,不需要传参数
  2. 添加队列元素3,返回null,需要传参
  3. 在对头删除元素,返回被删除的元素,不需要传参
  4. 再删除对头元素,若队列为空,返回-1,不需要传参

所以只有添加队列元素才需要传参,删除队头返回被删除元素,否则返回-1,其余操作均返回null

就是这么一个意思

而我们就是用数组来表示栈和队列,总的思路就是:

  • 把元素先存(push)进栈1
  • 然后再把栈1的元素从其尾部依次取出,存(push)到栈2
  • 删除的时候再从栈2的尾部开始取出元素

这样便可实现先进的元素先出

// 创建一个队列函数
var CQueue = function({
    // 定义两个栈
    this.stack1 = []
    this.stack2 = []
};

// 定义添加appendTail方法,添加元素
CQueue.prototype.appendTail = function(value{
    // 先存进栈1
    this.stack1.push(value)
    
    // 如果栈2为空的话,从栈1尾部取,往栈2尾部存
    if (!this.stack2.length) {
        while (this.stack1.length) {
            this.stack2.push(this.stack1.pop())
        }
    // 如果栈2不为空的话,从栈1头部取,往栈2的头部存
    } else {
        while (this.stack1.length) {
            this.stack2.unshift(this.stack1.shift())
        }
    }
};

// 删除元素
CQueue.prototype.deleteHead = function({  
    /*
    if (this.stack2.length === 0) {
        return -1
    } else {
        return this.stack2.pop()
    }*/

    // 等价于上面代码
    return this.stack2.pop() || -1
};

/**
 * var obj = new CQueue()  // 实例化构造函数obj
 * obj.appendTail(value)   // 添加元素
 * var param_2 = obj.deleteHead()  // 删除元素
 */

img
img

CYF

2021/04/25  阅读:27  主题:默认主题

作者介绍

CYF