[go学习笔记.第十八章.数据结构] 1.基本介绍,稀疏数组,队列(数组实现),链表
一.基本介绍
1.数据结构(算法)的介绍
(1).数据结构是一门研究算法的学科,自从有了编程语言也就有了数据结构,学好数据结构可以编写出更加漂亮,更加有效率的代码
(2).要学习好数据结构就要多多考虑如何将生活中遇到的问题用程序去实现解决
(3).程序= 数据结构 + 算法
2.数据结构和算法的关系
- 算法是程序的灵魂,为什么有些网站能够在高并发,在海量吞吐情况下依然坚如磐石,大家可能会说:网站使用了服务器群集技术、数据库读写分离和缓存技术(比如 redis等),那么如果再深入的问一句,这些优化技术又是怎样被那些天才的技术高手设计出来的呢?
- 大家请思考一个问题,是什么让不同的人写出的代码从功能看是一样的,但从效率上却有天壤之别,比如:我是做服务器的,环境是UNIX ,功能是要支持上千万人同时在线,并保证数据传输的稳定,在服务器上线前,做内侧,一切 OK.可上线后,服务器就支撑不住了,公司的CTO对我的代码进行优化,再次上线,坚如磐石,那一瞬间,我认识到程序是有灵魂的,就是算法.如果你不想永远都是代码工人,那就花时间来研究下算法
3.案例
(1).试写出用单链表表示的字符串类及字符串结点类的定义,并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数
代码如下:
func main() {var str string = "go, golang, hello world"str = strings.Replace(str, "go", "c", -1)fmt.Println(str)
}
(2).五子棋:如何判断游戏的输赢,并可以完成存盘退出和继续上局的功能
(3).约瑟夫问题(丢手帕问题)
设编号为 1 , 2 , … n 的 n 个人围坐一圈,约定编号为 k ( 1 <= k <= n)的人从 1 开始报数,数到m的那个人出列,它的下一位又从 1 开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列.
提示:
用一个不带头结点的循环链表来处理josephu问题,先构成一个有 n 个结点的单循环链表,然后由 k 结点起从 1 开始计数,计到m时,对应结点从链表中删除.然后再从被删除结点的下一个结点又从 1 开始计数,直到最后一个结点从链表中删除,算法结束.
(4).邮差问题
战争时期,胜利乡有7个村庄(A, B, C, D, E, F, G) ,现在有六个邮差,从G点出发,需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里
问:
如何计算出G村庄到 其它各个村庄的最短距离?如果从其它点出发到各个点的最短距离又是多少?
(5).最短路径问题
首先是迷宫的表示。如下图,起始位置是左上角黄色位置,重点位置是右下角黄色位置。在这个二维矩阵里,0表示道路通畅,可走;1表示有障碍物,不可走。最终计算出来的结果如右下角所示,从左上角0开始,每走一步,累加一次,这样就可以显示出整条路径的先后顺序。要走最短路径,只要从终点位置,不断递减1寻找上一步的位置直到回到起始位置即可.
(6).汉诺塔
假设这个游戏中有 3 个柱子,即 A、B 和 C,需要移动的是方块,其中一个柱子上已经有 N 个有序的方块,最大的在底部,方块按顺序越来越小。另外 2 个是空柱子。
基本条件:
- 一次只能移动一颗方块
- 小方块一定要在大方块上面
- 最终目标是将柱子上的所有方块移到另一根柱子上
(7).八皇后问题
- 首先定义一个8*8的棋盘
- 我们有八个皇后在手里,目的是把八个都放在棋盘中
- 位于皇后的水平和垂直方向的棋格不能有其他皇后
- 位于皇后的斜对角线上的棋格不能有其他皇后
- 解出能将八个皇后都放在棋盘中的摆法
二.稀疏数组
1.需求
编写五子棋程序,存盘退出和续上盘功能
分析:
上图中,二维数组中很多数都是默认值(0),因此纪录了很多没有意义的数据,故使用稀疏数组来进行处理
2.基本介绍
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组
稀疏数组的处理方法是:
(1).记录数组一共有几行几列,有多少个不同的值
(2).把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
3.应用实例
(1).使用稀疏数组,来保留类似前面的二维数组棋盘、地图等等)
(2).把稀疏数组存盘,并且可以从新恢复原来的二维数组数
(3).整休思路分析(4).代码实现
代码如下:
package mainimport("fmt""os""bufio""io""strings""strconv"
)type ValNode struct {row int col intval int
}//编写五子棋程序, 有存盘退出和续上盘的功能
func main() {//1.先创建一个原始数组var chessMap [11][11]intchessMap[1][2] = 1 //黑子chessMap[2][3] = 2 //蓝子//2.输出原始数组看看for _, v := range chessMap {for _, v2 := range v {fmt.Printf("%d\t", v2)}fmt.Println()}//3.转换成稀疏数组//思路://1).遍历chessMap,如果发现有一个元素不为零,创建一个node结构体//2).将其放入对应的切片即可//定义切片var spaseArr []ValNode//标准的一个稀疏数组应该还有一个记录元素的二维数组的规模(行和列,默认值)//创建一个ValNode节点valNode := ValNode {row: 11,col: 11,val: 0,}//追加到spaseArr切片中spaseArr = append(spaseArr, valNode)//循环chessMap,把不为零的元素放到spaseArr中for i, v := range chessMap {for j, v2 := range v {if v2 != 0 {//创建一个ValNode 值节点valNode = ValNode{row: i,col: j,val: v2,}spaseArr = append(spaseArr, valNode)}}}//输出稀疏数组fmt.Println("当前的稀疏数组为:")for i, valNode := range spaseArr {fmt.Printf("%d: %d %d %d\n", i, valNode.row, valNode.col, valNode.val)}//将稀疏数组存盘//创建一个新文件//打开一个文件 "f:/www/test2.txt"filePath := "f:/www/chessMap.data"file, err := os.OpenFile(filePath, os.O_WRONLY | os.O_CREATE, 0666)if err != nil {fmt.Printf("open file err =%v\n", err)}//及时关闭filedefer file.Close()var content string//准备写入writer := bufio.NewWriter(file)for _, valNode := range spaseArr {content = fmt.Sprintf("%d %d %d\n", valNode.row, valNode.col, valNode.val)writer.WriteString(content)}writer.Flush()//把存盘的稀疏数组恢复到原始数组//创建一个原始数组var chessMap2 [11][11]int//打开文件,遍历每一行数据file, err = os.Open(filePath)if err != nil {fmt.Println("os.Open file fail, err = ", err)}defer file.Close()//创建一个Readerreader := bufio.NewReader(file)//循环读取reader里的内容//文件中第一行数据过滤掉i := 1for {str, err := reader.ReadString('\n')if err == io.EOF { //读到文件末尾就退出break}if i == 1 {i++continue}//通过空格切割字符串,并转换成数组arr := strings.Fields(string(str))row, err := strconv.ParseInt(arr[0], 10, 64)col, err := strconv.ParseInt(arr[1], 10, 64)val, err := strconv.ParseInt(arr[2], 10, 64)chessMap2[row][col] = int(val)}//打印稀疏数组for _, v := range chessMap2 {for _, v2 := range v {fmt.Printf("%d\t", v2)}fmt.Println()}
}
三.队列(数组实现)
1.队列的应用场景
银行排队案例:
2.队列介绍
队列是一个有序列表,可以用数组或是链表来实现.遵循先入先出的原则。即:先存入队列的数据,要先取出,后存入的要后取出示意图,使用数组模拟队列示意图如下:
3.数组模拟队列
队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下:其中 maxSize 是该队列的最大容量
因为队列的输出、输入是分别从前后端来处理,因此需要两个变量front及rear分别记录队列前后端的下标, front 会随着数据输出而改变,而rear则是随着数据输入而改变,如图所示:
将数据存入队列时称为"addqueue", addqueue 的处理需要有两个步骤
(1).将尾指针往后移: rear + 1 , front ==real [空]
(2).若尾指引 rear 小于等于队列的最大下标 MaxSize -1, 则将数据存入 rear 所指的数组元素,否则无法存入数据
package mainimport ("fmt""errors""os"
)//定义一个结构体,存放队列相关数据
type Queue struct {maxSize int //队列最大数array [5]int // 数组=>模拟队列front int //指向队列首部 rear int //指向队列尾部
}//添加队列数据
func (this *Queue) AddQueue(val int) (err error) {//判断队列是否已满if this.maxSize -1 == this.rear { // rear是队列尾部(含最后一个元素)return errors.New("queue full")} this.rear++ //rear后移this.array[this.rear] = valreturn
}//显示队列:找到队首,然后遍历
func (this *Queue) ShowQueue () {fmt.Println("队列当前情况:")//this.front是不包含队首的元素for i := this.front + 1; i <= this.rear; i++ {fmt.Printf("arrar[%d]=%d\n", i, this.array[i])}
}//从队列中取出数据
func (this *Queue) GetQueue() (val int, err error) {//先判断队列是否为空if this.rear == this.front { //队列为空了return -1, errors.New("queue empty")}this.front++val = this.array[this.front]return val, err
}func main() {//先创建一个队列queue := &Queue {maxSize: 5,front: -1,rear: -1,}var key stringvar val intfor {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.AddQueue(val)if err != nil {fmt.Println(err.Error())} else {fmt.Println("加入队列成功")}case "get":val, err := queue.GetQueue()if err != nil {fmt.Println(err.Error())} else {fmt.Printf("从队列中取出的数为:%d\n", val)}case "show":queue.ShowQueue()case "exit":os.Exit(0)default:fmt.Println("输入有误,请重新输入")}}
}
对上面代码的小节和说明:
(1).上面代码实现了基本队列结构,但是役有有效的利用数组空间
(2).请思考:如何使用数组实现一个环形的队列
4.环形数组队列
对前面的数组模拟队列的优化,充分利用数组,因此将数组看做是一个环形的( 通过取模的方式来实现即可)
提醒:
(1).尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意(tail+1)%maxSize == head(满)
(2).tail == head (空)
分析思路:
(1).什么时候表示队列满? (tail+1)%maxSize == head
(2).什么时候表示队列空? tail == head
(3).初始化时,tail == 0,head == 0
(4).怎么统计该队列有多少个元素? (tail + maxSize - head) % maxSize
代码如下:
package mainimport("fmt""errors""os"
)//定义一个结构体管理环形队列
type CircleQueue struct{ maxSize int //队列最大值:5array [5]int //使用数组 =>队列head int //指向队列队首:0tail int //指向队列队尾:0
}//入队列 AddQueue(push)
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 = (this.tail + 1) % this.maxSizereturn
}//出队列 GetQueue(pop)
func (this *CircleQueue) Pop() (val int, err error) {//判断环形队列是否为空if this.IsEmpty() {return 0, errors.New("queue empty")}//取出:head是指向队首,并且含队首元素val = this.array[this.head]this.head = (this.head + 1) % this.maxSizereturn val, err
}//判断环形队列是否满了
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 (this *CircleQueue) ListQueue() {fmt.Println("环形队列情况如下:")//取出当前队列有多少个元素size := this.Size()if size == 0 {fmt.Println("队列为空")}//定义一个临时变量,指向headtempHead := this.headfor i := 0; i < size; i++ {fmt.Printf("array[%d] = %d\n", tempHead, this.array[tempHead])tempHead = (tempHead + 1) % this.maxSize}}
func main() {//先创建一个队列queue := &CircleQueue {maxSize: 5,head: 0,tail: 0,}var key stringvar val intfor {fmt.Println("1. 输入push,表示添加数据到队列")fmt.Println("2. 输入pop,表示从队列获取数据")fmt.Println("3. 输入list,表示显示队列")fmt.Println("4. 输入exit,表示退出队列")fmt.Scanln(&key)switch key {case "push":fmt.Println("输入要入队的对数:")fmt.Scanln(&val)err := queue.Push(val)if err != nil {fmt.Println(err.Error())} else {fmt.Println("加入队列成功")}case "pop":val, err := queue.Pop()if err != nil {fmt.Println(err.Error())} else {fmt.Printf("从队列中取出的数为:%d\n", val)}case "list":queue.ListQueue()case "exit":os.Exit(0)default:fmt.Println("输入有误,请重新输入")}}
}
四.链表
1.链表的介绍
链表是有序的列表,它在内存中的存储如下
2.单链表的介绍
示意图如下:
说明: 一般来说,为了比较好的对单链表进行增删改查的操作,都会给其设置一个头结点,头结点的作用主要是用来标识链表头,本身这个结点不存放数据
3.单链表的应用实例
使用带 head 头的单向链表实现\:水浒英雄排行榜管理
完成对英雄人物的增删改查操作
在添加英雄时,直接添加到链表的尾部
package mainimport ("fmt"
)//定义一个HeroNode结构体
type HeroNode struct {no intname stringnickname stringnext *HeroNode //表示指向下一个结点
}//给链表插入一个结点
//编写第一种插入方式:在单链表的最后插入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {//1.先找到链表最后这个结点//2.创建一个辅助结点temp := headfor {if temp.next == nil { //表示找到了最后break}temp = temp.next //让temp不断指向下一个结点}//当for结束时,temp一定是找到了最后一个节点的//3.将newHeroNode加入道最后temp.next = newHeroNode
}//编写第二种插入方式: 根据no的编号从小到大插入
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {//1.先找适当的结点//2.创建一个辅助结点temp := headflag := true//让插入结点的no和temp的下一个结点的no比较for {if temp.next == nil { //表示到了最后的链表break} else if temp.next.no > newHeroNode.no {//说明newHeroNode就应该插入到temp后面break} else if temp.next.no == newHeroNode.no {//说明链表中已经有这个no,就不允许插入了flag = falsebreak}temp = temp.next //让temp不断指向下一个结点}if !flag {fmt.Println("已存在no=", newHeroNode.no)return} else {newHeroNode.next = temp.nexttemp.next = newHeroNode}
}//显示链表的所有结点信息
func ListHeroNode(head *HeroNode) {//1.创建一个辅助结点temp := head//先判断该链表是不是空的链表if temp.next == nil { fmt.Println("空的链表")return}//2.遍历链表for {fmt.Printf("[%d, %s, %s] ==> ", temp.next.no, temp.next.name, temp.next.nickname)//判断链表是否最后temp = temp.nextif temp.next == nil {break}}
}//删除一个结点
func DelHeroNode(head *HeroNode, id int) {temp := headflag := false//找到要删除的结点的no,和temp的下一个结点的no比较for {if temp.next == nil {//说明到了链表的最后break} else if temp.next.no == id {//说明找到了flag = truebreak}temp = temp.next}if flag {//找到了,就行删除操作temp.next = temp.next.next // 这样目标结点就会成为一个垃圾结点,被系统回收} else {fmt.Println("要删除的结点id不存在")}
}
func main() {//1.先创建一个头结点head := &HeroNode{}//2.创建一个新的结点head1 := &HeroNode{no: 1,name: "宋江",nickname: "及时雨",}head2 := &HeroNode{no: 2,name: "陆静怡",nickname: "玉骑铃",}head3 := &HeroNode{no: 3,name: "零充",nickname: "包子头",}//3.加入//第一种方法// InsertHeroNode(head, head1)// InsertHeroNode(head, head3)// InsertHeroNode(head, head2)//第二种方法InsertHeroNode2(head, head1)InsertHeroNode2(head, head3)InsertHeroNode2(head, head2)//4.列表ListHeroNode(head)//5.删除fmt.Println()DelHeroNode(head, 2)ListHeroNode(head)
}
4.双向链表的应用实例
使用带 head 头的双向链表实现:水浒英雄排行榜管理
单向链表的缺点分析:
(1).单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找
(2).单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面单链表删除时节点,总是找到 temp 的下一个节点来删除
package mainimport ("fmt"
)//定义一个HeroNode结构体
type HeroNode struct {no intname stringnickname stringpre *HeroNode //表示指向上一个结点next *HeroNode //表示指向下一个结点
}//给链表插入一个结点
//编写第一种插入方式:在链表的最后插入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {//1.先找到链表最后这个结点//2.创建一个辅助结点temp := headfor {if temp.next == nil { //表示找到了最后break}temp = temp.next //让temp不断指向下一个结点}//当for结束时,temp一定是找到了最后一个节点的//3.将newHeroNOde加入道最后temp.next = newHeroNode//4.再将temp指向newHeroNode.prenewHeroNode.pre = temp
}//编写第二种插入方式: 根据no的编号从小到大插入
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {//1.先找适当的结点//2.创建一个辅助结点temp := headflag := true//让插入结点的no和temp的下一个结点的no比较for {if temp.next == nil { //表示到了最后的链表break} else if temp.next.no > newHeroNode.no {//说明newHeroNode就应该插入到temp后面break} else if temp.next.no == newHeroNode.no {//说明链表中已经有这个no,就不允许插入了flag = falsebreak}temp = temp.next //让temp不断指向下一个结点}if !flag {fmt.Println("已存在no=", newHeroNode.no)return} else {newHeroNode.next = temp.nextnewHeroNode.pre = tempif temp.next != nil {temp.next.pre = newHeroNode}temp.next = newHeroNode}
}//显示链表的所有信息:顺序方式
func ListHeroNode(head *HeroNode) {//1.创建一个辅助结点temp := head//先判断该链表是不是空的链表if temp.next == nil { fmt.Println("空的链表")return}//2.遍历链表for {fmt.Printf("[%d, %s, %s] ==> ", temp.next.no, temp.next.name, temp.next.nickname)//判断链表是否最后temp = temp.nextif temp.next == nil {break}}
}//显示链表的所有信息:逆序方式
func ListHeroNode2(head *HeroNode) {//1.创建一个辅助结点temp := head//先判断该链表是不是空的链表if temp.next == nil { fmt.Println("空的链表")return}//2.让temp定位到双向链表的最后结点for {if temp.next == nil {break}temp = temp.next}//2.遍历链表for {fmt.Printf("[%d, %s, %s] <== ", temp.no, temp.name, temp.nickname)//判断链表是否到headtemp = temp.preif temp.pre == nil {break}}
}//删除一个结点
func DelHeroNode(head *HeroNode, id int) {temp := headflag := false//找到要删除的结点的no,和temp的下一个结点的no比较for {if temp.next == nil {//说明到了链表的最后break} else if temp.next.no == id {//说明找到了flag = truebreak}temp = temp.next}if flag {//找到了,就行删除操作temp.next = temp.next.next // 这样目标结点就会成为一个垃圾结点,被系统回收if temp.next != nil { //当下一个结点存在时,才操作temp.next.pre = temp}} else {fmt.Println("要删除的结点id不存在")}
}
func main() {//1.先创建一个头结点head := &HeroNode{}//2.创建一个新的结点head1 := &HeroNode{no: 1,name: "宋江",nickname: "及时雨",}head2 := &HeroNode{no: 2,name: "陆静怡",nickname: "玉骑铃",}head3 := &HeroNode{no: 3,name: "零充",nickname: "包子头",}//3.加入//第一种方法InsertHeroNode(head, head1)InsertHeroNode(head, head2)InsertHeroNode(head, head3)//第二种方法// InsertHeroNode2(head, head1)// InsertHeroNode2(head, head3)// InsertHeroNode2(head, head2)// //4.列表//顺序ListHeroNode(head)fmt.Println()//逆序ListHeroNode2(head)// //5.删除// fmt.Println()DelHeroNode(head, 2)ListHeroNode(head)
}
5.单向环形链表的应用场景
josephu 问题:
设编号为1, 2 ,... n 的n个人围坐一圈, 约定编号为 k (1<=k<=n )的人从 1 开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到 m 的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列
提示:
用一个不带头结点的循环链表来处理josephu问题,先构成一个有 n 个结点的单循环链表,然后由 k 结点起从1开始计数,计到 m 时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从 1 开始计数,直到最后一个结点从链表中删除,算法结束
6.环形单向链表的介绍
7.环形单向链表应用案例
完成对单向环形链表的添加结点,删除结点和显示
删除一个环形单向琏表的思路如下:
1.先让 temp 指向 head
2.让 helper 指向环形链表最后
3.让temp 和要删除的id进行比较,如果相同,则同helper完成删除(这里必须考虑如果删除的就是头结点)
package mainimport ("fmt"
)//定义一个CatNode结构体
type CatNode struct {no int //猫的编号name string //名字next *CatNode //下一个结点
}//插入环形链表
func InsertCatNode(head *CatNode, newCatNode *CatNode) {//判断是不是添加第一只猫if head.next == nil {head.no = newCatNode.nohead.name = newCatNode.namehead.next = head // 构成一个环形fmt.Println(newCatNode, "加入到环形的链表")return } //先定义一个临时的变量,找到环形的最后结点temp := headfor {if temp.next == head {break}temp = temp.next}//加入到链表temp.next = newCatNodenewCatNode.next = head
}//显示环形链表
func ListCircleLink(head *CatNode) {temp := headif temp.next == nil {fmt.Println("空的链表")return}for {fmt.Printf("猫的信息为:no=%d,name=%s, =>\n", temp.no, temp.name)if temp.next == head {//说明链表环状查询完毕break}temp = temp.next}
}//删除
func DelCircleCatNode(head *CatNode, id int) *CatNode {temp := headhelper := head//空链表if temp.next == nil {fmt.Println("空链表")return head}//如果只有一个结点if temp.next == head {temp.next = nilreturn head}//将helper定位到环形链表最后for {if helper.next == head {break}helper = helper.next}//如果有两个以及以上的结点flag := truefor {if temp.next == head { //说明已经比较到最后一个(最后一个还没比较)break}if temp.no == id { // 找到了if temp == head { // 说明删除的是头结点head = temp.next}//可以在这里删除helper.next = temp.nextfmt.Printf("猫:%d已经被删除了\n", id)flag = falsebreak}temp = temp.next // 移动,目的是为了 "比较"helper = helper.next // 移动,目的是为了删除结点}//这里还要比较一次if flag { // 如果flag为true,则上面没有删除if temp.no == id {helper.next = temp.nextfmt.Printf("猫:%d已经被删除了\n", id)} else {fmt.Printf("没有该猫,no=%d\n", id)}}return head
}
func main() {//初始化一个环形链表的头结点head := &CatNode{}//创建一只猫cat1 := &CatNode{no: 1,name: "tom",}cat2 := &CatNode{no: 2,name: "jack",}cat3 := &CatNode{no: 3,name: "mary",}InsertCatNode(head, cat1)InsertCatNode(head, cat2)InsertCatNode(head, cat3)ListCircleLink(head)head = DelCircleCatNode(head, 2)ListCircleLink(head)
}
创建一个链表模拟队列,实现数据入队列,数据出队列,显示队列
package mainimport ("fmt""errors""os"
)//定义一个结构体管理环形队列
type CircleQueue struct {maxSize int //队列最大值:5array [5]int //使用数组 =>队列head int //指向队列队首:0tail int //指向队列队尾:0
}//入队列 AddQueue(push)
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 = (this.tail + 1) % this.maxSizereturn
}//出队列 GetQueue(pop)
func (this *CircleQueue) Pop() (val int, err error) {//判断环形队列是否为空if this.IsEmpty() {return 0, errors.New("queue empty")}//取出:head是指向队首,并且含队首元素val = this.array[this.head]this.head = (this.head + 1) % this.maxSizereturn val, err
}//判断环形队列是否满了
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 (this *CircleQueue) ListQueue() {fmt.Println("环形队列情况如下:")//取出当前队列有多少个元素size := this.Size()if size == 0 {fmt.Println("队列为空")}//定义一个临时变量,指向headtempHead := this.headfor i := 0; i < size; i++ {fmt.Printf("array[%d] = %d\n", tempHead, this.array[tempHead])tempHead = (tempHead + 1) % this.maxSize}}
func main() {//先创建一个队列queue := &CircleQueue{maxSize: 5,head: 0,tail: 0,}var key stringvar val intfor {fmt.Println("1. 输入push,表示添加数据到队列")fmt.Println("2. 输入pop,表示从队列获取数据")fmt.Println("3. 输入list,表示显示队列")fmt.Println("4. 输入exit,表示退出队列")fmt.Scanln(&key)switch key {case "push":fmt.Println("输入要入队的对数:")fmt.Scanln(&val)err := queue.Push(val)if err != nil {fmt.Println(err.Error())} else {fmt.Println("加入队列成功")}case "pop":val, err := queue.Pop()if err != nil {fmt.Println(err.Error())} else {fmt.Printf("从队列中取出的数为:%d\n", val)}case "list":queue.ListQueue()case "exit":os.Exit(0)default:fmt.Println("输入有误,请重新输入")}}
}
[上一节][go学习笔记.第十七章.redis的使用] 1.redis的使用
相关文章:

[附源码]计算机毕业设计校园服装租赁系统Springboot程序
项目运行 环境配置: Jdk1.8 Tomcat7.0 Mysql HBuilderX(Webstorm也行) Eclispe(IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持)。 项目技术: SSM mybatis Maven Vue 等等组成,B/S模式 M…...

详解C语言二级指针三种内存模型
二级指针相对于一级指针,显得更难,难在于指针和数组的混合,定义不同类型的二级指针,在使用的时候有着很大的区别 第一种内存模型char *arr[] 若有如下定义 char *arr[] {"abc", "def", "ghi"};…...

List——顺序表与链表(二)
文章目录前言一、链表概念及结构二、LinkedList与链表1.什么是LinkedList2.LinkedList的常用方法3.链表的遍历三.实现自己的LinkedList四.ArrayList和LinkedList的区别与优缺点总结前言 上一篇文章中,介绍了List接口以及ArrayList的使用,并且进行了简单…...

PCB入门介绍与电阻电容电感类元件的创建
摘自凡亿教育 目录 一、PCB入门介绍 二、电阻电容电感类元件的创建 1.绘制电阻的原理图库 2.绘制电容的原理图库 3.绘制电感的原理图 一、PCB入门介绍 1.EDA工具 Cadence Allegro :IC-芯片设计 Mentor PADS:做消费类电子产品、手机、机顶盒、平板电脑 Altium Designer…...

MongoDB入门与实战-第五章-MongoDB副本集
目录参考一、副本集概念1、**主要功能**2、主从复制和副本集区别3、复制结构图二、副本集成员角色1.主节点2.副本节点3.仲裁节点三、副本集架构(一主一副本一仲裁)1、**设置读操作权限:**2、取消作为奴隶节点的读权限四、选举原则1、触发条件…...

[YOLOv7/YOLOv5系列改进NO.40]融入适配GPU的轻量级 G-GhostNet
文章目录前言一、解决问题二、基本原理三、添加方法四、总结前言 作为当前先进的深度学习目标检测算法YOLOv7,已经集合了大量的trick,但是还是有提高和改进的空间,针对具体应用场景下的检测难点,可以不同的改进方法。此后的系列…...

Windows x64隐藏可执行内存
文章目录实现效果实现原理VAD内存什么是VAD内存查看VAD内存VAD属性VAD内存可利用的点x64分页机制W7 x64下任意地址PDT PTE算法W10 x64定位随机化页表基址实现隐藏可执行内存隐藏内存对抗实现效果 驱动程序在Test进程中申请一块内存地址并打印,然后控制台程序在接收到…...

map容器/multimap容器
目录 1.map基本概念 简介 本质 优点 map和multimap区别 2.map构造和赋值 功能描述: 函数原型 3.map大小和交换 功能描述 函数原型 4 map插入和删除 功能描述 函数原型 5. map查找和统计 功能描述 函数原型 6 map容器排序 学习目标 主要技术点 1.map基本概念…...

SpringBoot+Vue项目便捷洗衣服务平台
文末获取源码 开发语言:Java 使用框架:spring boot 前端技术:JavaScript、Vue.js 、css3 开发工具:IDEA/MyEclipse/Eclipse、Visual Studio Code 数据库:MySQL 5.7/8.0 数据库管理工具:phpstudy/Navicat JD…...

[激光原理与应用-36]:《光电检测技术-3》- 光学测量基础 - 光电效应与光电探测器的基本原理
目录 一、概述 二、光电检测的理论基础:光电效应 三、分类 3.1 光子效应 3.2 热效应 四、光电检测器的参数 五、常见的光电探测器 5.1 光电倍增管:微弱光信号转换成电信号 5.2 光电导器件:电阻或电流随着光强的变化而变化 5.3 光伏…...

给定一个字符串str,求最长回文子序列长度。
问题描述: 给定一个字符串str,求最长回文子序列长度。 思想: 思想一: 根据回文串的性质,我们可以生成一个新的字符串,新字符串的顺序是原来字符串的倒序。本题可以转化为两个字符串求最长的公共子序列。 …...

40 个机器学习面试问题(文末福利送书)
原创 文章目录初学者问题 (10)1. 偏差和方差之间的权衡是什么?2.解释有监督和无监督机器学习的区别3. 监督学习和无监督学习最常用的算法是什么?4.解释KNN和k-means聚类的区别5. 什么是贝叶斯定理?我们为什么用它?6. 什么是朴素贝…...

Springboot流浪动物管理系统p2326计算机毕业设计-课程设计-期末作业-毕设程序代做
Springboot流浪动物管理系统p2326计算机毕业设计-课程设计-期末作业-毕设程序代做 【免费赠送源码】Springboot流浪动物管理系统p2326计算机毕业设计-课程设计-期末作业-毕设程序代做本源码技术栈: 项目架构:B/S架构 开发语言:Java语言 开…...

Request和Response基础知识入门
文章目录1,Request和Response的概述2,Request对象2.1 Request继承体系2.2 Request获取请求数据2.2.1 获取请求行数据2.2.2 获取请求头数据2.2.3 获取请求体数据2.2.4 获取请求参数的通用方式2.3 IDEA快速创建Servlet2.4 请求参数中文乱码问题2.4.1 POST请…...

实战Docker未授权访问提权
1、fofa关键字 port“2375” && body“page not found” 2、docker -H tcp://ip:port 可查看到当前所有的实例 3、docker -H tcp://ip:port pull alpine 4、docker -H tcp://ip:port run -it --privileged alpine bin/sh 5、fdisk -l 查看其分区结构 6、创建一个…...

【微信小程序】页面跳转、组件自定义、获取页面参数值
🏆今日学习目标:第十七期——页面跳转、组件自定义、获取页面参数值 😃创作者:颜颜yan_ ✨个人主页:颜颜yan_的个人主页 ⏰预计时间:25分钟 🎉专栏系列:我的第一个微信小程序 文章目…...

数据结构:二叉树的链式结构
文章目录一.前言二.二叉树遍历2.1前序遍历/先根遍历2.2中序遍历/中根遍历2.3后序遍历/后根遍历2.4层序遍历2.5二叉树的销毁三.二叉树节点个数四.二叉树叶子节点的个数五.二叉树的高度六.二叉树第K层的节点个数七.找二叉树的节点八.题目8.1判断单值二叉树8.2相同的树8.3另一棵子…...

[附源码]计算机毕业设计小区疫情事件处理系统Springboot程序
项目运行 环境配置: Jdk1.8 Tomcat7.0 Mysql HBuilderX(Webstorm也行) Eclispe(IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持)。 项目技术: SSM mybatis Maven Vue 等等组成,B/S模式 M…...

03、自定义镜像上传阿里云
目录 1、alpine Linux简介 2、基于alpine制作JDK8镜像 1.1 下载镜像 1.2 创建并编辑dockerfile 1.3 执行dockerfile创建镜像 1.4 创建并启动容器 1.5 进入容器 1.6 测试jdk 3、Docker容器之最小JRE基础镜像 4、将Docker镜像上传至阿里云(或从阿云下载镜像) 5、Docke…...

机器学习之过拟合和欠拟合
文章目录前言什麽是过拟合和欠拟合?过拟合和欠拟合产生的原因:欠拟合(underfitting):过拟合(overfitting):解决欠拟合(高偏差)的方法1、模型复杂化2、增加更多的特征,使输入数据具有更强的表达能力3、调整参数和超参数4、增加训练…...

【Linux网络编程】服务端编程初体验
文章目录前言服务端是啥、有什么特点核心函数socket的简介服务器编程客户端代码The End前言 在上节课(Linux网络编程初体验)中我们实现了连接bilibili的功能,并获取其html源码 如图所示. 今天我们要自己编写个服务端来服务我们的客户端 提示:以下是本篇…...

《人类简史》笔记四—— 想象构建的秩序
目录 一、盖起金字塔 1、未来的来临 2、 由想象构建的秩序 3、如何维持构建的秩序 二、 记忆过载 三、亚当和夏娃的一天 一、盖起金字塔 1、未来的来临 原始社会: 人口少; 狩猎和采集; 整体活动范围大(有几十甚至上百平方…...

TIDB在centos7.9上通过docker-compose进行安装、备份
1.环境介绍: 在centos7.9上安装tidb docker-compose版本 虚拟机配置2C/8G/40G 最小化安装 2.安装步骤 2.1 安装centos7.9 略 2.2 安装docker (1)安装依赖包 yum install -y yum-utils device-mapper-persistent-data lvm2(2…...

Spring中Bean的生命周期
先直接说出过程,再来演示具体的操作 过程 简化来说就是 1、首先是实例化Bean,当客户向容器请求一个尚未初始化的bean时,或初始化bean的时候需要注入另一个尚末初始化的依赖时,容器就会调用doCreateBean()方法进行实例化…...

ACM第三周---周训---题目合集.
🚀write in front🚀 📝个人主页:认真写博客的夏目浅石.CSDN 🎁欢迎各位→点赞👍 收藏⭐️ 留言📝 📣系列专栏:ACM周训练题目合集.CSDN 💬总结:…...

VUE+Spring Boot前后端分离开发实战(六):基于RABC权限通用后台管理系统-给角色动态分配权限和用户
文章目录 前言功能设计后端实现前端实现写在后面前言 本文记录了通用后台管理系统中RABC权限中两个功能:给角色分配权限、给角色设置用户。 给角色分配用户:前端使用到了elementUI中的tree,包括加载树以及给已选配权限给默认值等。给角色设置用户:前端用到了elementUI中的…...

Dockerfile自定义镜像实操【镜像结构、Dockerfile语法、构建Java项目】
要自定义镜像,就必须先了解镜像的结构才行。 1 镜像结构 镜像是将应用程序及其需要的系统函数库、环境、配置、依赖打包而成。 以MySQL为例,镜像的组成结构: 简单讲,镜像就是在系统函数库、运行环境基础上,添加应用…...

javaScript 进阶之路 --- 《加深理解回调函数》
前言: 回想当初第一次看到“回调函数”这个名词的时候,真的快把我难哭了。所有视频教程在讲到某个知识点的时候,大概都会说一句:“啊,这里怎么办呢?这里我们就需要用到一个回调函数...”。 等等࿰…...

Linux开发常用ps命令选项详解
【摘要】本文介绍了在Linux应用/内核开发调试中,经常需要用到的两个选项组合,当然,如果你需要查看更多更详尽的选项说明,可以参考man说明文档,即命令行下输入man ps进行查看。 aux选项组合 使用场景:更多…...

【ceph】分布式存储ceph
1 块存储,文件存储,对象存储 1.1 简介 文件存储:分层次存储,文件存储在文件夹中;访问文件时系统需要知道文件所在的路径。 举例:企业部门之间运用网络存储器(NAS)进行文件共享。 …...

Spring框架(九):Spring注解开发Annotation
Spring注解开发引子如何用注解替代xml基础配置Bean可以加一些注解来实现原有的xml文件的功能Component注解及其衍生注解依赖注入AutowireSpring非自定义的注解开发Spring其他注解注解的原理解析-xml方式注解的原理解析-注解方式引子 痛定思痛,主要问题出现在自己雀…...

python隶属关系图模型:基于模型的网络中密集重叠社区检测方法
隶属关系图模型 是一种生成模型,可通过社区联系产生网络。下图描述了一个社区隶属关系图和网络的示例(图1)。最近我们被客户要求撰写关于社区检测的研究报告,包括一些图形和统计输出。 图1.左:社区关系图(圆…...

Java实现猜数游戏
1 问题 编写一个Java程序,实现以下功能: 2 方法 首先导入java.util包下的Random,让程序随便分配给用户一个数。 再导入java.util包下的Scanner类,构建Scanner对象,以便输入。 利用Random().nextInt()生成一个随机的i…...

阿里云安装mysql、nginx、redis
目录 安装mysql 安装nginx 编辑安装redis 先看一下系统基本信息 安装mysql rpm -qa | grep mariadb 卸载mariadb rpm -e --nodeps mariadb-libs-5.5.68-1.el7.x86_64 下载mysql源 wget -i http://dev.mysql.com/get/mysql57-community-release-el7-10.noarch.rpm yum…...

毕业设计-基于机器视觉的行人车辆跟踪出入双向检测计数
目录 前言 课题背景和意义 实现技术思路 实现效果图样例 前言 📅大四是整个大学期间最忙碌的时光,一边要忙着备考或实习为毕业后面临的就业升学做准备,一边要为毕业设计耗费大量精力。近几年各个学校要求的毕设项目越来越难,有不少课题是研究生级别难度的,对本科…...

linux 安装nginx
1.安装依赖包 //一键安装上面四个依赖 yum -y install gcc zlib zlib-devel pcre-devel openssl openssl-devel 2.下载并解压安装包 /或上传解压包 //创建一个文件夹 cd /usr/local mkdir nginx cd nginx //下载tar包 wget http://nginx.org/download/nginx-1.13.7.tar.gz t…...

javaee之黑马旅游网1
这是一个用来锻炼javaweb基础知识的项目,先来导入一些我们准备好的文件 下面这些东西是我们项目必备的,我们提前准备好了 ,这个我会上传到我的资源,你们可以自己去下载 利用maven来创建一个项目 选择无骨架创建项目,域…...

【高并发基础】理解 MVCC 及提炼实现思想
文章目录1. 前言2. MVCC 概念2.1 MVCC 版本链2.2 MVCC trx_id2.3 MVCC Read View3. 提出问题4. 解决问题4.1 不读未提交的数据4.1.1 一般的并发情况4.1.2 特殊的并发情况4.1.3 剩下的并发情况4.2 如果自己修改了数据,要第一时间读到5. MySQL RC 使用 MVCC5.1 MVCC D…...

Flow-vue源码中的应用
认识 Flow Flow 是 facebook 出品的 JavaScript 静态类型检查工具。Vue.js 的源码利用了 Flow 做了静态类型检查,所以了解 Flow 有助于我们阅读源码。 #为什么用 Flow JavaScript 是动态类型语言,它的灵活性有目共睹,但是过于灵活的副作用…...

学习python第一天(数据类型)
关于Python的数据类型 Python数据类型包括: 数字类型,字符类型,布尔类型,空类型,列表类型,元组类型,字典类型 1、数字类型 包括:整型int 浮点型float(有小数位的都是是浮点型) 注…...

echarts:nuxt项目使用echarts
一、项目环境 nuxt 2.X vue2.X vuex webpack 二、安装 yarn add echarts 三、使用 3.1、plugins目录下创建echarts.js import Vue from vue import * as echarts from echarts // 引入echarts Vue.prototype.$echarts echarts // 引入组件(将echarts注册为全…...

认证服务-----技术点及亮点
大技术 Nacos做注册中心 把新建的微服务注册到Nacos上去 两个步骤 在配置文件中配置应用名称、nacos的发现注册ip地址,端口号在启动类上用EnableDiscoveryClient注解开启注册功能 使用Redis存验证码信息 加入依赖配置地址和端口号即可 直接注入StringRedisTempla…...

【计算机毕业设计】74.家教平台系统源码
一、系统截图(需要演示视频可以私聊) 摘 要 21世纪的今天,随着社会的不断发展与进步,人们对于信息科学化的认识,已由低层次向高层次发展,由原来的感性认识向理性认识提高,管理工作的重要性已逐…...

Hbase的SQL接口之Phoenix使用心得
PHOENIX 官方定义 A SQL layer over HBase delivered as a client-embedded JDBC drivertargeting low latency queries over HBase data 不同于Hive on HBase的方式,Phoenix将Query Plan直接使用HBaseAPI实现,目的是规避MapReduce框架,减少…...

Springboot萌宠社交分享系统的设计与实现hfdwz计算机毕业设计-课程设计-期末作业-毕设程序代做
Springboot萌宠社交分享系统的设计与实现hfdwz计算机毕业设计-课程设计-期末作业-毕设程序代做 【免费赠送源码】Springboot萌宠社交分享系统的设计与实现hfdwz计算机毕业设计-课程设计-期末作业-毕设程序代做本源码技术栈: 项目架构:B/S架构 开发语言…...

线性代数与解析几何——Part4 欧式空间 酉空间
线性代数与解析几何——Part4 欧式空间 & 酉空间 1. 欧氏空间 1. 定义 & 性质2. 内积表示与标准正交基3. 欧氏空间的同构4. 欧氏空间的线性变换5. 欧氏空间的子空间 2. 酉空间 1. 定义 & 性质2. 酉变换3. Hermite变换4. 规范变换 1. 欧氏空间 1. 定义 & 性质…...

带头双向循环链表的实现
目录前言节点声明链表的初始化尾插打印链表头插尾删头删查找节点指定位置插入指定位置删除链表销毁前言 之前讲过单链表的实现,在实现的过程中,我们会发现每次删除或者在前面插入节点的时候,都要提前保存上一个节点的地址。这样做十分麻烦&a…...

07【C语言 趣味算法】最佳存款方案(采用 从后往前 递推解决)
目录 一、前情回顾二、Problem:最佳存款方案2.1 Description of the problem2.2 Analysis of the problem2.3 Algorithm design2.4 The complete code and the results of the run(完整的代码 以及 运行结果)一、前情回顾 06【C语言 & 趣味算法】牛顿迭代法求方程根(可…...

游戏开发36课 cocoscreator scrollview优化
在cocoscreator内,ScrollView控件封装的挺完美的了,不过对于一些对性能要求比较高的场景,会存在问题,以top100排行榜排行榜举例子 1、应用卡顿甚至崩溃 按照官方用例使用ScrollView,插入100个玩家的item,理…...

屏幕开发学习 -- 迪文串口屏
一 前言 最近学习了一款基于图形化开发的屏幕,在摸索一周后,基本熟悉了这款产品的一个开发过程,今天给大家分享一下迪文串口屏的学习过程,有不足之处,还请见谅😁,包含了环境搭建和功能DEMO 二 …...

基于springcloud实现分布式架构网上商城演示【项目源码】分享
基于springcloud实现分布式架构网上商城演示摘要 首先,论文一开始便是清楚的论述了系统的研究内容。其次,剖析系统需求分析,弄明白“做什么”,分析包括业务分析和业务流程的分析以及用例分析,更进一步明确系统的需求。然后在明白了系统的需求基础上需要进一步地设计系统,主要包…...

前端HTML网页之间传递数据多种办法,附代码案例
先看效果 目前常用的有三种办法 session传递,cookie传递,url传递 url会暴露参数,其余的两个是保存在服务端和浏览器中,不会暴露在地址栏里面 使用url: 下面依次介绍 一.session传递 index.html <!DOCTYPE htm…...

三方对接「心得」与「体会」
和三方的关系要处好; 01如果你看到这个话题,并不知道是什么意思,那么祝贺你,安安静静的当个小码农也挺好; 不过我敢说,随着职业生涯的慢慢发展,大家都得碰到,到时候就细细体会吧&am…...

经典编译器组成(前端+优化器+后端)以及LLVM和Clang简介
目录 1,典型的编译器结构:前端优化器后端 2,LLVM 简介 3,Clang简介 1,典型的编译器结构:前端优化器后端 一个传统的静态编译器(比如C 编译器)最普遍的设计是分为三个部分…...

交叉编译器的介绍
一.介绍 1.1何谓交叉编译器 交叉编译通俗地讲就是在一种平台上编译出能运行在体系结构不同的另一种平台上。这种方法在异平台移植和嵌入式开发时用得非常普遍,相对与交叉编译,我们平常做的编译就叫本地编译,也就是在当前平台编译࿰…...

【全局谐波偏置:局部上下文自适应卷积核】
LAGConv: Local-context Adaptive Convolution Kernels with Global Harmonic Bias for Pansharpening (LAGConv:全局谐波偏置的局部上下文自适应卷积核用于全色锐化) 全色锐化是一个关键而又具有挑战性的低层次视觉任务,其目的…...

Zabbix“专家坐诊”第186期问答汇总
问题一 Q:这两个键值vm.memory.size[pused]和vm.memory.util监控内存使用率有什么区别,使用那个监控使用率更好,支持windows系统和Linux系统么,对agent端有什么要求么。 A:vm.memory.size[pused]这个是内存的总使用率…...

Python自动化必不可少的测试框架 — pytest
Python在测试圈的应用非常广泛,特别是在自动化测试以及测试开发的领域,其中在自动化测试中我们常用的测试框架是uniitest和pytest,本文将带领大家搭建以及熟悉pytest的使用。 既然有unittest那么为什么还要用pytest呢? 这是因为…...

AndroidStudio功能 - 批量导入、导出 Live Templates 模板
嗯… 记得好多年前就写过Live Templates相关的Blog,但是内容相对综合并不是细致;索性最近开发任务较多,使用一些快捷模板可以提升一下效率,故需要借鉴同事的模板,初始的话可能要一个个抄,可是我有点懒&…...

电力展|2023中国(东莞)国际电力电工展览会
时间:2023年11月16-18日 地点:广东现代国际展览中心 ◆展会背景background: 电力工业是支撑国民经济和社会发展的基础性产业和公用事业,随着我国国民经济的快速发…...