Go 语言中的栈

欢迎回到Go 数据结构入门！今天，我们将学习栈。栈很容易理解，而且用途广泛。它在编程面试中也经常出现，因为它的特性可以衍生出许多很棒的应用。

什么是栈？

栈是一种遵循后进先出（LIFO）原则的数据结构。也就是说，最后放入的数据会最先被取出。想象一下一摞盘子。我们会从下往上堆叠盘子，然后先使用最上面的盘子。

用 Go 语言编写

实现起来非常简单。我们将使用切片来实现栈。

type Stack struct {
    items []int
}

我们首先定义一个Stack类型，并将items其属性设为整数。我们的栈负责存储整数，但您可以根据需要更改数据类型。

栈最重要的两种操作是压入push和弹出pop。将元素压入栈会将元素添加到栈顶，而从栈中弹出则会移除栈顶的元素。

func (s *Stack) Push(data int) {
    s.items = append(s.items, data)
}

func (s *Stack) Pop() {
    if s.IsEmpty() {
        return
    }
    s.items = s.items[:len(s.items)-1]
}

这些方法作用于指向我们Stack类型的指针，因为我们需要主动对其进行更改。

Push很简单——我们只需要将数据附加到s.items……

Pop也很简单。我们首先处理栈为空的情况，此时该方法不会执行任何操作。在其他情况下，我们可以取一个切片，其中s.items包含除最后一个元素之外的所有元素。

我们将定义另外三种有用的实用方法。

func (s *Stack) Top() (int, error) {
    if s.IsEmpty() {
        return 0, fmt.Errorf("stack is empty")
    }
    return s.items[len(s.items)-1], nil
}

func (s *Stack) IsEmpty() bool {
    if len(s.items) == 0 {
        return true
    }
    return false
}

func (s *Stack) Print() {
    for _, item := range s.items {
        fmt.Print(item, " ")
    }
    fmt.Println()
}

Top返回栈顶元素。当栈为空时，它将返回零值并报错，提示栈为空。

IsEmpty如果栈为空，则返回 true；否则返回 false。

Print遍历堆栈并打印元素。

这固然不错，但我该在哪里使用它呢？

目前看来，这似乎只是在切片功能上增加了一些步骤。这到底有什么用呢？

堆栈用于以下用途：

• 实现撤销操作。

• 反转字符串或数组。

• 内存中的调用堆栈。

• 在浏览器和文件资源管理器中前进和后退。

• 中缀、前缀和后缀表达式之间的转换。

• 检查括号是否正确闭合。

这些都是很有趣的用途，我们可以详细探讨其中比较有趣的一些用途。

撤销操作

我们只需要将上次操作的详细信息存储在一个栈中。当想要撤销操作时，只需弹出栈顶元素即可恢复到上次保存的状态。

反转字符串或数组

我们遍历字符串中的字符或数组中的元素，并将它们存储在栈中。完成后，我们只需读取栈顶元素并将其弹出，直到栈为空为止。

调用栈

stackoverflow.com名称中的“stack”指的是程序的调用栈。程序运行时，会分配一定大小的内存作为程序的调用栈。这个栈存储着所有被调用的函数。栈中存储的每个函数调用还会保存在该函数作用域内生成的局部变量的值。

需要注意的是，栈溢出是指调用的函数数量超过调用栈所能容纳的数量时发生的错误。这种情况通常发生在未能跳出递归函数时。栈溢出还可能导致缓冲区溢出攻击等潜在攻击，拥有高权限的恶意用户可以故意使栈溢出，导致栈内重要数据泄露。

中缀、前缀和后缀表示法

这有点复杂。所以通常情况下，我们会这样写表达式：

a + b

这就是所谓的中缀表达式。这是因为运算符位于两个操作数之间。根据这一点，你大概可以猜到另外两个表达式是什么样的。

Infix: <operand><operator><operand>
Prefix: <operator><operand><operand>
Postfix: <operand><operand><operator>

例如，上面所示的表达式也可以这样写：

Infix: a+b
Prefix: +ab
Postfix: ab+

我们为什么要这样写呢？嗯，虽然中缀表达式对人眼来说很美观，但对计算机来说却没什么吸引力。就像高级语言对人友好，低级语言对机器友好一样，前缀和后缀表达式更容易被计算机处理。

简单的表达式用中缀表示法很容易解析，但这不具备可扩展性。例如，请看这个表达式。

{(a*b) + (c*d)} - e

当括号和运算符数量很多时，难度就会迅速增加。我们不仅需要处理这些运算，还需要记住运算顺序。

Infix: {(a*b) + (c*d)} - e
Postfix: ab*cd*+e-

后缀表达式更容易理解，因为我们只需要从左到右扫描表达式就能得到结果。我们可以使用栈将中缀表达式转换为后缀表达式。具体是怎么做的呢？细节将在下一篇文章中介绍，因为这部分内容比较复杂。

检查括号是否正确闭合

当一个括号正确闭合时，我们称之为平衡。

Balanced: (a+b), {(a*b) + (c*d)}
Unbalanced: (a+b, []int{0, 1, 2), [)](

手动检查每个括号会很繁琐。我们可以使用栈来轻松地检查平衡性。

type StringStack struct {
    items []string
}

func checkBalance(exp string) bool {
    s := StringStack{}

    for _, char := range exp {
        switch char {
        case '(':
            s.Push(string(char))
        case '{':
            s.Push(string(char))
        case '[':
            s.Push(string(char))
        case ')':
            top, _ := s.Top()
            if top == "(" {
                s.Pop()
            } else {
                return false
            }
        case '}':
            top, _ := s.Top()
            if top == "{" {
                s.Pop()
            } else {
                return false
            }
        case ']':
            top, _ := s.Top()
            if top == "[" {
                s.Pop()
            } else {
                return false
            }
        }
    }

    if s.IsEmpty() {
        return true
    }
    return false
}

这段代码看起来有点丑陋，但它能完成任务。代码很长，因为我们要处理三种不同类型的括号：`\n` ()、{}`\n` 和 `\ []n`。让我们看看它的逻辑是如何运作的。

• 我们创建一个StringStack名为的实例s。

• 遍历输入字符串。每个字符都将用一个符文表示，符文是一种特殊的 Unicode 字符代码点表示方法。符文可以轻松转换为字符串。

• 如果一个字符是左括号，则将其添加到堆栈中。

• 如果一个字符是右括号，我们会检查栈顶元素是否匹配。对于右括号)，s.Top()应该返回(以保持平衡。如果括号匹配，则从栈中弹出该字符。否则，括号不平衡，因此应该返回空字符false。

• 继续遍历字符串，直到遍历完毕。如果栈中还有剩余元素，则表示某些括号未正确闭合，导致括号不平衡。但是，如果栈为空，则返回，true因为栈已平衡。

结论

我们讲解了 Go 语言中栈的基本实现及其方法，也介绍了栈在实际应用中的一些常见用法。对于初学者，我希望这篇文章能帮助你理解栈的概念；对于经验丰富的开发者，我希望这篇文章能帮助你温故知新。无论如何，我希望你阅读这篇文章时感到愉快。谢谢！

您也可以在Medium和我的个人网站上阅读这篇文章。