重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
队列的概念在 顺序队列 中,而使用循环队列的目的主要是规避假溢出造成的空间浪费,在使用循环队列处理假溢出时,主要有三种解决方案
公司主营业务:网站制作、网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。创新互联建站是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联建站推出麦盖提免费做网站回馈大家。
本文提供后两种解决方案。
顺序队和循环队列是一种特殊的线性表,与顺序栈类似,都是使用一组地址连续的存储单元依次存放自队头到队尾的数据元素,同时附设队头(front)和队尾(rear)两个指针,但我们要明白一点,这个指针并不是指针变量,而是用来表示数组当中元素下标的位置。
本文使用切片来完成的循环队列,由于一开始使用三个参数的make关键字创建切片,在输出的结果中不包含nil值(看起来很舒服),而且在验证的过程中发现使用append()函数时切片内置的cap会发生变化,在消除了种种障碍后得到了一个四不像的循环队列,即设置的指针是顺序队列的指针,但实际上进行的操作是顺序队列的操作。最后是对make()函数和append()函数的一些使用体验和小结,队列的应用放在链队好了。
官方描述(片段)
即切片是一个抽象层,底层是对数组的引用。
当我们使用
构建出来的切片的每个位置的值都被赋为interface类型的初始值nil,但是nil值也是有大小的。
而使用
来进行初始化时,虽然生成的切片中不包含nil值,但是无法通过设置的指针变量来完成入队和出队的操作,只能使用append()函数来进行操作
在go语言中,切片是一片连续的内存空间加上长度与容量的标识,比数组更为常用。使用 append 关键字向切片中追加元素也是常见的切片操作
正是基于此,在使用go语言完成循环队列时,首先想到的就是使用make(type, len, cap)关键字方式完成切片初始化,然后使用append()函数来操作该切片,但这一方式出现了很多问题。在使用append()函数时,切片的cap可能会发生变化,用不好就会发生扩容或收缩。最终造成的结果是一个四不像的结果,入队和出队操作变得与指针变量无关,失去了作为循环队列的意义,用在顺序队列还算合适。
参考博客:
Go语言中的Nil
Golang之nil
Go 语言设计与实现
数组
数组是内置(build-in)类型,是一组同类型数据的集合。
数组的初始化有多种形式
长度为5的数组,其元素值依次为:1,2,3,4,5
长度为5的数组,其元素值依次为:1,2,0,0,0 。在初始化时没有指定初值的元素将会赋值为其元素类型int的默认值0,string的默认值是 ""
长度为5的数组,其长度是根据初始化时指定的元素个数决定的
长度为5的数组,key:value,其元素值依次为:0,0,1,2,3。在初始化时指定了2,3,4索引中对应的值:1,2,3
长度为5的数组,起元素值依次为:0,0,1,0,3。由于指定了最大索引4对应的值3,根据初始化的元素个数确定其长度为5
切片
数组的长度不可改变,在特定场景中这样的集合就不太适用,Go中提供了一种灵活,功能强悍的内置类型 Slices 切片。
切片可以通过数组来初始化,也可以通过内置函数make()初始化。初始化时len=cap,在追加元素时如果容量cap不足时将按len的 2 倍扩容。
直接初始化切片, [] 表示是切片类型, {1,2,3} 初始化值依次是1,2,3.其cap=len=3
初始化切片s,是数组arr的引用
将arr中从下标startIndex到endIndex-1 下的元素 创建为一个新的切片
缺省endIndex时将表示一直到arr的最后一个元素
缺省startIndex时将表示从arr的第一个元素开始
通过切片s初始化切片s1
通过内置函数make()初始化切片s,[]int 标识为其元素类型为int的切片
定义一个切片,然后让切片去引用一个已经创建好的数组。基本语法如下:
索引1:切片引用的起始元素位
索引2:切片只引用该元素位之前的元素
例程如下:
在该方法中,我们未指定容量cap,这里的值为5是系统定义的。
在方法一中,可以用arr数组名来操控数组中的元素,也可以通过slice切片来操控数组中的元素。切片是直接引用数组,数组是事先存在的,程序员是可见的。
通过 make 来创建切片,基本语法如下:
make函数第三个参数cap即容量是可选的,如果一定要自己注明的话,要注意保证cap≥len。
用该方法可以 指定切片的大小(len)和容量(cap)
例程如下:
由于未赋值系统默认将元素值置为0,即:
数值类型数组: 默认值为 0
字符串数组: 默认值为 ""
bool数组: 默认值为 false
在方法二中,通过make方式创建的切片对应的数组是由make底层维护,对外不可见,即只能通过slice去访问各个元素。
定义一个切片,直接就指定具体数组,使用原理类似于make的方式。
例程如下:
Go 中的分片数组,实际上有点类似于Java中的ArrayList,是一个可以扩展的数组,但是Go中的切片由比较灵活,它和数组很像,也是基于数组,所以在了解Go切片前我们先了解下数组。
数组简单描述就由相同类型元素组成的数据结构, 在创建初期就确定了长度,是不可变的。
但是Go的数组类型又和C与Java的数组类型不一样, NewArray 用于创建一个数组,从源码中可以看出最后返回的是 Array{}的指针,并不是第一个元素的指针,在Go中数组属于值类型,在进行传递时,采取的是值传递,通过拷贝整个数组。Go语言的数组是一种有序的struct。
Go 语言的数组有两种不同的创建方式,一种是显示的初始化,一种是隐式的初始化。
注意一定是使用 [...]T 进行创建,使用三个点的隐式创建,编译器会对数组的大小进行推导,只是Go提供的一种语法糖。
其次,Go中数组的类型,是由数值类型和长度两个一起确定的。[2]int 和 [3]int 不是同一个类型,不能进行传参和比较,把数组理解为类型和长度两个属性的结构体,其实就一目了然了。
Go中的数组属于值类型,通常应该存储于栈中,局部变量依然会根据逃逸分析确定存储栈还是堆中。
编译器对数组函数中做两种不同的优化:
在静态区完成赋值后复制到栈中。
总结起来,在不考虑逃逸分析的情况下,如果数组中元素的个数小于或者等于 4 个,那么所有的变量会直接在栈上初始化,如果数组元素大于 4 个,变量就会在静态存储区初始化然后拷贝到栈上。
由于数组是值类型,那么赋值和函数传参操作都会复制整个数组数据。
不管是赋值或函数传参,地址都不一致,发生了拷贝。如果数组的数据较大,则会消耗掉大量内存。那么为了减少拷贝我们可以主动的传递指针呀。
地址是一样的,不过传指针会有一个弊端,从打印结果可以看到,指针地址都是同一个,万一原数组的指针指向更改了,那么函数里面的指针指向都会跟着更改。
同样的我们将数组转换为切片,通过传递切片,地址是不一样的,数组值相同。
切片是引用传递,所以它们不需要使用额外的内存并且比使用数组更有效率。
所以,切片属于引用类型。
通过这种方式可以将数组转换为切片。
中间不加三个点就是切片,使用这种方式创建切片,实际上是先创建数组,然后再通过第一种方式创建。
使用make创建切片,就不光编译期了,make创建切片会涉及到运行期。1. 切片的大小和容量是否足够小;
切片是否发生了逃逸,最终在堆上初始化。如果切片小的话会先在栈或静态区进行创建。
切片有一个数组的指针,len是指切片的长度, cap指的是切片的容量。
cap是在初始化切片是生成的容量。
发现切片的结构体是数组的地址指针array unsafe.Pointer,而Go中数组的地址代表数组结构体的地址。
slice 中得到一块内存地址,array[0]或者unsafe.Pointer(array[0])。
也可以通过地址构造切片
nil切片:指的unsafe.Pointer 为nil
空切片:
创建的指针不为空,len和cap为空
当一个切片的容量满了,就需要扩容了。怎么扩,策略是什么?
如果原来数组切片的容量已经达到了最大值,再想扩容, Go 默认会先开一片内存区域,把原来的值拷贝过来,然后再执行 append() 操作。这种情况对现数组的地址和原数组地址不相同。
从上面结果我们可以看到,如果用 range 的方式去遍历一个切片,拿到的 Value 其实是切片里面的值拷贝,即浅拷贝。所以每次打印 Value 的地址都不变。
由于 Value 是值拷贝的,并非引用传递,所以直接改 Value 是达不到更改原切片值的目的的,需要通过 slice[index] 获取真实的地址。
new 主要用于结构体的初始化
make用于数组array,切片slice,协程chnnel的初始化
例如: users:=make([10]int);
msg:=make(chan int);
new会分配结构空间,并初始化为清空为零,不进一步初始化
new之后需要一个指针来指向这个结构
make会分配结构空间及其附属空间,并完成其间的指针初始化
make返回这个结构空间,不另外分配一个指针
例子new:
var p *[]int = new([]int)
或
p := new([]int)
以上分配了一个slice结构,但是结构中的应该指向底层数组的ptr指针为空,故实际不能往这个slice里面存取数据
同时分配了一个指针p,也即(在32位系统中)占4个字节并存放slice结构的地址
例子make:
var v []int = make([]int, 0)
v := make([]int, 0)
以上分配了一个slice结构,且结构中的应该指向底层数组的ptr指针已经指向了某个底层数组,这个底层数组应该已经分配了,故这个slice已经可以使用了
注意v就是这个slice结构,而不是一个指向slice的指针
上述仅是示例,一般使用时都会明确长度和容量:v := make([]int, 10, 50)
结论:
由上可见,用new来分配slice的意义不大,因为没有恰当的初始化,无法直接使用
有附带空间的结构,使用make来初始化,可以完成内部指针初始化,其后可以立即使用