Golang实现数据结构Stack(堆栈)的示例详解

什么是Stack？

Stack，也称为堆栈，是一种先进后出（Last In First Out, LIFO）的数据结构。举个例子，比如一堆书，你按照一定的顺序叠起来，然后你想要拿出第一本，你需要先拿掉上面的书才能取到下面的。这就是典型的堆栈模型。

在编程中，Stack也是一种非常常见的数据结构，特别是在函数调用中，它经常被用来存储返回地址和局部变量等信息。

Golang实现Stack

用Slice实现Stack

在Golang中，可以利用Slice来实现Stack。我们先来看一下Slice的基本操作：

// 创建一个Slice
s := make([]int, 0)

// 往Slice中添加元素
s = append(s, 1)
s = append(s, 2)
s = append(s, 3)

// 获取Slice的长度和容量
fmt.Println(len(s)) // 输出：3
fmt.Println(cap(s)) // 输出：4

// 遍历Slice
for i := 0; i < len(s); i++ {
    fmt.Println(s[i])
}

接下来，我们可以通过在Slice的尾部追加和删除元素来实现Stack的基本操作。具体地，我们定义一个Stack结构体：

type Stack struct {
    s []int
}

// 往Stack里添加元素
func (stack *Stack) Push(v int) {
    stack.s = append(stack.s, v)
}

// 从Stack里弹出元素
func (stack *Stack) Pop() int {
    res := stack.s[len(stack.s)-1]
    stack.s = stack.s[:len(stack.s)-1]
    return res
}

// 判断Stack是否为空
func (stack *Stack) IsEmpty() bool {
    return len(stack.s) == 0
}

// 获取Stack的长度
func (stack *Stack) Size() int {
    return len(stack.s)
}

我们可以用Stack的Push方法往Stack里添加元素，用Pop方法从Stack里弹出元素。下面是一个简单的示例：

func main() {
    stack := &Stack{}
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    for !stack.IsEmpty() {
        fmt.Println(stack.Pop())
    }
}

输出：

3
2
1

用List实现Stack

Golang也提供了标准库container/list来实现Stack。list里有PushBack、PushFront、Remove等方法可以方便地操作Stack。下面是一个示例：

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)
    for e := l.Back(); e != nil; e = e.Prev() {
        fmt.Println(e.Value.(int))
    }
}

输出：

3
2
1

上面的代码定义了一个List，通过PushBack方法往List里添加元素，通过Back方法获取List的尾部元素，在循环中依次遍历List。这个示例相比于使用Slice实现Stack来说更优雅，但如果你的代码已经使用了Slice实现Stack，没有必要刻意地引入一个新的库来实现相同的效果。