在日常编程中，数据结构是不可或缺的一部分。无论是开发复杂的系统，还是编写小型工具，选择合适的数据结构都能显著提高程序的效率和可读性。在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