• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    golang环形队列实现代码示例

    Summary

    什么是环形队列

    在一个指定大小的数组里循环写入数据,借用二个指针分别实现入队标记与出队标记.也体现了指针的大好用处,请深入体会.大有裨益.

    如图所示,一个环形队列.含有二个指针: 队列头指针,队列尾指针.

    实现环形队列图示过程

    初始化一个数组大小为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,问题来了,我们无法判断数组是否满?因为初始化时front=rear=0, 现在数组满也是front=rear=0


    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

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    您可能感兴趣的文章:
    • 用golang实现一个定时器任务队列实例
    • Go语言的队列和堆栈实现方法
    上一篇:使用Go进行单元测试的实现
    下一篇:浅析go中的map数据结构字典
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

    golang环形队列实现代码示例 golang,环形,队列,实现,代码,