• 什么是栈？

    • 数据结构图
    • 入栈出栈图

  • JavaScript中的Array与栈

    • 在js中，如何发现出栈LIFO的特性？
    • 如何实现一个最小栈？

  • leetcode 栈 解法题目

    • 20.有效的括号（easy）
    • 67.二进制求和（easy）
    • 905.按奇偶排序数组（easy）
    • 56.合并区间（medium）
    • 75.颜色分类（medium）
    • 228.汇总区间（medium）
    • 739.每日温度（medium）

  • 面试题 栈 解法题目

    • 实现一个BigInt

什么是栈？

  • 栈是一种后入先出（LIFO）的数据结构
  • 栈通常使用DFS（Depth First Search）遍历
  • 通常可以通过top/bottom来代表栈的顶部和底部

数据结构图

入栈出栈图

JavaScript中的Array与栈

在js中，如何发现出栈LIFO的特性？

下面这个结构大家都熟悉，瞬间体现出栈LIFO的特性。

// 定义一个栈let stack = [1,2,3];// 入栈stack.push(4); // stack [1,2,3,4]// 出栈stack.pop(); // 4 stack [1,2,3]

如何实现一个最小栈？

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

push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。
var MinStack = function() {  this.stack = [];};MinStack.prototype.push = function(x) {  this.stack.push(x);};MinStack.prototype.pop = function() {  return this.stack.pop();};MinStack.prototype.top = function() {  return this.stack[this.stack.length - 1];};MinStack.prototype.getMin = function() {  return Math.min(...this.stack);};

题目：https://leetcode-cn.com/probl...
解法：https://github.com/FrankKai/l...

leetcode 栈 解法题目

  • 20.有效的括号（easy）
  • 67.二进制求和（easy）
  • 905.按奇偶排序数组（easy）
  • 56.合并区间（medium）
  • 75.颜色分类（medium）
  • 228.汇总区间（medium）
  • 739.每日温度（medium）

20.有效的括号（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

/**   * 解法2：栈   * 1.构建一个栈   * 2.依次入栈所有开括号   * 3.遇到闭括号时与栈顶的开括号匹配   *   3.1若匹配上，出栈并继续   *   3.2匹配不上，return false   * 4.遍历结束后的栈应该为空，否则为无效括号   */var isValid = function(s) {  var bracketsMap = {    "(": ")",    "{": "}",    "[": "]"  };  var openBrackets = Object.keys(bracketsMap);  var closeBrackets = Object.values(bracketsMap);  var stack = [];  var sArr = s.split("");  for (var i = 0; i < sArr.length; i++) {    if (openBrackets.indexOf(sArr[i]) !== -1) {      stack.push(sArr[i]);    } else if (closeBrackets.indexOf(sArr[i]) !== -1) {      var top = stack[stack.length - 1];      if (sArr[i] === bracketsMap[top]) {        stack.pop();      } else {        return false;      }    }  }  return stack.length === 0;}

67.二进制求和（easy）

/** * @param {string} a * @param {string} b * @return {string} */var addBinary = function (a, b) {    /**     * 解法2：栈     * 时间复杂度：O(n)     * 性能：56ms, 35.5MB     */    let aArr = a.split("");    let bArr = b.split("");    let stack = [];    let count = 0;    while (aArr.length !== 0 || bArr.length !== 0) {        let aPop = aArr.pop() || 0;        let bPop = bArr.pop() || 0;        let stackBottom = 0;        if (stack.length > count) {            stackBottom = stack.shift() || 0;        }        let sum = parseInt(aPop) + parseInt(bPop) + parseInt(stackBottom)        if (sum <= 1) {            stack.unshift(sum);        } else {            stack.unshift(sum - 2);            stack.unshift(1);        }        count++;    }    return stack.join("");};

905.按奇偶排序数组（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

/** * @param {number[]} A * @return {number[]} */var sortArrayByParity = function (A) {  /**   * 栈头栈尾解法即可   * 偶数栈底推入unshift   * 奇数栈顶推入push   */  var stack = [];  for (var i = 0; i < A.length; i++) {    if (A[i] % 2 === 0) {      stack.unshift(A[i]);    } else {      stack.push(A[i]);    }  }  return stack;};

56.合并区间（medium）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

/** * @param {number[][]} intervals * @return {number[][]} */var merge = function (intervals) {  /**   * 解法1：排序 + 栈   * 性能：88ms 36.3MB   * 思路：   * 推入区间 空栈 或者 arr[0]大于栈最后一个区间闭   * 覆盖重叠 arr[0]小于栈最后一个区间闭   *  */  intervals.sort((a, b) => a[0] - b[0]);  let stack = [];  for (let i = 0; i < intervals.length; i++) {    let currrentInterval = intervals[i];    let stackLastItem = stack[stack.length - 1];    if (stack.length === 0 || currrentInterval[0] > stackLastItem[1]) {      stack.push(currrentInterval);    } else if (currrentInterval[0] <= stackLastItem[1]) {      stackLastItem[1] = Math.max(stackLastItem[1], currrentInterval[1]);    }  }  return stack;};

75. 颜色分类（medium）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

var sortColors = function (nums) {  /**   * 解法1：递归 栈   * 性能：64ms 35.1MB   */  var length = nums.length;  var countHead = arguments[1] || 0;  var countTail = arguments[2] || 0;  for (var i = countHead || 0; i < length - countTail; i++) {    if (nums[i] === 0) {      countHead++;      nums.unshift(nums.splice(i, 1)); // 增加if(i!==0)会降低10ms性能      return sortColors(nums, countHead, countTail);    } else if (nums[i] === 2) {      countTail++;      nums.push(nums.splice(i, 1));      return sortColors(nums, countHead, countTail);    }  }  return nums;}

228.汇总区间（medium）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

/** * @param {number[]} nums * @return {string[]} */var summaryRanges = function (nums) {  /**   * 解法1：排序 + 栈   * 性能：52ms 33.7MB   */  nums.sort((a, b) => a - b);  let stack = [];  let result = [];  for (let i = 0; i < nums.length; i++) {    if (stack.length === 0 || nums[i] - stack[stack.length - 1] === 1) {      stack.push(nums[i]);    } else {      stackToResult();      stack = [];      stack.push(nums[i]);    }    if (i === nums.length - 1) {      stackToResult();    }  }  function stackToResult() {    if (stack.length > 1) {      result.push(`${stack[0]}->${stack[stack.length - 1]}`);    } else {      result.push(`${stack[0]}`);    }  }  return result;};

739.每日温度（medium）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

  /**   * 解法2：栈 + 递归 1132ms 19.96% 59.2MB 11.76%   * 思路：   * 1.通过shift取出栈底元素   * 2.遍历剩余温度栈内温度   *     若温度出现比栈底温度大者   *         存储i+1   *         递归进行下一次入栈   *     若温度小于等于栈底温度   *         若遍历到最后一个都没有出现更大的   *              存储 0   *              进行下一次入栈   * 3.最后一个温度无论如何都肯定是0   */var dailyTemperatures = function(T) {  if (T.length < 1 || T.length > 30000) return false;  var result = arguments[1] || [];  var bottom = T.shift();  for (var i = 0; i < T.length; i++) {    var t = T[i];    if (t > bottom) {      result.push(i + 1);      return dailyTemperatures(T, result);    } else {      if (i === T.length - 1) {        result.push(0);        return dailyTemperatures(T, result);      }    }  }  result.push(0);  return result;}

面试题 栈 解法题目

实现一个BigInt

实现大整数相加，大于 Number.MAX_VALUE，不能直接使用 BigInt。

/*** 请通过代码实现大整数（可能比Number.MAX_VALUE大）相加运算// your code goes herevar bigint1 = new BigInt('1231230');var bigint2 = new BigInt('12323123999999999999999999999999999999999999999999999991');console.log(bigint1.plus(bigint2))*/
function BigInt(value) {  this.value = value;}BigInt.prototype.plus = function (bigint) {  let aArr = this.value.split("");  let bArr = bigint.value.split("");  let stack = [];  let count = 0;  while (aArr.length !== 0 || bArr.length !== 0) {    let aPop = aArr.pop() || 0;    let bPop = bArr.pop() || 0;    let stackBottom = 0;    if (stack.length > count) {      stackBottom = stack.shift();    }    let sum = parseInt(aPop) + parseInt(bPop) + parseInt(stackBottom);    if (sum < 10) {      stack.unshift(sum);    } else if (sum >= 10) {      stack.unshift(sum - 10);      stack.unshift(1);    }    count++;  }  return stack.join("");};

期待和大家交流，共同进步，欢迎大家加入我创建的与前端开发密切相关的技术讨论小组：

  • 微信公众号： 生活在浏览器里的我们 / excellent_developers
  • Github博客: 趁你还年轻233的个人博客
  • SegmentFault专栏：趁你还年轻，做个优秀的前端工程师
  • Leetcode讨论微信群：Z2Fva2FpMjAxMDA4MDE=（加我微信拉你进群）

努力成为优秀前端工程师！