05.7.1.md

Go 语言实现队列

queue.go 程序描述了 Go 语言的队列实现，我们将分为五个部分来介绍。注意，这里队列的实现使用了链表。Push() 函数和 Pop() 函数分别用于队列中元素的增删。

queue.go 中的第一部分代码如下：

package main

import (
	"fmt"
)

type Node struct {
	Value int
	Next  *Node
}

var size = 0
var queue = new(Node)

用一个参数（size）保存队列中节点的数量很实用但不是必须的。不过为了简化操作，这里展示的实现还是提供了这个功能。

queue.go 的第二部分包含如下的 Go 代码：

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() 函数的实现，这个实现很好理解。如果队列是空的就会被新的节点取代。如果队列不为空，那么新节点就会被插入到当前队列的前面，然后新节点会变成队列的头节点。

queue.go 的第三部分包含如下 Go 代码：

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() 函数的实现，该函数将最老的元素从队列中移除。如果队列为空（size == 0）就没有值可以返回。如果队列只有一个节点，那么将返回这个节点的值，队列也会变成空的。其他情况下将取出队列中的最后一个元素，并将移除最后一个节点，然后对节点的指针进行必要的修改，最后返回被删除节点的值。

queue.go 的第四个代码段包含如下的 Go 代码：

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

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

严格来说，traverse() 函数对于队列的操作并不是必须的，但是它提供了一种实用的方法来查看队列中的所有节点。

queue.go 的最后一个代码段如下：

func main() {
	queue = nil
	Push(queue, 10)
	fmt.Println("Size:", size)
	traverse(queue)

	v, b := Pop(queue)
	if b {
		fmt.Println("Pop:", v)
	}
	fmt.Println("Size:", size)

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

	v, b = Pop(queue)
	if b {
		fmt.Println("Pop:", v)
	}
	fmt.Println("Size:", size)

	v, b = Pop(queue)
	if b {
		fmt.Println("Pop:", v)
	}
	fmt.Println("Size:", size)
	traverse(queue)
}

main() 中几乎所有的代码都是对队列操作的检查。其中最重要的代码是两个 if 语句，它能让你知道 Pop() 函数返回了一个确切的值还是因队列为空而没有返回任何值。

执行 queue.go 将产生如下输出：

Size: 1
10 -> 
Pop: 10
Size: 0
4 -> 3 -> 2 -> 1 -> 0 -> 
Size: 5
Pop: 0
Size: 4
Pop: 1
Size: 3
4 -> 3 -> 2 ->