什么是栈

什么是栈

栈（Stack） 是一种遵循 LIFO（后进先出）原则的线性数据结构 —— 最后放进去的元素，最先被取出来，就像一叠碟子，只能从顶部操作。

核心操作只有三个：push（入栈）、pop（出栈）、peek（查看栈顶）。

在 JS 中，数组就可以当栈用。

栈在 JS 中的常见应用

• 函数调用栈：JS 会用调用栈记录函数的执行顺序，哪个函数最后被调用，就会最先执行完并弹出。

• 递归：每次递归调用都会进入调用栈，递归返回时再按后进先出的顺序逐层退出。

• 括号匹配：遇到左括号入栈，遇到右括号就和栈顶匹配，用来判断括号是否合法。

• 撤销/重做：把每一步操作压入栈中，撤销时弹出最近一次操作，重做时再放回另一个栈。

• 深度优先搜索 DFS：用栈保存待访问节点，每次取出最后加入的节点继续向深处遍历。

• 表达式求值：用栈保存数字和运算符，按照优先级逐步计算表达式结果。

• 浏览器前进/后退：可以用两个栈分别保存后退历史和前进历史，实现页面切换。

栈的代码实现

function Stack() {
  this.dataStore = []; // 保存栈内元素
  this.top = 0; // 标记可以插入新元素的位置，栈内压入元素该变量变大，弹出元素该变量变小
  this.push = push; // 入栈操作
  this.pop = pop; // 出栈操作
  this.peek = peek; // 返回栈顶元素
  this.clear = clear; // 清空栈
  this.length = length; // 栈的长度
  this.isEmpty = isEmpty; // 判断栈是否为空
}

// 向栈中压入元素，同时让指针 top+1，一定注意++
function push(element) {
  this.dataStore[this.top++] = element;
  // this.dataStore.push(element);
}

// 出栈操作，同时将 top-1
function pop() {
  return this.dataStore[--this.top];
  // return this.dataStore.pop();
}

// 返回栈顶元素，top-1，返回不删除
function peek() {
  return this.dataStore[this.top - 1];
  // return this.dataStore[this.dataStore.length - 1];
}

// 返回栈内元素个数
function length() {
  return this.top;
  // return this.dataStore.length;
}

// 清空栈
function clear() {
  this.top = 0;
  // this.dataStore = [];
}

// 判断栈是否为空
function isEmpty() {
  return this.top === 0;
  // return this.dataStore.length === 0;
}

var stack = new Stack();
stack.push(1);
stack.push(2);
console.log("栈的长度：", stack.length());
console.log("栈顶元素：", stack.peek());
console.log("出栈元素：", stack.pop());
console.log("栈顶元素：", stack.peek());

用两个栈实现队列

题目地址 (opens new window)

入队始终操作 stack1，出队和获取头节点始终操作 stack2。

function StackQueue() {
  var stack1 = new Stack(); //负责添加元素
  var stack2 = new Stack(); //负责删除元素

  // 入队
  this.enqueue = function(item) {
    stack1.push(item);
  };

  // 队头元素
  this.head = function() {
    if (stack1.isEmpty() && stack2.isEmpty()) {
      return null;
    }
    while (stack2.isEmpty()) {
      while (!stack1.isEmpty()) {
        stack2.push(stack1.pop());
      }
    }
    return stack2.peek();
  };

  // 队列大小
  this.size = function() {
    if (!stack1.isEmpty()) {
      return stack1.length();
    } else {
      if (!stack2.isEmpty()) {
        return stack2.length();
      } else {
        return 0;
      }
    }
  };

  // 出队
  this.dequeue = function() {
    if (stack1.isEmpty() && stack2.isEmpty()) {
      return null;
    }
    while (stack2.isEmpty()) {
      while (!stack1.isEmpty()) {
        stack2.push(stack1.pop());
      }
    }
    return stack2.pop();
  };
}

var sQueue = new StackQueue();
sQueue.enqueue(1);
sQueue.enqueue(2);
sQueue.enqueue(3);
console.log(sQueue.head()); // 1
console.log(sQueue.dequeue()); // 1
console.log(sQueue.head()); // 2
console.log(sQueue.size()); // 2
console.log(sQueue.dequeue()); // 2
console.log(sQueue.dequeue()); // 3
console.log(sQueue.size()); // 0

验证回文串

题目地址 (opens new window)

var isPalindrome = function(s) {
  s = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    stack.push(s[i]);
  }
  let reverse = "";
  while (stack.length) {
    reverse += stack.pop();
  }
  return reverse === s;
};

判断括号是否合法 ✅

题目地址 (opens new window)

// 时间和空间复杂度都是 O(n)
var isValid = function(s) {
  if (s.length % 2 !== 0) return false;
  const stack = [];
  for (const c of s) {
    switch (c) {
      case "(":
      case "{":
      case "[":
        stack.push(c);
        break;
      case ")":
        if (stack.pop() !== "(") return false;
        break;
      case "}":
        if (stack.pop() !== "{") return false;
        break;
      case "]":
        if (stack.pop() !== "[") return false;
    }
  }
  return stack.length === 0;
};

// 时间和空间复杂度都是 O(n)
var isValid = function(s) {
  if (s.length % 2 !== 0) return false;
  const stack = [];
  const bracket = {
    "(": ")",
    "{": "}",
    "[": "]"
  };
  for (const c of s) {
    if (c in bracket) {
      stack.push(c);
    } else if (stack.length === 0 || bracket[stack.pop()] !== c) {
      return false;
    }
  }
  return stack.length === 0;
};

最长有效括号

题目地址 (opens new window)

var longestValidParentheses = function(s) {
  let res = 0;
  const stack = [-1];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(i); // 左括号的索引入栈
      continue; // 跳过，考察下一个符号
    }
    stack.pop(); // 遇到右括号，栈顶出栈
    if (!stack.length) {
      stack.push(i); // 如果栈顶因此为空，说明该更换栈顶索引了
    } else {
      res = Math.max(res, i - stack[stack.length - 1]); // 比较获取最大的有效长度
    }
  }
  return res;
};

计算后缀表达式（逆波兰表达式）

function calc_exp(exp) {
  var stack = new Stack();
  for (var i = 0; i < exp.length; i++) {
    var item = exp[i];
    if (["+", "-", "*", "/"].indexOf(item) >= 0) {
      // 从栈顶弹出两个元素
      var value1 = stack.pop();
      var value2 = stack.pop();
      // 拼成表达式
      var exp_str = value2 + item + value1; // 第一次弹出的数放在运算符右边，第二次弹出的数放在运算符左边
      // 计算并取整
      var res = parseInt(eval(exp_str)); // eval() 函数可计算某个字符串，并执行其中的的 JavaScript 代码
      // 将计算结果压入栈
      stack.push(res.toString());
    } else {
      stack.push(item);
    }
  }
  // 若表达式正确，最终栈里应只有一个元素，这就是表达式的值
  return stack.pop();
}
var exp1 = ["4", "13", "5", "/", "+"]; // (4 + (13 / 5)) = 6
// var exp2 = ['10','6','9','3','+','-11','*','/','*','17','+','5','+'];  // ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22
console.log(calc_exp(exp1));
console.log(calc_exp(exp2));

十进制转二进制

function BinaryConversion(number) {
  var stack = new Stack();
  var remainder;
  var binary = ""; // 存储二进制
  while (number > 0) {
    remainder = number % 2; // 求模取余
    stack.push(remainder);
    number = Math.floor(number / 2); // 向下取整
  }
  while (!stack.isEmpty()) {
    binary += stack.pop();
  }
  return binary;
}
console.log(BinaryConversion(10)); // 1010