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

從邏輯角度來(lái)說(shuō)，數(shù)組和鏈表都是線性結(jié)構(gòu)（就是排成一條線的結(jié)構(gòu)，只有前后兩個(gè)方向，非線性結(jié)構(gòu)包括樹、圖等，后面會(huì)講到），從存儲(chǔ)角度來(lái)說(shuō)，一個(gè)是順序存儲(chǔ)，一個(gè)是鏈?zhǔn)酱鎯?chǔ)，各有利弊。

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

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

首先來(lái)看棧。

棧的概念

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

棧的概念比較簡(jiǎn)單，理解起來(lái)也不復(fù)雜，下面給出一個(gè)圖示，幫助你形象了解棧的操作流程：

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

棧的實(shí)現(xiàn)

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

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

package main

import (
    "fmt"
)

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

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

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

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

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

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

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

// 遍歷（不刪除任何節(jié)點(diǎn)，只讀取值）
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() 失敗!")
    }

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

    // 批量進(jìn)棧
    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)
}

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

感興趣的同學(xué)可以自行通過(guò) Go 語(yǔ)言的數(shù)組/切片實(shí)現(xiàn)一個(gè)順序棧。

棧的使用場(chǎng)景

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