什么是棧？

棧（stack）又名堆棧，它是一種運(yùn)算受限的線(xiàn)性表。限定僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表。這一端被稱(chēng)為棧頂，相對(duì)地，把另一端稱(chēng)為棧底。向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱(chēng)作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。

顯示生活中也能發(fā)現(xiàn)很多棧的例子，如書(shū)本的堆放和取出，疊盤(pán)子等。棧也被用在編程語(yǔ)言的編譯器和內(nèi)存中保存變量、方法調(diào)用等。JavaScript的基本類(lèi)型變量就保存在棧中。在計(jì)算機(jī)中，棧運(yùn)用的經(jīng)典例子就是保存歷史記錄，例如Ctrl+Z這種撤回操作的實(shí)現(xiàn)。

JavaScript實(shí)現(xiàn)棧

棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，我們最容易想到的就是JS中數(shù)組的push、pop操作。用數(shù)組保存棧結(jié)構(gòu)，這是一種最簡(jiǎn)便的實(shí)現(xiàn)形式。另外一種就是使用對(duì)象和指針保存棧結(jié)構(gòu)的形式。兩者的區(qū)別是，用數(shù)組存儲(chǔ)棧元素，在處理大量數(shù)據(jù)的時(shí)候，需要迭代整個(gè)數(shù)組，大部分方法的時(shí)間復(fù)雜度是O(n)，而采用對(duì)象的形式能直接通過(guò)屬性獲取元素。
接來(lái)下我們分別實(shí)現(xiàn)兩種方法，主要實(shí)現(xiàn)棧的以下幾個(gè)主要功能：

1. push（element）: 添加元素到棧頂。
2. pop（）：移除棧頂元素，同時(shí)返回被修改的元素。
3. peek（）：返回棧頂元素，不對(duì)棧做任何修改。
4. isEmpty（）：檢查棧是否為空，返回一個(gè)Boolean值。
5. clear（）：清空棧元素。
6. size（）：返回棧里元素的個(gè)數(shù)。

數(shù)組存儲(chǔ)實(shí)現(xiàn)

    class StackByArray {
      constructor() {
        this.items = [];
      }
      push(element){
        this.items.push(element);
      }
      pop(){
        return this.items.pop();
      }
      peek(){
        return this.items[this.items.length-1];
      }
      isEmpty(){
        return this.items.length === 0;
      }
      clear(){
        this.items = []
      }
      size(){
        return this.items.length;
      }
    }

對(duì)象存儲(chǔ)實(shí)現(xiàn)

    class StackByObject {
      constructor() {
        this.count = 0;
        this.items = {};
      }
      push(element) {
        this.items[this.count] = element;
        this.count++;
      }
      pop() {
        // 先判空，確定對(duì)象內(nèi)是否還有該屬性值
        if (this.isEmpty()) {
          return undefined;
        }
        this.count--;
        const result = this.items[this.count];
        delete this.items[this.count];
        return result;
      }
      peek() {
        return this.items[this.count - 1];
      }
      isEmpty() {
        return this.count === 0;
      }
      clear() {
        this.count = 0;
        this.items = {};
      }
      size() {
        return this.count;
      }
      // 需要手動(dòng)實(shí)現(xiàn)toString打印
      toString(){
        if(this.isEmpty()){
          return '';
        }
        let s = `${this.items[0]}`;
        for(let i = 1;i< this.count;i++){
          s += `,${this.items[i]}`;
        }
        return s;
      }
    }