Go语言中的队列与栈：基础与实践

在日常编程中，数据结构是不可或缺的一部分。无论是开发复杂的系统，还是编写小型工具，选择合适的数据结构都能显著提高程序的效率和可读性。在Go语言中，队列和栈是两种常用的基础数据结构。本文将详细介绍如何在Go中实现队列与栈，并补充一些扩展内容，以帮助大家更好地理解和应用这些结构。

队列：先进先出（FIFO）的数据结构

队列（Queue）是一种特殊的链表结构，新元素总是插入到链表的头部，删除元素则从尾部开始。你可以想象排队去银行办事，只有前面的人完成了业务，你才能上前与柜员交谈。这种“先来先服务”的处理方式就是队列的本质。

队列的优势

队列的最大优势在于它的简单性。我们只需要两个函数：一个用于向队列添加元素，另一个用于从队列中移除元素。由于操作有限，这也意味着程序中出错的概率更低。同时，队列的实现方式也相对灵活，只要能支持这两个操作，具体的实现方式是多种多样的。

Go语言中的队列实现

下面是一个基于链表的队列实现示例，我们通过编写Push()和Pop()函数，分别实现添加和移除节点的功能。

定义节点结构与全局变量

package main

import (
    "fmt"
)

type Node struct {
    Value int     // 节点存储的值
    Next  *Node   // 指向下一个节点的指针
}

var size = 0     // 用于记录队列的大小
var queue *Node  // 队列的头节点

在上面的代码中，我们定义了一个Node结构体，它包含一个存储值的字段Value，以及指向下一个节点的指针Next。此外，使用全局变量size记录队列中的元素个数，queue作为队列的起始节点。

实现Push函数

Push()函数用于向队列中添加元素。它通过创建一个新节点，并将其插入到队列的头部。

func Push(t *Node, v int) bool {
    if queue == nil {
        queue = &Node{v, nil} // 如果队列为空，则新节点成为队列的第一个节点
        size++
        return true
    }
    t = &Node{v, nil}       // 创建新节点
    t.Next = queue          // 将新节点插入到队列的头部
    queue = t
    size++
    return true
}

这个Push()函数逻辑简单：当队列为空时，直接将新节点作为队列的起始节点。否则，新节点插入队列的头部，成为新的队列头。

实现Pop函数

Pop()函数用于从队列中移除最早加入的元素（队尾元素）。如果队列为空，返回false表示无法移除元素。

func Pop(t *Node) (int, bool) {
    if size == 0 {
        return 0, false // 队列为空时，无法移除元素
    }
    if size == 1 {
        queue = nil      // 只有一个元素时，移除后队列为空
        size--
        return t.Value, true
    }

    temp := t
    for t.Next != nil {  // 遍历队列找到最后一个节点
        temp = t
        t = t.Next
    }
    v := temp.Next.Value // 取出队尾元素的值
    temp.Next = nil      // 移除队尾节点
    size--
    return v, true
}

这个Pop()函数根据队列的大小执行不同的操作：如果队列只有一个元素，则直接将队列设为空；如果队列有多个元素，则遍历到队尾并移除它。

遍历队列的辅助函数

为了更直观地查看队列中的元素，我们可以实现一个traverse()函数，用于遍历并打印队列的所有节点。

func traverse(t *Node) {
    if size == 0 {
        fmt.Println("队列为空！")
        return
    }
    for t != nil {
        fmt.Printf("%d -> ", t.Value)
        t = t.Next
    }
    fmt.Println()
}

这个函数会从队列头开始，依次输出每个节点的值，直到遍历完所有节点。

主函数测试

下面是主函数，通过调用Push()和Pop()函数来测试队列的功能。

func main() {
    queue = nil
    Push(queue, 10)
    fmt.Println("队列大小:", size)
    traverse(queue)

    v, b := Pop(queue)
    if b {
        fmt.Println("移除元素:", v)
    }
    fmt.Println("队列大小:", size)

    for i := 0; i < 5; i++ {
        Push(queue, i)
    }
    traverse(queue)
    fmt.Println("队列大小:", size)

    v, b = Pop(queue)
    if b {
        fmt.Println("移除元素:", v)
    }
    fmt.Println("队列大小:", size)

    traverse(queue)
}

运行结果将显示队列的操作过程：

队列大小: 1
10 ->
移除元素: 10
队列大小: 0
4 -> 3 -> 2 -> 1 -> 0 ->
队列大小: 5
移除元素: 0
队列大小: 4
4 -> 3 -> 2 ->

通过上面的代码，我们可以看到，队列的操作符合先进先出的原则。

栈：后进先出（LIFO）的数据结构

栈（Stack）是一种与队列类似的数据结构，但其操作规则是“后进先出”，即最后进入栈的元素会最先被取出。这种结构可以类比为堆叠的盘子，最上面的盘子总是最先被使用。

Go语言中的栈实现

栈的实现与队列非常相似，都是基于链表。在实现过程中，我们需要两个核心函数：Push()用于添加元素，Pop()用于移除元素。

定义节点结构与全局变量

package main

import (
    "fmt"
)

type Node struct {
    Value int     // 节点存储的值
    Next  *Node   // 指向下一个节点的指针
}

var size = 0     // 用于记录栈的大小
var stack *Node  // 栈的顶端节点

实现Push函数

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
}

实现Pop函数

Pop()函数用于移除栈顶元素，并返回其值。

func Pop() (int, bool) {
    if size == 0 {
        return 0, false // 栈为空时，无法移除元素
    }
    v := stack.Value
    stack = stack.Next  // 移除栈顶元素
    size--
    return v, true
}

主函数测试

我们可以通过以下主函数来测试栈的功能：

func main() {
    v, b := Pop()
    if !b {
        fmt.Println("栈为空，无法弹出元素")
    }

    Push(100)
    Push(200)
    for i := 0; i < 5; i++ {
        Push(i)
    }

    for i := 0; i < 6; i++ {
        v, b := Pop()
        if b {
            fmt.Println("弹出元素:", v)
        }
    }
}

运行结果如下：

栈为空，无法弹出元素
弹出元素: 4
弹出元素: 3
弹出元素: 2
弹出元素: 1
弹出元素: 0
弹出元素: 200