GO语言学习实战2：环形队列的实现

GO语言中数组在定义的时候就会指定一个空间容量，为充分利用数组的向量空间，克服数组"假溢出"现象的方法是：将数组向量空间想象为一个首尾相接的圆环，并称这种数组向量为循环向量。

如下图，定义一个容量为7的数组，当array[6]的时间，让指针又重新指向array[0]，实现一个循环的队列。让数组的首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。 循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

在循环队列中，当队列为空时，有 t.ptrTail == t.ptrHead（头=尾），而当所有队列空间全占满时，也有 （头=尾）的情况。为了区别这两种情况，规定循环队列最多只能有 t.MaxSize-1 个队列元素，当循环队列中只剩下一个空存储单元时 (t.ptrTail+1)%t.maxSize == t.ptrHead ，队列就已经满了。

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件t.ptrTail == t.ptrHead 来判别队列是"空"还是"满"。

解决这个问题的方法至少有两种：

① 另设一布尔变量以区别队列的空和满；

②另一种方式就是数据结构常用的： 队满时：(t.ptrTail+1)%t.maxSize==t.ptrHead，由于t.ptrTail，t.ptrHead均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算：

假设队列已满，但是 t.ptrTail（5）+1=6！=t.ptrHead（0），对空间长度求余，作用就在此 6%6=0=t.ptrHead（0）。

类型定义采用环状模型来实现队列,各数据成员的意义如下：

t.ptrHead指定队首位置，取出一个元素就将t.ptrHead顺时针移动一位；

val = t.array[t.ptrHead]                //取出要返回的位置
t.ptrHead = (t.ptrHead + 1) % t.maxSize //将头部指向新位置

t.ptrTail指向元素要插入的位置，插入一个元素就将t.ptrTail顺时针移动一位；

t.array[t.ptrTail] = val                //修改当前队列最后位置的值
t.ptrTail = (t.ptrTail + 1) % t.maxSize //队列尾部指向新位置

t.Size()存放队列中元素的个数，当t.Size()等于t.maxSize时，不可再向队列中插入元素。

t.size=(t.ptrTail - t.ptrHead + t.maxSize) % t.maxSize //统计队列长度
t.maxSize = len(queue.array) //通过统计队列数组长度限制最大长度

 

下面是通过GO实现的环形队列代码：

package main

import (
	"errors"
	"fmt"
	"os"
)

//CircleQueue 队列数据结构
type CircleQueue struct {
	maxSize int    //队列可存放最大数
	array   [7]int //队列数组
	ptrHead int    //队列指针头
	ptrTail int    //队列指针尾
}

//Push form *CircleQueue 向队列里写入一个数据
func (t *CircleQueue) Push(val int) (thePtrTail int, err error) {
	if t.IsFull() {
		return 0, errors.New("列队已满~")
	}
	t.array[t.ptrTail] = val                //修改当前队列最后位置的值
	thePtrTail = t.ptrTail                  //临时变量返回当前ptrTail位置
	t.ptrTail = (t.ptrTail + 1) % t.maxSize //队列尾部指向新位置，保存下次用户输入的值
	fmt.Printf("nt=========> Push(val int) 当前 t.ptrHead = %d , t.ptrTail = %d，所以t.array[%d] = %d ,t.ptrTail下次将指向 -> %d <=========n", t.ptrHead, thePtrTail, thePtrTail, val, t.ptrTail)
	return
	/*
		初始化为0（t.ptrTail==0）所以array[t.ptrTail] = array[0] = val
		用户输入-> 1：Push(1) -> t.array[t.ptrTail=0] = t.array[0] = 1;
		执行：t.ptrTail = (0 + 1) % 7=1（t.ptrTail取余后结果为1）用于保存下次用户输入的值
		当t.ptrTail=6的时候(6+1)%7=0,array[t.ptrTail] 又回到了 array[0] = val 为了防止未取出的数丢失可以使用了IsFull去判断
	*/
}

//Pop form *CircleQueue 从队列里读取一个数据
func (t *CircleQueue) Pop() (val int, ptr int, err error) {
	ptr = t.ptrHead //要出队的数据位置
	if t.IsEmpty() {
		return 0, ptr, errors.New("nnt=========> 队列里没有可取数据~ <=========nn")
	}
	val = t.array[ptr]                      //取出当前位置的值
	t.ptrHead = (t.ptrHead + 1) % t.maxSize //将头部指针偏移到新位置供下次取出
	fmt.Printf("nt=========> Pop() 当前 t.ptrHead=%d , t.ptrTail=%d ,下次 t.ptrHead 将指向 -> %d <=========n", ptr, t.ptrTail, t.ptrHead)
	fmt.Printf("nt=========> (t.ptrHead + 1) %% t.maxSize => (%d + 1) %% %d = %d <=========n", ptr, t.maxSize, t.ptrHead)
	fmt.Printf("nt=========> 所以 val = t.array[%d] = %d <=========nn", ptr, val)
	return
}

//IsFull form CircleQueue 判断队列是否满了
func (t CircleQueue) IsFull() bool {
	return (t.ptrTail+1)%t.maxSize == t.ptrHead
	//如果尾部+1取模最大数后与头部处于同一位置时，表示队列已满
	/*
		当t.ptrTail = 6的时候 (6+1)%7 == 0 而 t.ptrHead没有取，初始依然为0，所以返回0==0 true
		当t.ptrTail = 5 的时候 (5+1)%7 == 1 而 t.ptrHead=1 取了1个
	*/
}

//IsEmpty form CircleQueue  判断队列是否为空
func (t CircleQueue) IsEmpty() bool {
	return t.ptrTail == t.ptrHead //队列的头与尾指向同一个位置，代表为空
}

//Size form CircleQueue 获取队列有多少个元素
func (t CircleQueue) Size() int {
	return (t.ptrTail - t.ptrHead + t.maxSize) % t.maxSize
	//队列的头-队列的尾+队列最大数 % 取模队列最大数
}

//ShowQueue form CircleQueue 显示列队里所有的元素
func (t CircleQueue) ShowQueue() {
	fmt.Println()
	if t.Size() == 0 {
		fmt.Println("队列为空")
	} else {
		fmt.Print("当前队列数据：")
		temp := t.ptrHead
		for i := 0; i < t.Size(); i++ {
			fmt.Printf("array[%d] = %dt", temp, t.array[temp])
			temp = (temp + 1) % t.maxSize
		}
		fmt.Println()
		if t.IsFull() {
			fmt.Println("请注意：当然列队已满(队列容量：", t.Size(), ")，不能再添加数据~")
		}
		fmt.Println()
		fmt.Println()
		fmt.Println("上面队列输出算法为：")
		temp = t.ptrHead
		for i := 0; i < t.Size(); i++ {
			fmt.Printf("nt===========================>   for i = %d   <===========================n", i)
			fmt.Printf("t=========> 当前 temp = %d ,所以：array[temp(%d)] = %d <=========", temp, temp, t.array[temp])
			preTemp := temp
			temp = (temp + 1) % t.maxSize
			fmt.Printf("nt=========> 下次 temp = %d ,算法为：temp = (temp + 1) %% t.maxSize => (%d + 1) %% %d = %d <=========n", temp, preTemp, t.maxSize, temp)
		}
		fmt.Println()
	}
}
func main() {
	queue := &CircleQueue{
		ptrHead: 0, //队列头部初始指向0
		ptrTail: 0, //没有数据的时候尾部也是0
	}
	//最大个数与数组长度一样，并保留1位，实际能使用的只有maxSize-1
	queue.maxSize = len(queue.array)
	var key string //存放用户键盘输入
	var val int    //存放用户输入队列的数字
	for {
		if key == "" {
			fmt.Println()
			fmt.Println("<---====== 环 形 队 列 使 用 说 明 =======--->")
			fmt.Println()
			fmt.Println("	1.输入“add”添加数据到队列")
			fmt.Println("	2.输入“get”从队列获取一个数据")
			fmt.Println("	3.输入“show”显示队列所有数据")
			fmt.Println("	4.输入“exit”退出程序")
			fmt.Println()
			fmt.Println("<---=====================================--->")
			fmt.Println()
		}
		fmt.Print("请输入：“add”、“get”、“show”、“exit”：")
		fmt.Scanln(&key) //用户输入
		switch key {
		case "add":
			if queue.IsFull() {
				fmt.Println("当前队列已满(当前容量：", queue.Size(), ")，无法增加新数据！请使用get取出后才能再次添加到队列~")
			} else {
				fmt.Println()
				fmt.Print("请输入要加入队列的数值：")
				fmt.Scanln(&val)                   //用户输入的值
				thePtrTail, err := queue.Push(val) //添加数据到队列
				fmt.Println()
				if err != nil {
					fmt.Println(err.Error())
				} else {
					fmt.Printf("tarray[t.ptrTail] = val => array[%d] = %d 队列已加入n", thePtrTail, val)
				}
				fmt.Println()
			}
		case "get":
			val, ptr, err := queue.Pop() //从队列获取一个数据
			if err != nil {
				fmt.Println(err.Error())
			} else {
				fmt.Printf("t从队列取出了：array[%d]=%d", ptr, val)
				if queue.IsEmpty() {
					fmt.Printf("，数据已取完，队列为空~")
				}
				fmt.Println()
				fmt.Println()
			}
		case "show":
			queue.ShowQueue() //显示队列所有数据
			fmt.Println()
		case "exit":
			os.Exit(0) //退出程序
		default:
			fmt.Println("输入有误，请重新输入")
			key = "" //让说明菜单重新显示
		}
	}
}

数据结构分为线性结构和非线性结构，队列和线性表都是线性结构。线性表是由n 个数据元素组成的有限序列，该序列有惟一的“第一个”和惟一的“最后一个”数据元素；除了 “第一个”和“最后一个”之外，队列中的每个数据元素都只有一个直接前驱和一个直接后继。线性表的插入和删除操作可以在表中任意位置进行。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端ptrHead进行删除Pop()操作，而在表的后端ptrTail进行插入Push(val int)操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾(ptrTail)，进行删除操作的端称为队头(ptrHead)。队列中没有元素时，称为空队列(IsEmpty())。

队列的数据(array)元素又称为队列元素。在队列中插入一个队列(array[ptrTail] = val)元素称为入队，从队列中删除一个队列(val = t.array[ptrHead])元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

除非注明，网络人的文章均为原创，转载请以链接形式标明本文地址：https://www.55mx.com/post/88