开发者学堂课程【Go 语言核心编程 - 数据结构和算法：数据结构和算法-数组模拟环形队列实现（一）】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/627/detail/9834
数据结构和算法-数组模拟环形队列实现（一）
内容简介：
一、代码实现
二、代码说明
三、代码运行
一、代码实现
打开 VSCode ，在 chapter20 文件夹中新建一个文件称为 circlequeue ，再在其内新建一个文件称为 main.go ，并输入以下代码:
package main
import (
“fmt”
“errors”
“os”
)
//使用一个结构体管理环形队列
type CircleQueue struct {
maxSize int //4
array [4]int //数组
head int //指向队列队首 0
tail int //指向队尾 0
}
//入队列 AddQueue(push) GetQueue(pop）
func (this *circleQueue) Push(val int) (err error) {
if this.IsFull() {
return errors.New(“queue full”)
}
//分析出 this.tail 在队列尾部，但是包含最后的元素
this.array[this.tail] = val //把值给尾部
this.tail++
return
//出队列
func (this *circleQueue) Pop() (val,err error) {
if this.IsEmpty() {
return 0, errors.New(“queue empty”)
}
//取出 head 是指向队首，并且含队首元素
val = this.array[this.head]
this.head++
return
}
//显示队列
func (this *CircleQueue) ListQueue() {
fmt.Println(“环形队列情况如下:”)
//取出当前队列有多少个元素
size := this.Size()
if size == 0 {
fmt.Println(“队列为空”)
}
//设计一个辅助的变量，指定 head
tempHead := this.head
for i := 0； i < size；++ {
fmt.Println(“arr[%d]=%d\t, tempHead, this.array[tempHead])
tempHead = (tempHead + 1) this.maxSize
}
fmt.Println()
}
//判断环形队列是满
func (this *CircleQueue) IsFull() bool {
return (this.tail + 1) % this.maxSize == this.head
}
//判断环形队列是空
func (this *CircleQueue) IsEmpty() bool {
return this.tail == this.head
}
//取出环形队列有多少个元素
func (this *CircleQueue) Size() int {
//这是一个关键的算法。
return (this.tail + this.maxSize - this.head ) % this.maxSize
}
func main() {
//初始化一个环形队列
queue := &CircleQueue{
maxSize : 5,
head : 0,
tail : 0,
}
var key string
var val int
for {
fmt.Println(“1.输入 add 表示添加数据队列”)
fmt.Println(“2.输入 get 表示从队列获取数据”)
fmt.Println(“3.输入 show 表示显示队列”)
fmt.Println(“4.输入 exit 表示显示队列”)
fmt.Scanln(&key)
switch key {
case “add”:
fmt.Println(“输入你要入队列数”)
fmt.Scanln(&val)
err := queue.Push(val)
if err != nil {
fmt.Println（err.Error())
} else {
fmt.Println(“加入队列ok”)
}
case “get”:
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println(“从队列中取出了一个数=”,val)
}
case”show”:
case”exit”:
os.Exit(0)
二、代码说明
说明①:这个可能看起来有点吃力，因为这是个环形列表，大家都不停的在后面， head 在不停的长，在加到快出去的时候加一个 maxSize ，然后就回去了，所以说会造成这个 tail 在某个情况下，它的自然值是小于 head 的，因为你还在后面去了，所以要把它加上，再减掉，再模上。
说明②:问一个问题，思考一下，如果像“this.tail++”这样写的话，tail 到底有没有包含这个队列的最后一个元素，就是在它运行的那瞬间，到底有没有包含它最后一个元素?
应该是没有的，因为初始化的时候，两个都是零,从目前算法来看，这个 tail 是在这个队列的最后，但是它没有包含最后一个元素。这样分析出这个尾部 this.tail ，它在队列尾部，但是它不含最后一个元素，它相当于是在最后一个元素，后面再移了一位。
可能会想为什么要移位？如果包含的话，这个就不好做，先看图片，如下:
原先箭头在1的位置，我加1，再加1，再加1，一直往前走，走到4位置的时候，因为它其实真的数据还在3的位置，等到再加一个的时候，其实这时的 tail 就是上图所指向的地方，没有真正的东西，因为要把这个地方留下来，当作一个标志位，然后判断一下我加1是不是等于零，如果等于零，就说明已经满了，最后这个要留下来。为什么留下来的原因是这样子的，如果不留下来，队首因为在整个环境取的时候，队列的首会发生变化，如果中间没有一个标志位很难处理，但是有些人会问为什么要标志位，在写的过程中会发现写了好久没有这个东西，没办法往下弄，
所以说环形链表用数组模拟环境列表，它实际的容量是这个数组的大小减一，如果你最后不留一个，这个叫做约定或者标志，此环境列表很难实现，为什么要这样做？
这个在做的工作实在没别的办法，想来想去没办法，便只能做一个约定。
如果你有一个办法说不留一个且最后这个都能用上，你厉害。从逻辑上看起来可能更复杂一点，估计会多一点判断，因为这个地方不留东西的话，不知道会出什么问题，可以试一下将其写出来，写出来给大家参考一下，这里就采用了一个相对容易理解的，我就留了一个，这个影响不是很大，为什么？
比如有一个数组，这个数组有50个元素，有一个没用，应该还是能够接受的，这个我就采用的是这种方式，即预留一个，最后做一个约定。
说明③:以上图作为参考，显示一个环形队列，有一个队首、一个队尾，可能会觉得那就从队首开始遍历到队尾就可以了，这是不对的，因为现在是变成环形的，环形的话就有可能出现这种情况，比如这个队尾走到5的位置，到这里突然因为种种原因，往前面加了一个，那也就是说，它的下标有可能是队尾小于队首，所以现在不能就给它一个 front ，然后遍历，这根本就不对了，代码执行不起来，所以这地方，不能再用那种方式。
