iT邦幫忙

2021 iThome 鐵人賽

DAY 8
1
Software Development

少女人妻在廚房裡想不通的演算法系列 第 8

【在廚房想30天的演算法】Day 08 資料結構:堆疊 Stack

Aloha~!我是少女人妻 Uerica!有天地方角頭米飯,蒸籠幫的包子、饅頭、肉粽起了爭執,米飯米口眾多出手又兇狠,很快打得包子饅頭滿地找牙,害怕的肉粽被逼到角落,立刻將衣服扒開說:我是臥底!


好的~終於來到第 8 天了,今天要來聊一下資料結構中常見的堆疊了!

堆疊 (Stack)

堆疊是一種由下往上的儲存資料,且只能從最新的資料開始存取。可以想像如同堆放在桌上的文件,先放的會在最下方,最新的在最上方,而拿取時也只能從最上方開始操作。

堆疊圖

堆疊的定義與特性

像這樣的資料存取方式,又稱「後進先出」(LIFO, Last-in-First-out),或「先進後出」(FILO, First-in-Last-out)。這樣的好處是能確保存取的資料都是維持在最新的狀態,但因資料存取都只能從最新的元素開始操作,所以若要存取較舊的元素就需要將上方元素一個個取出才行。

vyxQBKM

  • 優點
    • 保持存取資料都是最新的
    • 新增資料快速
  • 缺點
    • 插入或刪除費時
    • 越接近第一筆資料越難取得

常見的基本操作

push:將最新的元素推入資料結構中。

a6JVVuk

pop:將最新加入的元素移出資料結構。

T01emTq

peek:在不將資料推出堆疊的情況下得知最新的資料元素。

oj89PLs

size: 回傳堆疊裡的資料元素數量 (資料長度)

MJGYGrI

來!實作

一般的程式語言都有提供內建的堆疊 (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


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


上一篇
【在廚房想30天的演算法】Day 07 資料結構:陣列 Array
下一篇
【在廚房想30天的演算法】Day 09 資料結構:佇列 Queue
系列文
少女人妻在廚房裡想不通的演算法30

尚未有邦友留言

立即登入留言