AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

发现数据结构之美-栈

2022-06-08 140
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 在代码的世界中，无论是什么语言，栈其实都是一种非常重要的数据结构。

image.png


全球闻名的代码提问社区stack overflow就以栈（stack）溢出作为网站名的一个部分。在写代码或者是debug的过程中，相信你已经感受到了在函数调用栈的世界蹦蹦跳跳的快乐了。在学校里刷oj，刷LeetCode，进入社会参加笔试面试的过程中，相信你也感受到了栈的强大和易用。

这篇博文非常适合数据结构基础非常薄弱的同学食用，也欢迎基础扎实的同学指正和交流。

如果从未感受过stack的美妙和强大，这篇博文将非常适合你~

  • 什么是栈？
  • 数据结构图
  • 入栈出栈图
  • JavaScript中的栈
  • 在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来代表栈的顶部和底部


数据结构图


image.png

入栈出栈图


image.png

JavaScript中的栈

在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...


图解函数调用栈

image.png

从frames stack中调用函数。


function foo(){
    let a = 10;
    return a + b + 11
}
function bar(x){
    let y = 3;
    return foo(x*y);
}
console.log(bar(7)); // 返回42


过程拆解：


  • 调用bar时，包含bar的arguments和本地变量的第一个frame创建了
  • 当bar调用foo时，包含了foo的arguments和本地变量的第二个frame创建成功，并且将其推入顶部
  • 当foo返回时，顶部的frame element会从stack中pop出来（留下bar在栈中）
  • 当bar返回时，stack清空


可视化拆解：


image.png


image.png


image.png


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 here
var 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("");
};



文章标签：
JavaScript
前端开发
数据可视化
关键词：
数据结构栈
趁你还年轻233
目录
相关文章
ephemerals__
|
14天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
那年春天
|
5天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
14 1
德国都芳最好
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
46 21
html的七十二变
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
24 2
dufadayang
|
12天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
40 4
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
28 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
肾透侧视攻城狮
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
17 1
禁默
|
1月前
初步认识栈和队列
初步认识栈和队列
禁默
58 10
星霜旅人
|
30天前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
17 1
java冯坚持
|
1月前
|
算法
数据结构与算法二：栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用，并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
java冯坚持
43 3