Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（二）：棧

從邏輯角度來說，數(shù)組和鏈表都是線性結(jié)構(gòu)（就是排成一條線的結(jié)構(gòu)，只有前后兩個方向，非線性結(jié)構(gòu)包括樹、圖等，后面會講到），從存儲角度來說，一個是順序存儲，一個是鏈式存儲，各有利弊。

數(shù)組需要預先申請連續(xù)內(nèi)存，超出限制會溢出，但是對明確知道規(guī)模的小型數(shù)據(jù)集而言，使用數(shù)組會更加高效，隨機訪問的特性也更加方便數(shù)組讀取，但插入和刪除性能要差一些；鏈表的話沒有空間限制，但是需要額外空間存儲指針，插入、刪除效率很高，但不支持隨機訪問。

接下來我們要介紹兩種特殊的線性結(jié)構(gòu)，或者說用于滿足特定場景需求的線性結(jié)構(gòu)：棧和隊列。

首先來看棧。

棧的概念

棧（Stack）又叫堆棧，是限定只能在一端進行插入和刪除操作的線性表，并且滿足后進先出（LIFO）的特點，即最后插入的最先被讀取。我們把允許插入和刪除的一端叫做棧頂，另一個端叫做棧底，不含任何數(shù)據(jù)的棧叫做空棧。

棧的概念比較簡單，理解起來也不復雜，下面給出一個圖示，幫助你形象了解棧的操作流程：

我們將插入操作叫做進棧，讀取（刪除）操作叫做出棧。

棧的實現(xiàn)

棧支持通過數(shù)組或鏈表實現(xiàn)，通過數(shù)組實現(xiàn)的通常叫做順序棧，通過鏈表實現(xiàn)的叫做鏈棧。通過鏈表實現(xiàn)沒有空間限制，并且插入和刪除元素的效率更高，顯然更加合適一些，下面我們基于 Go 語言來實現(xiàn)一個簡單的鏈棧。

鏈棧本質(zhì)上就是一個特殊的鏈表，特殊之處在于只能從頭部插入節(jié)點，然后從頭部讀取（并刪除）節(jié)點，因此實現(xiàn)起來非常簡單，我們?yōu)檫@個棧提供了進棧、出棧和遍歷功能：

package main

import (
    "fmt"
)

// 定義鏈表節(jié)點
type Node struct {
    Value int
    Next  *Node
}

// 初始化棧結(jié)構(gòu)（空棧）
var size = 0
var stack = new(Node)

// 進棧
func Push(v int) bool {
    // 空棧的話直接將值放入頭節(jié)點即可
    if stack == nil {
        stack = &Node{v, nil}
        size = 1
        return true
    }

    // 否則將插入節(jié)點作為棧的頭節(jié)點
    temp := &Node{v, nil}
    temp.Next = stack
    stack = temp
    size++
    return true
}

// 出棧
func Pop(t *Node) (int, bool) {
    // 空棧
    if size == 0 {
        return 0, false
    }

    // 只有一個節(jié)點
    if size == 1 {
        size = 0
        stack = nil
        return t.Value, true
    }

    // 將棧的頭節(jié)點指針指向下一個節(jié)點，并返回之前的頭節(jié)點數(shù)據(jù)
    stack = stack.Next
    size--
    return t.Value, true
}

// 遍歷（不刪除任何節(jié)點，只讀取值）
func traverse(t *Node) {
    if size == 0 {
        fmt.Println("空棧!")
        return
    }

    for t != nil {
        fmt.Printf("%d -> ", t.Value)
        t = t.Next
    }
    fmt.Println()
}

func main() {
    stack = nil
    // 讀取空棧
    v, b := Pop(stack)
    if b {
        fmt.Print(v, " ")
    } else {
        fmt.Println("Pop() 失敗!")
    }

    // 進棧
    Push(100)
    // 遍歷棧
    traverse(stack)
    // 再次進棧
    Push(200)
    // 再次遍歷棧
    traverse(stack)

    // 批量進棧
    for i := 0; i < 10; i++ {
        Push(i)
    }

    // 批量出棧
    for i := 0; i < 15; i++ {
        v, b := Pop(stack)
        if b {
            fmt.Print(v, " ")
        } else {
            // 如果已經(jīng)是空棧，則退出循環(huán)
            break
        }
    }

    fmt.Println()
    // 再次遍歷棧
    traverse(stack)
}

運行上述代碼，打印結(jié)果如下：

感興趣的同學可以自行通過 Go 語言的數(shù)組/切片實現(xiàn)一個順序棧。

棧的使用場景

棧在日常開發(fā)和軟件使用中，應用非常廣泛，比如我們的瀏覽器前進、倒退功能，編輯器/IDE 中的撤銷、取消撤銷功能，程序代碼中的函數(shù)調(diào)用、遞歸、四則運算等等，都是基于棧這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的，就連著名的 stackoverflow 網(wǎng)站也是取棧溢出，需要求教之意。