队列

栈向队列的转化双端队列

关于队列，在算法面试中大家需要掌握以下重点：

栈向队列的转化

双端队列

优先队列

栈向队列的转化

队列——先入先出，怎么用栈表示队列呢，就用两个栈，一个存，一个出，出的时候将存的队列倒过来压进去即可

232. 用栈实现队列


var MyQueue = function() {
    this.stack = []
    this.stack2 = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stack.push(x)
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
	// 如果stack2为空就把stack1 倒着压进stack2
    if(this.stack2.length === 0){
        while(this.stack.length){
            this.stack2.push(this.stack.pop())
        }
    }
    return this.stack2.pop()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if(this.stack2.length === 0){
        while(this.stack.length){
            this.stack2.push(this.stack.pop())
        }
    }
    return this.stack2 && this.stack2[this.stack2.length-1]
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.stack.length === 0 && this.stack2.length === 0
};

双端队列

双端队列就是允许在队列的两端进行插入和删除的队列

就是支持 push pop shift unshift的数组

双端队列——>滑动窗口问题

239. 滑动窗口最大值

暴力法：两层嵌套循环就完了


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if(!nums.length){
        return []
    }
    const res = []
    for(let i =0;i+k<=nums.length;i++){
        let max = nums[i]
        for(let j = i;j<i+k;j++){
            if(nums[j]>=max){
                max = nums[j]
            }
        }
        res[i] = max
    }
    return res
};

每次把k个数入辅助队列，当推进去的值大于队尾的值时，辅助队尾出队，始终保持队头是最大的值，然后输出队头就是K个数中最大值。当移动时判断移开的值是否是队头，如果是则出队。


const maxSlidingWindow = function (nums, k) {
  // 缓存数组的长度
  const len = nums.length;
  // 初始化结果数组
  const res = [];
  // 初始化双端队列
  const deque = [];
  // 开始遍历数组
  for (let i = 0; i < len; i++) {
    // 当队尾元素小于当前元素时
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      // 将队尾元素（索引）不断出队，直至队尾元素大于等于当前元素
      deque.pop();
    }
    // 入队当前元素索引（注意是索引）
    deque.push(i);
    // 当队头元素的索引已经被排除在滑动窗口之外时
    while (deque.length && deque[0] === i - k) {
      // 将队头元素索引出队
      deque.shift();
    }
    // 判断滑动窗口的状态，只有在被遍历的元素个数大于 k 的时候，才更新结果数组
    if (i >= k - 1) {
      res.push(nums[deque[0]]);
    }
  }
  // 返回结果数组
  return res;
};