栈：9、30、59

[janeLLLL]

9. 用两个栈实现一个队列

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

   示例 1：

   输入：
   ["CQueue","appendTail","deleteHead","deleteHead"]
   [[],[3],[],[]]
   输出：[null,null,3,-1]示例 2：
   

   实例2：

   输入：
   ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
   [[],[],[5],[2],[],[]]
   输出：[null,-1,null,null,5,2]提示：
   

   1 <= values <= 10000
   最多会对 appendTail、deleteHead 进行 10000 次调用

   解题思路：

   • 队列先进后出

   • 栈1队头，栈2队尾

   • 队列增=栈1.push(value)、队列减=栈2.pop()

   • 情况：

     1.栈2没有出列元素，那么：

     1.1 栈1出栈、栈2进栈，最后栈2出栈的元素，即为该次需要模拟的出队元素

     1.2 栈1没有元素，返回-1

   • 

   代码：

   var CQueue = function() {
       this.stack1 = []//头部：出栈
       this.stack2 = []//尾部：进栈
   };
   
   /** 
    * @param {number} value
    * @return {void}
    */
   //尾部插入整数
   CQueue.prototype.appendTail = function(value) {
       this.stack1.push(value)
   };
   
   /**
    * @return {number}
    */
   //头部删除整数
   CQueue.prototype.deleteHead = function() {
       if(this.stack2.length){
       //1.当栈2不为空，对其进行弹出元素指令
           return this.stack2.pop()
       }else if(!this.stack2.length){
       //2.当栈2为空，需要把栈1元素转移到栈2中
           if(!this.stack1.length){
               return -1
           }
           while(this.stack1.length){
               var x = this.stack1.pop()
               this.stack2.push(x)
           }
           return this.stack2.pop()
       }
   };

10. 包含min函数的栈

    定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

    示例:
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.min();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.min();   --> 返回 -2.
    

    提示：

    各函数的调用总次数不超过 20000 次

解题思路：

代码：

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = []
    this.minValue = Number.MAX_VALUE//假定,为什么0不可以
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    var item = x - this.minValue
    if(item < 0){
        this.minValue = x
    }
    this.stack.push(item)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    var item = this.stack.pop()
    //item = x - min
    if(item < 0){
        this.minValue = this.minValue - item
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    if(!this.stack.length){
        return null
    }else{
        var realValue = this.minValue - this.stack[0]
        return realValue
    }
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
    if(!this.stack.length){
        return null
    }else{
        return this.minValue
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

59. 队列最大值

    请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

    若队列为空，pop_front 和 max_value 需要返回 -1

    示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

解题思路：

• 维护一个单调的双端队列
• 需要注意pop()+unshift(),push()+shift()

代码：

var MaxQueue = function() {
    this.queue1 = []
    this.queue2 = []
};

/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function() {
    if (this.queue2.length) {
        return this.queue2[0];
    }
    return -1;
};

/** 
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function(value) {
    this.queue1.push(value);//队列1存储所有元素
    while (this.queue2.length && this.queue2[this.queue2.length - 1] < value) {
        this.queue2.pop();
    }//将队列2的元素从后往前和当前插入元素比较，如果出现大于当前插入元素的数据便停止
    this.queue2.push(value);//从队头插入当前元素，保证比后面的元素要小
};

/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function() {
    if (!this.queue1.length) {
        return -1;
    }
    const value = this.queue1.shift();//队列1弹出元素
    if (value === this.queue2[0]) {
        this.queue2.shift();//队列2
    }
    return value;
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * var obj = new MaxQueue()
 * var param_1 = obj.max_value()
 * obj.push_back(value)
 * var param_3 = obj.shift_front()
 */