基礎技能樹-22 基於數組實現數據結構

本節內容 - 開篇 - 棧(Stack) - 隊列(Queue) - 緩衝區(Pool) - 鏈表(Linked List) ...

本節內容

基礎技能樹系列文章導航
開篇
棧(Stack)
隊列(Queue)
緩衝區(Pool)[付費閱讀]
鏈表(Linked List)[付費閱讀]

開篇

很顯然數組帶來很大的好處，直接的好處有幾點，第一它是一塊完整的連續的記憶體而且只需要一次性分配，第二數組本身訪問效率很高，第三我們可以對數組進行複製，因為數組只有一塊記憶體，我只要把這一塊的記憶體完整複製就可以了，而其他的很多複合結構可能有多塊記憶體組成的，我們想複製的時候並不容易。比如切片還好點只有兩塊記憶體，比如像鏈表可能有很多塊記憶體，我們想複製一個鏈表的時候我們得遍歷一塊一塊的複製，所以數組先天性的具備了性能上的優勢，我們承認數組在操作上的確有很多麻煩，但數組的性能不能忽略。接下來我們做的是能不能用數組實現常用的數據結構。第一我們使用數組帶來的性能優勢，第二把數組轉換為另外的訪問方式帶來操作上的便利性。把這兩者結合起來，因為直接操作數組的很多時候比較麻煩，比如我們插入、刪除這些操作不特別方便。所以我們接下來把數組和其他數組結構訪問上的便利性結合起來。

棧(Stack)

棧是很典型的先進後出(FILO)數據結構。其實我們在前面接觸很多的棧，調用堆棧本身就是一個棧結構，它是一個記憶體空間，地址從高位到低位分配，首先高位記錄一個位置，比如使用BP寄存器保存，另外一個位置用SP寄存器來處理當前棧頂的位置。加一個數據即Push操作SP往上減，彈出一個數據即Pop操作SP往下增。很顯然用一個數組加兩個欄位來模擬SP、BP就可以了。我們怎麼樣去做呢，用一個最簡單的做法就是第一種方式使用一個結構體，指針屬性指向一個數組，數組天生就包含了起始位置BP和容量cap，或者這個數組直接內聯，然後SP屬性記錄棧頂的位置就可以實現簡單棧的管理。還有個簡單的方式使用一個數組，把位置一當作BP寄存器使用，假如我們需要分配四個元素項的棧，那麼實際分配就是4+1，把索引0當作BP來用，以後就是操作數組後面的空間。這樣的方式與結構體類似，因為結構體本身記憶體也是連續的，一塊是數組，一塊是BP，結構體也是這樣的數據結構本質上是一回事。當然也可以用數組方式做，只需要有個地方記錄一下BP的值就可以了，所以整個的棧結構實現起來非常的簡單。

s是一個動態的記憶體，所以我們用切片的方式去創建，切片看上去和數組是一樣的，我們的目的是獲得一個動態數組，我們把容量+1，用0來當作BP寄存器來用。首先初始化的時候0指向棧底的位置，然後往裡加數據的時候BP往上移，所以BP初始化的時候指向最後一個位置。接下來往裡面加數據的時候，讀取BP寄存器的值，如果這時候SP指向0的位置的時候棧已經滿了，先判斷棧是否已經滿了，滿了的話返回一個錯誤，如果不滿的話直接把數據寫進去，同時往裡壓數據的時候，每壓一個數據，BP寄存器往上移一次，表示下次可以往新的地方寫。彈出數據的時候，BP寄存器記錄的是最後一次可寫的位置，可寫和可讀的數據中間應該差一個，首先加上1調整BP寄存器位置，如果這個位置指向最低的時候表示沒有數據了，表示為空，如果有數據就返回，同時調整BP寄存器，因為我們知道彈出數據的時候，SP往下做加法，壓數據的時候，SP往上做減法。整個操作很簡單也就是4-5行核心代碼。

如果不用數組用鏈表實現隊列和棧最簡單的，但是鏈表在記憶體管理上有很大的缺陷。

package main

import "errors"

type Stack []int

var (
    ErrStackFull  = errors.New("stack full")
    ErrStackEmpty = errors.New("stack empty")
)

func NewStack(cap int) Stack {
    s := make([]int, cap+1)
    s[0] = cap
    return s
}

func (s Stack) Push(v int) error {
    i := s[0]
    if i == 0 {
        return ErrStackFull
    }

    s[i] = v
    s[0] = i - 1

    return nil
}

func (s Stack) Pop() (int, error) {
    i := s[0] + 1
    if i == cap(s) {
        return 0, ErrStackEmpty
    }

    v := s[i]
    s[0] = i

    return v, nil
}

隊列(Queue)

隊列是很典型的先進先出(FIFO)數據結構。隊列如果是一個數組結構，我們從左往右加數據，實際上有兩個屬性需要註意的，第一個是寫W的位置，第二個是讀R的位置。比如我們可以連續寫3個格子，寫的位置就到位置4，讀的位置還是停留在位置1，所以讀和寫的位置是不一樣的。這地方就有個問題，我們怎麼維護讀和寫的位置。比如說寫滿了以後就不能寫了，我們通常會實現一個環狀隊列，比如寫滿了，接下來讀操作，讀到位置3，那麼1-2空間就重新可用了，寫的位置就會調整到位置1，這就有個麻煩，W可能大於R，W也可能小於R，我們怎麼處理這個呢？

記錄當前元素數量記錄W和R的位置，因為W和R預設都為0，當往裡面寫的時候數量會遞增，當數量等於容量的時候表示滿了，假如數據數量是2，在位置2和位置3，W寫的時候寫在位置4，寫滿了，這時候數據數據不等於容量，怎麼知道W需要回頭呢。所以W和R除了要和數據數量比較還需要和容量即最後一個索引號比較。如果等於最大的索引號，W就需要回頭。

第一個背景，假設有這樣的一個容器，4個格子，我們有個指針一直做加法，那麼到一定程度就超出了容器的限制，不管這個指針超出多大，我們對於指針與容量取模操作結果值肯定是在容量範圍之內。任何一個數字除以一個固定容量那麼餘數肯定會在這個範圍之類。

第二個背景，隊列R和W最大的麻煩是隊列有長度限制，因為有長度限制，所以R和W有回頭操作，假如長度沒有限制無限長，那麼W永遠大於等於R，W減去R肯定是當前數據長度，這樣的話，隊列長度無限的，判斷邏輯就非常簡單。

我們把第一個背景和第二個背景組合到一起，如果變成一個環，假如這個隊列是個環狀的，假如這個環是無限大小的，那麼R到W區域就是有數據的。問題是真實情況我們的隊列肯定是有限制的，我們用抽象大小的環來處理R和W的值，第一個用抽象的處理R和W，避免R和W回頭操作，第二個在數據讀寫的時候，去做取模操作，因為取模操作就可以映射到真實的容量具體的位置上面，那麼接下來需要判斷事就很簡單，要麼寫滿了，要麼是空的沒數據。

package main

import (
    "errors"
)

type RingQueue struct {
    data []int
    head int
    tail int
}

var (
    ErrQueueFull  = errors.New("queue full")
    ErrQueueEmpty = errors.New("queue empty")
)

func NewRingQueue(cap int) *RingQueue {
    return &RingQueue{
        data: make([]int, cap),
    }
}

func (q *RingQueue) Push(x int) error {
    if (cap(q.data) - (q.tail - q.head)) == 0 {
        return ErrQueueFull
    }

    n := q.tail % cap(q.data)
    q.data[n] = x

    q.tail++
    return nil
}

func (q *RingQueue) Pop() (int, error) {
    if q.tail == q.head {
        return 0, ErrQueueEmpty
    }

    n := q.head % cap(q.data)
    x := q.data[n]

    q.head++
    return x, nil
}

這是很簡單的數據結構，一個數組，一個讀一個寫，寫的位置作為頭head，讀的位置作為尾tail。頭和尾之間的區域就是有數據的區域。往裡面寫Push的時候，先判斷下當前是否有真實的地方有空位，假如無限大小的，tail減去head是有數據的區域，總長度減去有數據的長度就是空位長度，所以cap(data) - (tail - head)就是是否有空位，那麼tail和head一直累加和總長度沒有關係的，這樣的話首先判斷是否有空位，如果空位等於零就表示已經滿了，直接返回一個錯誤。如果沒有滿，把尾部的信息取模操作就是把抽象的環映射到真實的數據結構上面。接下來在真實位置寫，然後把抽象環上的tail值累加。讀操作其實也是一樣的，所以說這地方只有兩個概念構成，抽象大小的環處理tail和head的位置，這兩個位置只是要判斷有數據的長度或者是空位的長度，有數據的長度大於零代表有數據，空位的長度大於零代表有寫的位置。對應映射固定長度的隊列，有數據隊列上肯定有數據的，有空位隊列上肯定有空位的。

這樣一來我們就不需要處理tail和head前後的問題了，把這個邏輯變得很簡單了，有些時候我們需要用抽象的概念去處理複雜的邏輯，就是把複雜的邏輯抽象化。我們藉助抽象的概念來處理簡單的索引位置。這是一個很典型的環狀設計。

package main

import "fmt"

func main() {
    s := NewRingQueue(3)

    fmt.Println(s.Push(1), s)
    fmt.Println(s.Push(2), s)
    fmt.Println(s.Push(3), s)
    fmt.Println(s.Push(4), s)

    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())

    fmt.Println(s.Push(4), s)
    fmt.Println(s.Push(5), s)
    fmt.Println(s.Pop())
}