网络人

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

Kwok: 2020-11-01 17:11:39 点击:5 评论: 0

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)元素又称为队列元素。在队列中插入一个队列(val = t.array[ptrHead])元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出FIFO—first in first out)线性表。

本文地址:http://m.neter8.com/go/88.html
标签:GO环形队列

本站推荐阅读

热门点击文章