資料結構筆記： Stack 堆疊

考量到文章長度，把資料結構的部分分拆成不同文章，雖然標題是演算法，其實內容介紹資料結構比較多。上課之前不太清楚演算法跟資料結構的關係，上課後有更深一步的感想，看到題目以後需要選擇用哪種資料結構解題，此資料結構又有哪些方法可以使用，才能夠將效率最大化。

Stack 堆疊

結構：

function Stack() {
  let items = []; // 我們這邊使用陣列 array 的方式來儲存堆疊內的元素
}

特性：
插入、刪除需時 O(1) 。搜尋需時 O(N) 。

方法：

• Push(data)：把資料放進Stack，O(1) 。
• Pop：把「最上面」的資料從Stack中移除，O(1) 。除了最上面的資料可以使用Top()來讀取，無法得知Stack裡面還有其餘哪些資料。要知道Stack裡的所有資料，只能靠Pop()，把資料一個一個拿出來檢查，O(n) 。
• Top：回傳「最上面」的資料，不影響資料結構本身，O(1) 。
• IsEmpty：確認Stack裡是否有資料，不影響資料結構本身 ，O(1) 。
• getSize：回傳Stack裡的資料個數，不影響資料結構本身，O(n)。

圖一

以圖一為例，一開始Stack是空的：

• 當Push(6)後，便把66放入Stack。並用一個稱為top的變數，記錄Stack最上面的資料為何，在此即為66。
• 當Push(3)、Push(7)後，便把3、73、7放入Stack。並更新top，使其記錄77。
• 當Pop()後，便把Stack中「最上面」的資料(77)給移除，所以Stack中剩下6、36、3，並更新top記錄33。
• 當Push(14)、Push(8)後，便把14、814、8放入Stack。並更新top，使其記錄88。
• 在以上的任何階段，只要Stack有資料，使用函式Top()會回傳變數top所記錄的資料。
• 在以上的任何階段，使用IsEmpty()便能判斷Stack裡是否有存放資料。
• 在以上的任何階段，使用getSize()會回傳Stack中的資料個數。

Stack的應用

Stack最主要的功能是「記得先前的資訊」，所以時常用來處理需要「回復到先前的狀態」的問題，也稱為Back-Tracking問題，例如：

• 編輯器(如word、sublime等等)中的undo。
• 網頁瀏覽器的「回到前一頁」功能。

LeetCode 題目

Maximum Binary Tree - LeetCode

答案：

var constructMaximumBinaryTree = function(nums) {
    if(nums.length == 0){
        //needed because the way this is coded doesn't check for nums length
        return null
    }
    
    if(nums.length == 1){
        // this is a base case for returning a node. Eventually your tree will go down to a single node, so you return it to construct the entire tree.
        return new TreeNode(nums[0])
    }
    
    
    // the main idea here is to get the maxIndex and value of the given array, construct a tree node from it, and then construct a tree by slicing left of the max value and right of the max value.
    let maxIndex = getMaxIndex(nums)
    let maxVal = nums[maxIndex]
    let rootNode = new TreeNode(maxVal)
    rootNode.left = constructMaximumBinaryTree(nums.slice(0,maxIndex))
    rootNode.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1, nums.length))
    console.log(rootNode)
    return rootNode
    
};
var getMaxIndex = function(arr){
    // just a utility function for getting the max index.
    let maxIndex = 0
    for(let i = 0; i<arr.length; i++){
        if(arr[i] > arr[maxIndex] ){
            maxIndex = i
        }
    }
    return maxIndex
}

參考資料：
1. stack intro : http://alrightchiu.github.io/SecondRound/stack-introjian-jie.html
2. stack method : http://alrightchiu.github.io/SecondRound/stack-yi-arrayyu-linked-listshi-zuo.html