【前端算法系列】堆栈和队列

堆栈

堆栈（英文：stack），又称为栈或堆叠。是一种LIFO（LAST IN FIRST OUT 后进先出）的数据结构，对栈数据的操作有push（入栈）和pop（出栈），数据的入栈和出栈都只能在栈顶。

堆栈与DFS

深度优先搜索（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。该算法与堆栈有着千丝万缕的关系。DFS算法通常需要用到堆栈结构。例如，寻找二叉树中的目标节点。

如下图所示，红色表示死胡同，绿色G表示目标，我们一起看看DFS是如何寻找目标的：

1、从入口A出发，首先来到第一个分岔口，有B和C两条路，

2、遍历B，发现是死胡同，回退到最近的分岔口A，尝试往C方向走；

3、遍历C，发现是一个分岔口，有D、E、F三条路，

4、遍历D，发现是死胡同，回退到分岔口C，

6、遍历E，发现有G一条路，

7、遍历G，找到出口，成功走出“迷宫”！

DFS算法的思路，是试图穷举全部路径。 遍历的目标时，一个劲的往下走，直至无路可走，这大概是深度优先算法中“深”的由来吧！这种思路跟堆栈的数据结构契合。例如上面的例子，用堆栈的方式可以表示如下：

看完上图，相信大家对堆栈和DFS已经有了一定的了解，下面我们来看看与堆栈相关的算法题。

最小栈问题

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

此题的解法如下：

/**
 * initialize your data structure here.
 */
var MinStack = function () {
    this.stack = [] // 初始化一个数组
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
    this.stack.push(x) // 用数组的push方法模拟栈的push方法
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
    return this.stack.pop() // 用数组的pop方法，模拟栈的pop方法
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
    // 做非空判断
    if (!this.stack || !this.stack.length) {
        return
    }

    return this.stack[this.stack.length - 1] // 返回数组最后一个元素（即栈顶的元素）
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
    var minVal = Infinity; // 初始化最小值为Infinity
    const { stack } = this
    for (var i = 0; i < stack.length; i++) { // 遍历堆栈，找到比初始值小的值就替换，一轮遍历即可找到最小值。
        if (stack[i] < minVal) {
            minVal = stack[i]
        }
    }
    return minVal
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

有效的括号问题

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true 

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

1 <= s.length <= 104

s 仅由括号 '()[]{}' 组成

此题的解法如下：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    let stack = []
    const leftToRight = {
        '{': '}',
        '[': ']',
        '(': ')',
    }

    const len = s.length

    for (let i = 0; i < len; i++) {
        const char = s[i]
        if (char === '{' || char == '[' || char === '(') { // 缓存对应的右括号到stack中
            stack.push(leftToRight[char])
        } else {
            // 如果栈为空（空字符串）或栈顶的元素（上一个子符）和当前遍历的字串不一致，说明括号无法闭合，返回false，循环结束。
            if (!stack.length || stack.pop() !== char) {
                return false
            }
        }
    }

    // 如果stack被清空，说明字符串是有效的括号
    return !stack.length
};

队列

队列（queue），是一种先进先出（FIFO, First-In-First-Out）的线性表。队列只允许在后端插入（Enqueue）操作，在前端进行删除操作（Dequeue）。

队列与BFS

BFS算法的实现通常依赖队列这种数据结构，如下图所示，红色表示死胡同，绿色G表示目标，我们一起看看DFS是如何寻找目标的：

1、遍历第2层数据，访问A，有B和C两条路，保存为下一层的遍历数据，清空A数据。

2、遍历第2层数据，访问B，发现是死胡同，清空B数据；遍历C，发现D、E、F，保存为下一层的遍历数据，清空C数据；

3、遍历第3层数据，访问D，发现是死胡同，清空D数据；遍历E，发现G，保存为下一层的遍历数据，清空E数据，遍历F数据并清空；

4、遍历第4层数据，访问G，目标找到。

BFS算法的思路，是逐层遍历，遍历到哪个层，就把该层的所有数据都遍历完，才考虑下一层。注重的是广度优先，这大概是广度优先算法中“广”的由来吧！这种思路的实现需要用到队列这种数据结构。

上面的例子，用队列的方式可以表示如下：

队列算法真题

如何用栈实现一个队列？

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

• 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 操作）。

解题思路：

认真看文章的人都知道，堆栈是LIFO（后进先出）的数据结构，而队列是FIFO（先进先出）的数据结构。堆栈只能在栈顶操作元素，而队列可以从尾部插入数据，从头部取出数据。显然，一个堆栈是不可能实现队列的要求的。聪明的小伙伴可能已经想到了，两个堆栈！是的，没有什么是两个堆栈解决不了的，如果有就是三个......回归正题，下面我介绍一下如何用两个堆栈实现一个队列。

根据题目描述，队列要有push方法，堆栈本身就有push方法，所以可以直接套用，问题不大。而pop方法，堆栈是没有的，要实现pop方法，需要两个堆栈（stack1和stack2）。如下图所示，调用队列的push方法时，始终将元素push到stack1中：

调用pop方法时，始终从stack2取数据。当stack2不为空，直接从stack2中取出数据，当stack2为空时，将stack1中的数据转移到stack2中，再从stack2中取数据。此时，有人可能会问：如果此时还有数据push进来怎么办？没错，先push到stack1中。

总而言之，就是始终push到stack1中，始终从stack2中pop数据。

该题的参考解法如下：

/**
 * 初始化构造函数
 */
const MyQueue = function () {
  // 初始化两个栈
  this.stack1 = [];
  this.stack2 = [];
};

/**
* 在MyQueue的原型中添加push方法
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
  // 直接调度数组的 push 方法
  this.stack1.push(x);
};

/**
* 在MyQueue的原型中添加pop方法
* @return {number}
*/
MyQueue.prototype.pop = function () {
  // 假如 stack2 为空，需要将 stack1 的元素转移进来
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length !== 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 为了达到逆序的目的，我们只从 stack2 里出栈元素
  return this.stack2.pop();
};


/**
* 在MyQueue的原型中添加peek方法.
* @return {number}
* 这个方法和 pop 唯一的区别就是没有将定位到的值出栈
*/
MyQueue.prototype.peek = function () {
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length != 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 缓存 stack2 的长度
  const stack2Len = this.stack2.length;
  return stack2Len && this.stack2[stack2Len - 1];
};

/**
* 在MyQueue的原型中添加empty方法.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
  // 若 stack1 和 stack2 均为空，那么队列空
  return !this.stack1.length && !this.stack2.length;
};

关于堆栈和队列的知识就先介绍到这里了，还有好多经典题目可以搬出来的。同样作为前端的我，也是一边学一边写文章的，希望可以把学到的知识以通俗的方式展现给大家。如有纰漏，欢迎大家在评论区指出。

码文不易，如果您觉得本文帮助到您，请为我点个赞吧!