定义

栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。

模拟实现

  1. class Stack{
  2.     constructor(){
  3.     this.stack = [];
  4.     this.top = 0;
  5.     this.max=10000;
  6.   };
  7.   // 入栈
  8.   push(item){
  9.     if(this.top<this.max){
  10.       this.top++;
  11.         this.stack.push(item);
  12.     }else{
  13.         consle.error('栈溢出')
  14.     }
  15.   }
  16.   // 出栈
  17.   pop(){
  18.     if(this.top > 0) {
  19.       let x = this.stack.pop();
  20.       this.top--;
  21.       return x;
  22.     }else{
  23.         console.log('栈已经为空')
  24.     }
  25.   }
  26.   // 判断栈是否为空
  27.   empty(){
  28.       return this.top === 0;
  29.   }
  30.   // 返回位于栈顶的元素
  31.   peek(){
  32.       return this.stack[this.top];
  33.   }
  34.   // 栈的大小
  35.   size(){
  36.       return this.top;
  37.   }
  38. }

常见应用

进制转换

利用栈将转化数字的进制，假设将数字n转换为以b为基数的数字，方法如下:

  1. 最高位为n % b，将此位压入栈
  2. 使用Math.floor(n/b)代替n
  3. 重复步骤1和2，直到n等于0，且没有余数

  4. 持续将栈内元素弹出，直到栈为空

    1.  function mulBase(num, base){
    2. var stack = new Stack();
    3. do {
    4.    stack.push(num % base);
    5.    num = Math.floor(num /= base)
    6. } while(num > 0)
    7. var str = '';
    8. while(stack.length() > 0){
    9.     str += stack.pop();
    10. }
    11. return str
    12. }

    回文判断

    利用栈，可以轻松判断一个字符串是否是回文(回文指一个字符串从前往后写和从后往前写都一样)

    1. function isPalindrome(word){
    2.     var stack = new Stack();
    3.     for(var i = 0, len = word.length; i++){
    4.         stack.push(word[i]);
    5.     }
    6.     var rword = '';
    7.     while(stack.length() > 0){
    8.         rword += stack.pop();
    9.     }
    10.     return rword == word;
    11. }

    当然正常我们直接使用

    1. var arr = Array.prototype.slice.call(word);
    2. return arr.reverse().join('') == word

    实现特殊栈

    实现一个特殊的栈，有栈的正常方法，能返回栈里的最小值。要求时间复杂度为O(1)
    思路：创建两个栈，一个栈 data 放正常的数据。另一个栈 mins 放当前数据中的最小值。例如：若新添加的数据小于当前的最小值，两个栈都添加新的数据。若新添加的数据大于当前栈中的最小值，mins 仍然添加当前最小值。
    而且，data出数据的时候，mins同时出栈。

    常见的算法

    有效的括号

    leetCode 20:给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
    有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

    1. var isValid = function(s) {
    2. let map = {
    3.  '(': -1,
    4.  ')': 1,
    5.  '[': -2,
    6.  ']': 2,
    7.  '{': -3,
    8.  '}': 3
    9. }
    10. let stack = []
    12. for (let i = 0; i < s.length; i++) {
    13.  if (map[s[i]] < 0) {
    14.    stack.push(s[i])
    15.  } else {
    16.    let last = stack.pop()
    17.    if (map[last] + map[s[i]] != 0) return false
    18.  }
    19. }
    20. if (stack.length > 0) return false
    21. return true
    22. }

    每日温度

    LeetCode 739: 根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
    例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

    1. const dailyTemperatures = function(T) {
    2.  const len = T.length // 缓存数组的长度 
    3.  const stack = [] // 初始化一个栈   
    4.  const res = (new Array(len)).fill(0) //  初始化结果数组，注意数组定长，占位为0
    5.  for(let i=0;i<len;i++) {
    6.    // 若栈不为0，且存在打破递减趋势的温度值
    7.    while(stack.length && T[i] > T[stack[stack.length-1]]) {
    8.      // 将栈顶温度值对应的索引出栈
    9.      const top = stack.pop()  
    10.      // 计算 当前栈顶温度值与第一个高于它的温度值 的索引差值
    11.      res[top] = i - top 
    12.    }
    13.    // 注意栈里存的不是温度值，而是索引值，这是为了后面方便计算
    14.    stack.push(i)
    15.  }
    16.  // 返回结果数组
    17.  return res 
    18. };

    图解链接： https://mp.weixin.qq.com/s/3kDSOHyd-qOw7apzj0Z9YQ

其他

利用堆栈，还可以解决如下常见问题：

  • 求解算术表达式的结果（LeetCode 224、227、772、770)
  • 求解直方图里最大的矩形区域（LeetCode 84）


参考链接 https://github.com/lznbuild/my-blog/issues/26 https://mp.weixin.qq.com/s/3kDSOHyd-qOw7apzj0Z9YQ