队列算法题

需要位置对比的题目，队列 或 栈 内放的不是数，而是位置i

一般要不考察单增队列，要不就单减队列

3.用栈实现队列 （ LeetCode 232 ）

var MyQueue = function() {
    this.s1 = [] // 真正储存数据
    this.s2 = [] // push的时候临时存放数据
};

MyQueue.prototype.push = function(x) { // O(n) O(n)
    while(this.s1.length) {
        this.s2.push(this.s1.pop())
    }
    this.s1.push(x)
    while(this.s2.length) {
        this.s1.push(this.s2.pop())
    }
};

MyQueue.prototype.pop = function() {
    return this.s1.pop()
};

MyQueue.prototype.peek = function() {
    return this.s1[this.s1.length -1]
};

MyQueue.prototype.empty = function() {
    return !this.s1.length
};

接下来这种方法节省了每次push都需要反转s1的情况，

类似于懒加载，pop的时候需要反转才反转，

反转后就直接放在s2,pop的时候直接从s2拿，s2没有就再反转是s1

var MyQueue = function() {
    this.s1 = [] // 真正储存数据
    this.s2 = [] // push的时候临时存放数据
    this.front = null
};

// push永远都push在s1,而s2中的数据更早入栈
MyQueue.prototype.push = function(x) {
    if(!this.s1.length) {
        this.front = x
    }
    this.s1.push(x)
};
// pop数据时,s2没有就去把s1的全部倒置到s2,此时s2栈顶的元素就是最早的
// 此处的pop有点懒加载的感觉,用到了我才去翻转s1
MyQueue.prototype.pop = function() {
    if(!this.s2.length) {
        while(this.s1.length) {
            this.s2.push(this.s1.pop())
        }
    }
    return this.s2.pop()
};

// peek返回(但不删除)最早入队列的元素(队首元素)
// front专门用来考虑s2无数据,最早入栈元素在s1的情况,此时peek就拿front
MyQueue.prototype.peek = function() {
    const S2 = this.s2
    return !S2.length ? this.front : S2[S2.length - 1]
};

MyQueue.prototype.empty = function() {
    return !this.s1.length && !this.s2.length
};

4.滑动窗口最大值（ LeetCode 239 ）

leetcode

想快速获取最大值，就维护一个单调递减的双端队列，左侧永远是最大值

如果队列头超出 滑动窗口左边界，就去除。(队列内放位置i，而不是值，方便对比位置)

当i >= k - 1,滑动窗口装满，才开始排res

var maxSlidingWindow = function (nums, k) {
    const queue = []
    const res = []
    const l = nums.length
    for (let i = 0; i < l; i++) {
        while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
            queue.pop()
        }
        queue.push(i)
        if (queue[0] === i - k) {
            queue.shift();
        }
        if (i >= k - 1) {
            res.push(nums[queue[0]])
        }
    }
    return res
};