蝙蝠岛资源网 Design By www.hbtsch.com
Summary
- 什么是环形队列
- 实现环形队列图示过程
- golang版本代码实现过程
- 参考全部代码
什么是环形队列
在一个指定大小的数组里循环写入数据,借用二个指针分别实现入队标记与出队标记.也体现了指针的大好用处,请深入体会.大有裨益.
如图所示,一个环形队列.含有二个指针: 队列头指针,队列尾指针.
实现环形队列图示过程
初始化一个数组大小为6的环形队列, 头指针front=0, 尾指针rear=0, 刚好front=rear =0的状态,表示环形队列为空.
2.向环形队列里插入1个元素,则rear指针移动一格,front=0,rear=1
3.继续添加a2,a3,a4,a5元素,rear指针指到末尾处,front=0, reat=5
4.如果再继续添加a6元素,则rear=6,大于数组大小,发生数组溢出.
5.如上图所示添加a6时,rear指针发生溢出.我们使用一个小技巧,当rear=6时与数组大小6进行取模, (rear+1) % maxLen,让rear指针回到开始处rear=0,问题来了,我们无法判断数组是否满"text-align: center">
6.解决以上问题有三种办法,我们采用第3种方法实现.
使用第3种方法: 即当(rear+1) % maxLen == front时,判断环形数组满,则无法添加元素
golang版代码实现过程
a. 定义环形数据结构
type CycleQueue struct { data []interface{} //存储空间 front int //前指针,前指针负责弹出数据移动 rear int //尾指针,后指针负责添加数据移动 cap int //设置切片最大容量 }
b.初始化环形队列
func NewCycleQueue(cap int) *CycleQueue { return &CycleQueue{ data: make([]interface{}, cap), cap: cap, front: 0, rear: 0, } }
c. 入队操作
//入队操作 //判断队列是否队满,队满则不允许添加数据 func (q *CycleQueue) Push(data interface{}) bool { //check queue is full if (q.rear+1)%q.cap == q.front { //队列已满时,不执行入队操作 return false } q.data[q.rear] = data //将元素放入队列尾部 q.rear = (q.rear + 1) % q.cap //尾部元素指向下一个空间位置,取模运算保证了索引不越界(余数一定小于除数) return true }
d.出队操作
//出队操作 //需要考虑: 队队为空没有数据返回了 func (q *CycleQueue) Pop() interface{} { if q.rear == q.front { return nil } data := q.data[q.front] q.data[q.front] = nil q.front = (q.front + 1) % q.cap return data }
e:求当前的环形队列长度
//因为是循环队列, 后指针减去前指针 加上最大值, 然后与最大值 取余 func (q *CycleQueue) QueueLength() int { return (q.rear - q.front + q.cap) % q.cap }
参考全部代码
github
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
蝙蝠岛资源网 Design By www.hbtsch.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
蝙蝠岛资源网 Design By www.hbtsch.com
暂无golang环形队列实现代码示例的评论...
更新日志
2024年05月17日
2024年05月17日
- 原音母版1:1直刻《卓依婷精选集》[低速原抓WAV+CUE]
- 【佛之吧沙发】VA-BuddhaBar-BestOf2byRavin(FLAC)
- [ABC唱片]-《雪莉—蓝》[SACD-008][SACD][WAV+CUE]
- 黎瑞恩.2002-理想的日子精选2CD【环球】【WAV+CUE】
- 【驰放沙发(J)】VA-2024-WinterTime,Vol.12(FLAC)
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 韩红《青藏高原+红+韩红精选集》3CD[WAV分轨][1.7G]
- 高胜美《经典金选》1991-1994 4CD[WAV整轨][1.9G]
- 【迷幻电音】AstralWaves-2023-Singles,RemixesandRaritiesII(FLAC)
- 中唱唱片群星《好歌珍藏-游子情深》2CDWAV
- 张国荣.2011-极品天碟LPCD45II(雨果版)【环球】【WAV+CUE】
- 张学友《醒着做梦》[DFF][1.1G]
- 刘惜君 《如我》[WAV分轨][403M]
- 白玛多吉《梦》限量1:1母盘直刻[低速原抓WAV+CUE][508M]
- 魏金栋-金歌新曲-梦里全是桂花香2CD[天凡之音][WAV+CUE]