發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)之美-棧

在代碼的世界中蜀涨，無論是什么語言瞎嬉，棧其實都是一種非常重要的數(shù)據(jù)結(jié)構(gòu)。
全球聞名的代碼提問社區(qū)stack overflow就以棧（stack）溢出作為網(wǎng)站名的一個部分厚柳。
在寫代碼或者是debug的過程中氧枣，相信你已經(jīng)感受到了在函數(shù)調(diào)用棧的世界蹦蹦跳跳的快樂了。
在學(xué)校里刷oj别垮，刷LeetCode便监，進(jìn)入社會參加筆試面試的過程中，相信你也感受到了棧的強大和易用碳想。

這篇博文非常適合數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)非常薄弱的同學(xué)食用烧董，也歡迎基礎(chǔ)扎實的同學(xué)指正和交流。
如果從未感受過stack的美妙和強大胧奔，這篇博文將非常適合你~

什么是棧逊移？
- 數(shù)據(jù)結(jié)構(gòu)圖
- 入棧出棧圖
JavaScript中的Array與棧
- 在js中，如何發(fā)現(xiàn)出棧LIFO的特性龙填？
- 如何實現(xiàn)一個最小棧胳泉？
leetcode 棧解法題目
- 20.有效的括號（easy）
- 67.二進(jìn)制求和（easy）
- 905.按奇偶排序數(shù)組（easy）
- 56.合并區(qū)間（medium）
- 75.顏色分類（medium）
- 228.匯總區(qū)間（medium）
- 739.每日溫度（medium）
面試題棧解法題目
- 實現(xiàn)一個BigInt

什么是棧？

棧是一種后入先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)
棧通常使用DFS（Depth First Search）遍歷
通逞乙牛可以通過top/bottom來代表棧的頂部和底部

數(shù)據(jù)結(jié)構(gòu)圖

image

入棧出棧圖

image

JavaScript中的Array與棧

在js中扇商，如何發(fā)現(xiàn)出棧LIFO的特性？

下面這個結(jié)構(gòu)大家都熟悉宿礁，瞬間體現(xiàn)出棧LIFO的特性案铺。

// 定義一個棧
let stack = [1,2,3];
// 入棧
stack.push(4); // stack [1,2,3,4]
// 出棧
stack.pop(); // 4 stack [1,2,3]

如何實現(xiàn)一個最小棧？

設(shè)計一個支持 push 梆靖，pop 控汉，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧返吻。

push(x) —— 將元素 x 推入棧中暇番。
pop() —— 刪除棧頂?shù)脑亍?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/problems/min-stack/
解法：https://github.com/FrankKai/leetcode-js/blob/master/155.Min_Stack.js

leetcode 棧解法題目

20.有效的括號（easy）
67.二進(jìn)制求和（easy）
905.按奇偶排序數(shù)組（easy）
56.合并區(qū)間（medium）
75.顏色分類（medium）
228.匯總區(qū)間（medium）
739.每日溫度（medium）

20.有效的括號（easy）

題目：https://leetcode-cn.com/problems/valid-parentheses/
題解：https://github.com/FrankKai/leetcode-js/blob/master/20.Valid_Parentheses.js

/**
   * 解法2：棧
   * 1.構(gòu)建一個棧
   * 2.依次入棧所有開括號
   * 3.遇到閉括號時與棧頂?shù)拈_括號匹配
   *   3.1若匹配上壁酬，出棧并繼續(xù)
   *   3.2匹配不上，return false
   * 4.遍歷結(jié)束后的棧應(yīng)該為空，否則為無效括號
   */
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.二進(jìn)制求和（easy）

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    /**
     * 解法2：棧
     * 時間復(fù)雜度：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.按奇偶排序數(shù)組（easy）

題目：https://leetcode-cn.com/problems/sort-array-by-parity/
題解：https://github.com/FrankKai/leetcode-js/blob/master/905.Sort_Array_By_Parity.js

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParity = function (A) {
  /**
   * 棧頭棧尾解法即可
   * 偶數(shù)棧底推入unshift
   * 奇數(shù)棧頂推入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.合并區(qū)間（medium）

題目：https://leetcode-cn.com/problems/merge-intervals/
題解：https://github.com/FrankKai/leetcode-js/blob/master/56.Merge_Intervals.js

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  /**
   * 解法1：排序 + 棧
   * 性能：88ms 36.3MB
   * 思路：
   * 推入?yún)^(qū)間 空棧 或者 arr[0]大于棧最后一個區(qū)間閉
   * 覆蓋重疊 arr[0]小于棧最后一個區(qū)間閉
   *  */
  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/problems/sort-colors/
題解：https://github.com/FrankKai/leetcode-js/blob/master/75.Sort_Colors.js

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.匯總區(qū)間（medium）

題目：https://leetcode-cn.com/problems/summary-ranges/
題解：https://github.com/FrankKai/leetcode-js/blob/master/228.Summary_Ranges.js

/**
 * @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/problems/daily-temperatures/
題解：https://github.com/FrankKai/leetcode-js/blob/master/739.Daily_Temperatures.js

  /**
   * 解法2：棧 + 遞歸 1132ms 19.96% 59.2MB 11.76%
   * 思路：
   * 1.通過shift取出棧底元素
   * 2.遍歷剩余溫度棧內(nèi)溫度
   *     若溫度出現(xiàn)比棧底溫度大者
   *         存儲i+1
   *         遞歸進(jìn)行下一次入棧
   *     若溫度小于等于棧底溫度
   *         若遍歷到最后一個都沒有出現(xiàn)更大的
   *              存儲 0
   *              進(jìn)行下一次入棧
   * 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;
}

面試題棧解法題目

實現(xiàn)一個BigInt

實現(xiàn)大整數(shù)相加舆乔，大于 Number.MAX_VALUE岳服，不能直接使用 BigInt。

/**
* 請通過代碼實現(xiàn)大整數(shù)（可能比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("");
};

期待和大家交流希俩，共同進(jìn)步吊宋，歡迎大家加入我創(chuàng)建的與前端開發(fā)密切相關(guān)的技術(shù)討論小組：

微信公眾號：生活在瀏覽器里的我們 / excellent_developers

Github博客: 趁你還年輕233的個人博客

SegmentFault專欄：趁你還年輕，做個優(yōu)秀的前端工程師

Leetcode討論微信群：Z2Fva2FpMjAxMDA4MDE=（加我微信拉你進(jìn)群）

image

努力成為優(yōu)秀前端工程師颜武！

發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)之美-棧

什么是棧？

數(shù)據(jù)結(jié)構(gòu)圖

入棧出棧圖

JavaScript中的Array與棧

在js中扇商，如何發(fā)現(xiàn)出棧LIFO的特性？

如何實現(xiàn)一個最小棧？

leetcode 棧 解法題目

20.有效的括號（easy）

67.二進(jìn)制求和（easy）

905.按奇偶排序數(shù)組（easy）

56.合并區(qū)間（medium）

75. 顏色分類（medium）

228.匯總區(qū)間（medium）

739.每日溫度（medium）

面試題 棧 解法題目

實現(xiàn)一個BigInt

leetcode 棧解法題目

面試題棧解法題目