Aloha～！我是少女人妻 Uerica！有天地方角头米饭，蒸笼帮的包子、馒头、肉粽起了争执，米饭米口众多出手又凶狠，很快打得包子馒头满地找牙，害怕的肉粽被逼到角落，立刻将衣服扒开说：我是卧底！

好的～终於来到第 8 天了，今天要来聊一下资料结构中常见的堆叠了！

堆叠 (Stack)

堆叠是一种由下往上的储存资料，且只能从最新的资料开始存取。可以想像如同堆放在桌上的文件，先放的会在最下方，最新的在最上方，而拿取时也只能从最上方开始操作。

堆叠图

堆叠的定义与特性

像这样的资料存取方式，又称「後进先出」(LIFO, Last-in-First-out)，或「先进後出」(FILO, First-in-Last-out)。这样的好处是能确保存取的资料都是维持在最新的状态，但因资料存取都只能从最新的元素开始操作，所以若要存取较旧的元素就需要将上方元素一个个取出才行。

• 优点
  • 保持存取资料都是最新的
  • 新增资料快速
• 缺点
  • 插入或删除费时
  • 越接近第一笔资料越难取得

常见的基本操作

push：将最新的元素推入资料结构中。

pop：将最新加入的元素移出资料结构。

peek：在不将资料推出堆叠的情况下得知最新的资料元素。

size: 回传堆叠里的资料元素数量 (资料长度)

来！实作

一般的程序语言都有提供内建的堆叠 (Stack)，但 JavaScript 没有，不过在阵列中有些雷同的特性，所以就直接用 JavaScript 阵列与阵列提供的方法来实作看看吧！

//建构一个 Stack 类别，并将其储存的资料 elements 的型态宣告为阵列。
class Stack {
    
    constructor () {
        this.elements = [];
    }

    //使用 JavaScript Array 提供的方法 push()
    push(element) {
        this.elements.push(element);
    }

    //使用 JavaScript Array 提供的方法 pop()
    //如果堆叠内是空的回传 "没有资料元素"
    pop() { 
        if(this.elements.length === 0) return "没有资料元素"; 
        else return this.elements.pop();
    }

    //在不取出的情况下，得知最新资料元素的值。
    //一样使用阵列特性取最後一个的索引值。
    peek() {
        return this.elements [ this.elements.length - 1 ];
    }

    //使用阵列提供的 length 属性，来得知目前资料的长度
    size() {
        return this.elements.length;
    }
}

建立实体，来将文字反转吧

function reverse(str){

     // 创建一个 stack，并宣告一个空字串
     let stack = new Stack();
     let reversedStr = "";
     let i = 0;  

     //利用 while 回圈将所有字元依序推入堆叠中
     while (i !== str.length) {
         stack.push(str.charAt(i));
         i++;
     }
   
     //用回圈一个个取出再存入字串中
     while (stack.size() !== 0) {
         reversedStr += stack.pop();
     }  

     //回传反转後的字串.
     return reversedStr;
}

console.log(reverse('aholA')) //Aloha

关於堆叠的时间复杂度

由於堆叠的 push 或 pop 都是从最新资料推入或取出，此部分的时间复杂度是 O(1)，但若是有搬移资料元素，或删除某一资料元素的话，时间复杂度是 O(n)

参考资料：

用 JavaScript 学习资料结构和演算法：堆叠（Stack）篇
JavaScript 学演算法（六）- 堆叠 ＆ 伫列
基本资料结构
Reverse a String with a Stack in JavaScript

感谢阅读！今天就先到这边啦～话说肉粽虽然逃过一劫，但他家人硷粽可就没这麽幸运了～明天见！掰掰～