棧是一種數(shù)據(jù)的存儲(chǔ)方式，特點(diǎn)是后進(jìn)先出(Last In First Out), 就是只能在棧頂進(jìn)行操作。

stack.png

想一下我們往箱子里放書，只能一本一本的從最上面累加，拿的時(shí)候也是從最上面往外拿，只能一頭操作不能兩頭操作。

接下來，我們用數(shù)組來實(shí)現(xiàn)棧的功能，主要的方法有：

• push: 添加元素到棧頂
• pop: 彈出棧頂元素
• top: 返回棧頂元素
• isEmpty: 判斷棧是否為空
• size：返回棧里的元素個(gè)數(shù)
• clear：清空棧

function Stack () {
    let items = []; // 存儲(chǔ)數(shù)據(jù)
    
    // 從棧頂添加元素，也叫壓棧
    this.push = function (item) {
        items.push(item);
    }
    
    // 彈出棧頂元素
    this.pop = function () {
        return items.pop();
    }
    
    // 返回棧頂元素
    this.top = function () {
        return items[items.length - 1];
    }
    
    // 判斷棧是否為空
    this.isEmpty = function () {
        return items.length === 0;
    }
    
    // 返回棧的大小
    this.size = function () {
        return items.length;
    }
    
    // 清空棧
    this.clear = function () {
        items = [];
    }
}

為啥items數(shù)組沒有掛在this上呢？

items是作為私有變量存在的，如果掛在this上面，實(shí)例就可以訪問到，就能根據(jù)下標(biāo)去操作數(shù)組，就不符合先進(jìn)后出了。所以只能調(diào)用方法去操作。

下面通過幾個(gè)例子，來感受一下通過棧的方式來思考問題

例一:
判斷是否是合法的括號(hào)（成對出現(xiàn)）

as()sfrg(dfg)
(sf(dfdg))
()()))

思路分析：for循環(huán)遍歷字符串

• 遇到左括號(hào)入棧
• 遇到右括號(hào)，如果棧中有元素，棧頂元素出棧；如果棧為空，說明沒有對應(yīng)的左括號(hào)，結(jié)束循環(huán)，返回false。
• 遍歷完之后查看棧是否為空，是的話說明括號(hào)都一一抵消掉了，是合法的返回true；否的話說明缺少對應(yīng)的左括號(hào)，是不合法的返回false。

function isLegalBrackets(str) {
    const stack = new Stack();
    for(let i = 0; i < str.length; i++) {
        const item = str[i];
        // 遇到做括號(hào)入棧
        if (item === '(') {
            stack.push(item);
        } else if (item === ')') {
           // 遇到右括號(hào)，判斷棧是否為空
            if (stack.isEmpty()) {
                return false;
            } else { // 彈出左括號(hào)
                stack.pop();
            }
        }
    }

    // 如果棧為空，說明字符串括號(hào)合法
    return stack.isEmpty();
}

例二：中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

中綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算對象的中間：

1 + 2、1+2+3

后綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算對象的后面：

1 2 +、1 2 3 + +

后綴表達(dá)式的優(yōu)點(diǎn)：計(jì)算機(jī)運(yùn)算特別方便，嚴(yán)格從左向右進(jìn)行，不需要考慮運(yùn)算符的優(yōu)先，也沒有括號(hào)了。

思路分析：
后綴表達(dá)式重要的就是運(yùn)算符的存放位置，運(yùn)算數(shù)的順序就是從左到右依次存放。我們定義一個(gè)數(shù)組和棧，數(shù)組存放后綴表達(dá)式，棧存放運(yùn)算符和括號(hào)，在合適的時(shí)候出棧存入數(shù)組。

循環(huán)中綴表達(dá)式數(shù)組

• 遇到運(yùn)算數(shù)存入數(shù)組
• 遇到左括號(hào)入棧
• 遇到運(yùn)算數(shù)，如果棧為空或者當(dāng)前運(yùn)算符的優(yōu)先級大于棧頂元素的優(yōu)先級，或者棧頂元素是左括號(hào)，入棧
• 如果當(dāng)前運(yùn)算符的優(yōu)先級小于等于棧頂元素的優(yōu)先級，彈出棧頂元素存到數(shù)組中，直到?jīng)]有棧頂元素優(yōu)先級大于當(dāng)前運(yùn)算符的優(yōu)先級為止。最后把當(dāng)前運(yùn)算符入棧
• 如果是右括號(hào)，彈出棧頂元素直到遇到左括號(hào)為止。并且彈出左括號(hào)
• 循環(huán)結(jié)束后，如果棧中還有元素，依次彈出存到數(shù)組中。

這篇文章過程分析描述的挺詳細(xì)的

const priorityMap = { '+': 1, '-': 1, '*':2, '/': 2 }; // 定義運(yùn)算符優(yōu)先級
function infixExpToPostfixExp (exp) {
  const postfixArr = []; // 存儲(chǔ)后綴表達(dá)式
  const stack = new Stack();

  for(let i = 0; i < exp.length; i++) {
    const item = exp[i];

    if (!isNaN(item)) { // 是數(shù)字直接存進(jìn)數(shù)組
      postfixArr.push(item);
    } else if (stack.isEmpty() || priorityMap[item] > priorityMap[stack.top()] || item === '(' || stack.top() === '(') { // 棧為空 || 當(dāng)前元素優(yōu)先級大于棧頂元素優(yōu)先級 || 當(dāng)前元素是左括號(hào) || 棧頂是左括號(hào)，直接入棧
      stack.push(item);
    } else if (item === ')') { // 遇到右括號(hào)
      while(stack.top() !== '(') { // 把左括號(hào)前的運(yùn)算符全部出棧存到數(shù)組中
        const top = stack.pop();
        postfixArr.push(top);
      }
      stack.pop(); // 左括號(hào)出棧
    } else if (priorityMap[item] <= priorityMap[stack.top()]) { // 當(dāng)前元素優(yōu)先級小于棧頂元素優(yōu)先級
      while(priorityMap[item] <= priorityMap[stack.top()]) { // 把比當(dāng)前元素優(yōu)先級大的運(yùn)算符全部出棧存進(jìn)數(shù)組
        const top = stack.pop();
        postfixArr.push(top);
      }
      stack.push(item); // 當(dāng)前運(yùn)算符入棧
    }
  }
  while(!stack.isEmpty()) { // 如果最后棧中還有元素，全部出棧存進(jìn)數(shù)組
    postfixArr.push(stack.pop());
  }

  return postfixArr;
}

// var exp = ["(","1","+","(","4","+","5","+","3",")","-","3",")","+","(","9","+","8",")"];
// console.log(infixExpToPostfixExp(exp))

例三. 計(jì)算逆波蘭表達(dá)式

逆波蘭表達(dá)式也就是后綴表達(dá)式，例如：["4", "13", "5", "/", "+"]，它的計(jì)算方式就是遇到'/'時(shí)，把13和5拿出來進(jìn)行除法運(yùn)算，然后把13、5、/三個(gè)元素刪除，把運(yùn)算結(jié)果放進(jìn)去，遇到‘+’, 把前兩個(gè)運(yùn)算數(shù)拿出來進(jìn)行加法運(yùn)算，最后的結(jié)果也就是后綴表達(dá)式的結(jié)果。

用棧怎么實(shí)現(xiàn)呢？循環(huán)遍歷數(shù)組

• 遇到操作數(shù)，入棧
• 遇到運(yùn)算符，依次從棧頂彈出兩個(gè)元素，和當(dāng)前運(yùn)算符進(jìn)行運(yùn)算
• 把運(yùn)算結(jié)果入棧
• 遍歷結(jié)束后，棧里只有一個(gè)元素，這個(gè)元素就是最后的計(jì)算結(jié)果

function calcExp (exp) {
  const stack = new Stack();
  for (let i = 0; i < exp.length; i++) {
    const item = exp[i];
    if (['+', '-', '*', '/'].includes(item)) {
      const value1 = stack.pop();
      const value2 = stack.pop();

      const expStr = value2 + item + value1;
      // 計(jì)算并取整
      const res = parseInt(eval(expStr));
      // 計(jì)算結(jié)果壓入棧中（注意轉(zhuǎn)成字符串）
      stack.push(res.toString());
    } else {
      stack.push(item);
    }
  }
  return stack.pop();
}

3. 實(shí)現(xiàn)一個(gè)有min方法的棧

實(shí)現(xiàn)一個(gè)棧，除了常見的push，pop方法以外，提供一個(gè)min方法，返回棧里最小的元素，且時(shí)間復(fù)雜度為o(1)

思路分析：

1. 用兩個(gè)棧來存儲(chǔ)數(shù)據(jù)，一個(gè)是常規(guī)棧（dataStack），正常存儲(chǔ)數(shù)據(jù)，另一個(gè)專門用來存儲(chǔ)最小值(minStack)。兩個(gè)棧的元素個(gè)數(shù)要一致，如果最小值棧只存儲(chǔ)當(dāng)前的最小值（只有一個(gè)元素）， pop()操作之后再求最小值就不行了
2. 編程思想里有一個(gè)分而治之的思想，就是分開想，分開處理?？紤]dataStack的時(shí)候，就別管min方法，它就是一個(gè)普通的棧，正常處理就行

考慮minStack的時(shí)候，就別管dataStack了，它是專門為min方法而存在的棧。如果minStack為空，push進(jìn)來的數(shù)據(jù)一定是最小的，直接入棧；如果不為空，跟棧頂元素比較，比棧頂元素小也入棧。如果比棧頂元素大，為了保證和常規(guī)棧的長度一樣，把棧頂元素再次入棧

function MinStack () {
  var dataStack = new Stack(); // 普通的棧
  var minStack = new Stack(); // 存儲(chǔ)最小值的棧

  this.push = function (item) {
    dataStack.push(item); // 普通棧正常壓棧

    if (minStack.isEmpty() || item < minStack.top()) { // 如果最小值棧為空或者將要壓入的值比棧頂元素小，入棧
      minStack.push(item);
    } else { // 否則就把棧頂元素再一次入棧（minStack要和dataStack的元素個(gè)數(shù)保持一致）
      minStack.push(minStack.top())
    }
  };
 
  this.pop = function () { // 兩個(gè)棧都彈出
    minStack.pop();
    return dataStackk.pop();
  }

  this.min = function () { // 直接取棧頂元素
    return minStack.top();
  }
}

有些問題用數(shù)組的方式來實(shí)現(xiàn)很難，但是用棧來思考就會(huì)發(fā)現(xiàn)別有洞天。這也是看了張老師的視頻講解之后做了一下筆記，方便日后查閱。