剑指Offer——II. 队列的最大值（JS实现）

var MaxQueue = function() {
    this.queue = [];
    this.stack = [];
};
MaxQueue.prototype.max_value = function() {
    if (this.stack.length !== 0) {
        return this.stack[0]
    } else {
        return -1;
    }
};
// ! 解题关键：模拟队列的首元素得是最大值
MaxQueue.prototype.push_back = function(value) {
    this.queue.push(value);
    if (this.stack.length === 0) {
        this.stack.push(value)
    } else {
        // 本题易错点：在下面这段代码，原因在于我们不仅要保证头元素是最大值，还要保证如果一旦头元素被pop之后，第二个元素也是相对于其他元素来说是最大的
        // while循环确保stack中全是比value大的，然后把value放到最后，这样就形成了一个降序排列
        while (this.stack[this.stack.length - 1] < value) {
            this.stack.pop();
        }
        this.stack.push(value);
    }
};
MaxQueue.prototype.pop_front = function() {
    if (this.queue.length !== 0) {
        if (this.queue[0] === this.stack[0]) {
            this.stack.shift();
        }
        return this.queue.shift();
    } else {
        return -1;
    }
};