队列的典型题：栈实现队列、双端队列
最近在看数据结构和算法，努力总结出道~
TL;DR
队列的特点：先进先出。
练习：用栈实现队列
网络异常，图片无法展示
|
栈后进先出，队列先进先出。
思路是：「输入栈」正常push的时候，相当于队列的倒序；如果把「输入栈」的元素逐个弹出放到「输出栈」，相当于正序的队列，此时弹出就实现了先进先出。
步骤：
- 把一个栈当做「输入栈」，把另一个栈当做「输出栈」
- 当 push() 新元素的时候，进入「输入栈」
- 当 pop() 元素的时候，优先从「输出栈」弹出元素。如果「输出栈」为空，则把「输入栈」的元素逐个推进到「输出栈」中，这样「输出栈」相当于正序的队列，可以执行pop的操作了
网络异常，图片无法展示
|
/** * Initialize your data structure here. */ var MyQueue = function () { // 取出只能从这个栈里，如果这个栈空的话，就把inStack都放进来，再取出栈顶 this.outStack = []; // 进队只能从这个栈里 this.inStack = []; }; /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function (x) { this.inStack.push(x); }; /** * Removes the element from in front of queue and returns that element. * @return {number} */ MyQueue.prototype.pop = function () { if (this.outStack.length) { return this.outStack.pop(); } while (this.inStack.length) { this.outStack.push(this.inStack.pop()); } return this.outStack.pop(); }; /** * Get the front element. * @return {number} */ MyQueue.prototype.peek = function () { if (this.outStack.length) { return this.outStack[this.outStack.length - 1]; } while (this.inStack.length) { this.outStack.push(this.inStack.pop()); } return this.outStack.length && this.outStack[this.outStack.length - 1]; }; /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function () { return !this.outStack.length && !this.inStack.length; };
这里注意，虽然取出的操作，可能有循环，但是均摊时间复杂度其实O(1)，可以简单理解为大部分的取出都是O(1)。
练习：双端队列
双端队列就是允许在队列的两端进行插入和删除的队列。
体现在编码上，最常见的载体是既允许使用 pop、push 同时又允许使用 shift、unshift 的数组。
网络异常，图片无法展示
|
普通办法：循环，找出每个窗口的最大值，时间复杂度O(kn)。
于是，还是用空间换时间，采用双向队列法，让复杂度变成O(n)
思路：窗口移动，维护队列，让队首始终是当前窗口的最大值的索引。队列是递减队列，存放索引，推进值之后，判断队首是不是在窗口之外，之外则移除。移除之后，新的队首就是当前窗口的最大值。
步骤：
- 遍历给定数组中的元素，
- 如果队列不为空且当前值
>队尾元素，则将队尾元素移除。直到，队列为空或当前值小于新的队尾元素，才将当前值推进队列； - 当队首元素的下标
<当前窗口左边界L时，表示队首元素已不在滑动窗口内，需要将其从队首移除。 - 此时，队首元素就是该窗口内的最大值。但由于数组下标从0开始，只有当窗口右边界
R>=k-1时，才意味着窗口形成，注意这个前提条件。
网络异常，图片无法展示
|
演示和思路是元素，但实际代码中，为了方便操作，队列存储的是索引。
const last = (arr) => arr[arr.length - 1]; const first = (arr) => arr[0]; var maxSlidingWindow = function (nums, k) { // 存储最大值的数组 let res = []; // 递减队列 let queue = []; // 遍历，R表示滑动窗口右边界 for (let R = 0; R < nums.length; R++) { const cur = nums[R]; // 维护递减队列，只要当前值大于队列末端，就pop，直到小于或者为空才进队 while (queue.length && cur > nums[last(queue)]) { queue.pop(); } queue.push(R); // 窗口左边的指针索引 const L = R - k + 1; // 队首的索引小于L，表示在窗口之外了，需要移除 if (first(queue) < L) { queue.shift(); } // 当R>=k-1的时候，窗口形成，此时队首是最大值的索引，存到res中 if (R >= k - 1) { res[L] = nums[first(queue)]; } } return res; };
