05.8.1 Go 语言实现栈

现在是时候看看如何使用 Go 语言实现栈了。相关的细节在 stack.go 源文件中。同样，栈的实现也会用到链表。如你所知，你需要两个函数：一个 Push() 函数将元素放入栈中，一个 Pop() 函数从栈中删除元素。单独使用一个变量保存栈中元素的数量是个很实用的方法，这样即使不访问链表也能判断栈是否为空，不过这不是必须的。

stack.go 中的源代码将分四个部分介绍。第一部分如下：

package main

import (
    "fmt"
)

type Node struct {
    Value int
    Next  *Node
}

var size = 0
var stack = new(Node)

stack.go 的第二部分包含了 Push() 函数的实现：

func Push(v int) bool {
    if stack == nil {
        stack = &Node{v, nil}
        size = 1
        return true
    }

    temp := &Node{v, nil}
    temp.Next = stack
    stack = temp
    size++
    return true
}

如果栈为空就创建一个新节点（temp）并将它放在当前栈的最前面，然后新节点会成为栈的头节点。这个版本的 Push() 函数永远返回 true。对于存储空间有限的栈，你可以修改一下，在栈将要溢出时返回 false。

第三部分包含 Pop() 函数的实现：

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

    if size == 1 {
        size = 0
        stack = nil
        return t.Value, true
    }

    stack = stack.Next
    size--
    return t.Value, true
}

stack.go 的第四个代码段如下：

func traverse(t *Node) {
    if size == 0 {
        fmt.Println("Empty Stack!")
        return
    }

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

由于这里的栈是使用链表实现的，所以也用链表的方式进行遍历。

stack.go 的最后一部分如下：

func main() {

    stack = nil
    v, b := Pop(stack)
    if b {
        fmt.Print(v, " ")
    } else {
        fmt.Println("Pop() failed!")
    }

    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 {
            break
        }
    }
    fmt.Println()
    traverse(stack)
}

如你所见，stack.go 的源代码比 queue.go 的稍微短一点，这主要是因为栈背后的思想比队列更简单。

执行 stack.go 将生成如下输出：

Pop() failed!
100 -> 
200 -> 100 -> 
9 8 7 6 5 4 3 2 1 0 200 100 
Empty Stack!

现在为止，你已经知道了如何使用链表实现哈希表、队列和栈。这些例子会让你意识到，在一般情况下链表对于编程和计算机科学来说是多么的有效和重要！