《JavaScript解题秘籍：力扣队列与栈的高效解题策略》

 

232.用栈实现队列

力扣题目链接(opens new window)

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

 这道题就是向让我们用栈来模拟队列的操作，其实没有什么难点。我把解释写在代码注释里。

var MyQueue = function() { this.stackIn = []; this.stackOut = []; }; /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function(x) { this.stackIn.push(x); }; /** * Removes the element from in front of queue and returns that element. * @return {number} */ //取对队头元素就是栈底元素 MyQueue.prototype.pop = function() { const size = this.stackOut.length; if(size) { return this.stackOut.pop(); } while(this.stackIn.length) { this.stackOut.push(this.stackIn.pop()); } return this.stackOut.pop(); }; /** * Get the front element. * @return {number} */ //这里注意使用pop方法会将这个元素给出栈掉，因此我们要把它还回去。 MyQueue.prototype.peek = function() { const x = this.pop(); this.stackOut.push(x); return x; }; /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function() { return !this.stackIn.length && !this.stackOut.length }; 225. 用队列实现栈

力扣题目链接(opens new window)

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈pop() -- 移除栈顶元素top() -- 获取栈顶元素empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

这两道题确实很适合我们掌握栈和队列之间的区别，分别用栈模拟队列和用队列模拟栈让我们看到了他们之间的区别：

在用栈模拟队列时，在访问队尾操作时由于栈的特性所以我们只能采用遍历的方法。 

同样：在用队列模拟栈时，在访问栈顶操作时因为队列只能先进先出所以我们要一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

var MyStack = function() { this.queue=[] }; /** * @param {number} x * @return {void} */ MyStack.prototype.push = function(x) { this.queue.push(x) }; /** * @return {number} */ MyStack.prototype.pop = function() { let size = this.queue.length; while(size-- > 1) { this.queue.push(this.queue.shift()); } return this.queue.shift(); }; /** * @return {number} */ MyStack.prototype.top = function() { const x = this.pop(); this.queue.push(x); return x; }; /** * @return {boolean} */ MyStack.prototype.empty = function() { return !this.queue.length; }; /** * Your MyStack object will be instantiated and called as such: * var obj = new MyStack() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.top() * var param_4 = obj.empty() */ 20. 有效的括号

力扣题目链接(opens new window)

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"输出: true

示例 2:

输入: "()[]{}"输出: true

示例 3:

输入: "(]"输出: false

示例 4:

输入: "([)]"输出: false

示例 5:

输入: "{[]}"输出: true

 这道题简直是为了栈定制的一道题，我们的思路就是先把字符串里的元素压入栈中，在这里我们设置一个map组，只让他压入朝向一边的括号。然后我们判断另一半。

结合代码解释一下：  

var isValid = function(s) { const stack = [], //这个是为了利用map的特性找到它的另一半 map = { "(":")", "{":"}", "[":"]" }; for(const x of s) { //把朝向一致的括号压入栈中 if(x in map) { stack.push(x); continue; }; //处理另一朝向的括号，如果不满足就不是有效的括号 if(map[stack.pop()] !== x) return false; } return !stack.length; };

 

1047. 删除字符串中的所有相邻重复项

力扣题目链接(opens new window)

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"输出："ca"解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= S.length <= 20000S 仅由小写英文字母组成。

 这道题就是消消乐哈，也是通过栈的形式来实现。我借助一下代码随想录的动画来演示一下：

 

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？

所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。

代码如下：  

var removeDuplicates = function(s) { const result = [] for(const i of s){ if(i === result[result.length-1]){ result.pop() }else{ result.push(i) } } return result.join('') }; 150. 逆波兰表达式求值

力扣题目链接(opens new window)

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 + ,  - ,  * ,  / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: ["2", "1", "+", "3", " * "]输出: 9解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入: ["4", "13", "5", "/", "+"]输出: 6解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入: ["10", "6", "9", "3", "+", "-11", " * ", "/", " * ", "17", "+", "5", "+"]

输出: 22

解释:该算式转化为常见的中缀算术表达式为：

((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

逆波兰式就是计算机很喜欢的后缀表达式，感觉本章节只要掌握了栈和队列的特性其他通过模拟就可以完成。

 

var evalRPN = function (tokens) { const stack = []; for (const token of tokens) { if (isNaN(Number(token))) { // 非数字 const n2 = stack.pop(); // 出栈两个数字 const n1 = stack.pop(); switch (token) { // 判断运算符类型，算出新数入栈 case "+": stack.push(n1 + n2); break; case "-": stack.push(n1 - n2); break; case "*": stack.push(n1 * n2); break; case "/": stack.push(n1 / n2 | 0); break; } } else { // 数字 stack.push(Number(token)); } } return stack[0]; // 因没有遇到运算符而待在栈中的结果 };

我们从字符串的头部开始寻找，如果是数字就把他压入栈中，要是是符号就走switch并且通过出栈拿到两个要进行运算的数字。

239. 滑动窗口最大值

力扣题目链接(opens new window)

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

 

提示：

1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length

这道题我们第一下想到的肯定是暴力，但是这是O（n*k）的算法。我们可以通过单调队列来实现我们这道题。 

对于窗口里的元素{2, 3, 5, 1 ,4}，单调队列里只维护{5, 4} 就够了，保持单调队列里单调递减，此时队列出口元素就是窗口里最大元素。

此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢？

设计单调队列的时候，pop，和push操作要保持如下规则：

pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值

var maxSlidingWindow = function(nums, k) { if (nums.length === 0 || k === 0) return []; let resArr = []; let helperQueue = []; // 单调队列，用于存储索引 let i = 0, j = 0; while (j < nums.length) { // 维护单调队列的非严格递减性质 while (helperQueue.length > 0 && nums[helperQueue[helperQueue.length - 1]] < nums[j]) { helperQueue.pop(); } helperQueue.push(j); // 当窗口大小达到k时，开始收集结果 if (j - i + 1 === k) { resArr.push(nums[helperQueue[0]]); // 移除离开窗口的元素的索引 if (helperQueue[0] === i) { helperQueue.shift(); } i++; } j++; } return resArr; };

 暴力又有什么不好呢~只是大家更喜欢单调队列吧。就像她不喜欢笨拙真诚的你，却喜欢花言巧语的他罢了。