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

感謝閱讀！今天就先到這邊啦～話說肉粽雖然逃過一劫，但他家人鹼粽可就沒這麼幸運了～明天見！掰掰～