用栈实现队列（LeetCode 232）

题目描述：使用两个栈实现队列的下列操作：

push(x) 将元素 x 放入队列尾部
shift(x) 将元素 x 从队列头部移除
peek() 返回队列头部元素
empty() 返回队列是否为空

示例：

const queue = new MyQueue()
queue.push(1)
queue.push(2)
queue.peek() //  1
queue.shift() // 1
queue.empty() // false

思路分析：
栈是先进后出，队列是先进先出，本题的意思就是用栈实现先进先出
那么很明显只用一个栈 stack1 是不可能实现的，我们还需要一个辅助栈 stack2
元素在stack1 中一一进入，然后从尾部一一出栈再进入stack2，这时候stack2 的顺序就与 stack1 相反
stack2 中元素出栈的顺序就和队列的顺序一致了，也就是说队列 shift() 的时候就是 stack2 pop() ，前提是stack1 的元素要入栈到 stack2

class MyQueue {
  stack1 = []
  stack2 = [] // 辅助栈
  push(x) {
    this.stack1.push(x)
  }
  shift() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop())
      }
    }
    return this.stack2.pop()
  }
  peek() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop())
      }
    }
    return this.stack2[this.stack2.length -1]
  }
  empty(){
    return !this.stack1.length && !this.stack2.length
  }
}

双端队列解决窗口滑动问题（LeetCode hard）

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

const queue = [1,2,3,4] 
queue.push(5) // 队尾新增
queue.pop() // 队尾删除
queue.shift()// 队首删除
queue.unshift(0)// 队首新增

滑动窗口问题

题目描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例：
输入 nums = [1, 3, -1, -3, 5, 3, 6, 7] ， k=3
输出 [3,3,5,5,6,7]
提示：k 总有效，1 ≤ k≤ 输入数组的长度
思路分析：
这道题有两种解法：

双指针 + 遍历：使用双指针模拟窗口，在窗口范围内记录最大值，时间复杂度 O(kn)
双端队列：时间复杂度 O(n)
双指针 + 遍历
```javascript const maxSlidingWindow = function (nums, k) { // 缓存数组的长度 const len = nums.length; // 定义结果数组 const res = []; // 初始化左指针 let left = 0; // 初始化右指针 let right = k - 1; // 当数组没有被遍历完时，执行循环体内的逻辑 while (right < len) { // 计算当前窗口内的最大值 const max = calMax(nums, left, right); // 将最大值推入结果数组 res.push(max); // 左指针前进一步 left++; // 右指针前进一步 right++; } // 返回结果数组 return res; };

// 这个函数用来计算最大值 function calMax(arr, left, right) { // 处理数组为空的边界情况 if (!arr || !arr.length) { return; } // 初始化 maxNum 的值为窗口内第一个元素 let maxNum = arr[left]; // 遍历窗口内所有元素，更新 maxNum 的值 for (let i = left; i <= right; i++) { if (arr[i] > maxNum) { maxNum = arr[i]; } } // 返回最大值 return maxNum; }

<a name="OPEWE"></a>
### 双端队列法（推荐）
双端队列法的核心在于维护一个递减的双端队列，这样队列的第一个元素始终是最大值，避免了在窗口内循环找最大值的过程
```javascript
const maxSlidingWindow = function(nums, k){
  let res = []
  let len = nums.length
  // 初始化双端队列，里面维护元素的索引
  const deque = [] 
  for(let i=0;i < len; i++){
    // 先判断能不能维持递减，不能的话把前面笑的元素 pop 出来
    while(deque.length && nums[i] >= nums[ deque[deque.length -1]]){
      deque.pop()
    }
    // 维持递减队列才能 push
    deque.push(i)
    // 这也是为什么 deque 存的不是值而是索引，用来判断还在不在窗口内
    if(deque[0] === i-k){  // 如果最大值已经不在窗口范围内了
      deque.shift()
    }
    if(i >= k-1){ // 前k个元素的时候，窗口还没移动
      res.push(nums[deque[0]])
    }
  }
  return res
}

队列

用栈实现队列（LeetCode 232）

双端队列解决窗口滑动问题（LeetCode hard）

滑动窗口问题

双指针 + 遍历