重新學習 CS 基礎 - 實作堆疊

我一直在嘗試學習新的程式語言，還有什麼比從基礎開始更好的方法呢。在這一系列的文章中，我將嘗試使用 Go 實作一個簡單的資料結構和演算法。 

在 CLRS 的演算法簡介一書中的基本資料結構章節中，討論的第一個資料結構是堆疊。

什麼是堆疊

堆疊是一種簡單的資料結構，用於儲存一組項目。堆疊的屬性是它允許我們將項目新增到堆疊頂部並從堆疊中刪除，因此它遵循後進先出原則或 LIFO。

插入操作稱為Push，刪除操作稱為Pop。由於我們不想彈出空堆疊並處理記憶體錯誤，因此我們也實作了對堆疊是否為空的檢查。相當簡單的資料結構。

下面你可以找到golang中堆疊的實作。使用堆疊的時間複雜度為 O(N)，空間複雜度為 O(1)

package main

import "fmt"

type Stack []int

func (stack *Stack) Push (value int){
    *stack = append(*stack, value)
}

func (stack *Stack) Pop () int{
    if stack.IsEmpty() {
        return 0
    }
    top := (*stack)[len(*stack)-1]
    *stack = (*stack)[:len(*stack)-1]
    return top
}

func (stack *Stack) IsEmpty() bool{
    return len(*stack) == 0
}


func main(){
    st := Stack{}
    st.Push(1)
    st.Push(2)
    fmt.Println(st.Pop())
}

以上是重新學習 CS 基礎 - 實作堆疊的詳細內容。更多資訊請關注PHP中文網其他相關文章！