golang环形队列实现

百里 · · 104 次点击 · · 开始浏览    

Summary

  1. 什么是环形队列
  2. 实现环形队列图示过程
  3. golang版本代码实现过程
  4. 参考全部代码

什么是环形队列

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

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

image.png

实现环形队列图示过程

  1. 初始化一个数组大小为6的环形队列, 头指针front=0, 尾指针rear=0, 刚好front=rear =0的状态,表示环形队列为空.

image.png
2.向环形队列里插入1个元素,则rear指针移动一格,front=0,rear=1
image.png
3.继续添加a2,a3,a4,a5元素,rear指针指到末尾处,front=0, reat=5
image.png
4.如果再继续添加a6元素,则rear=6,大于数组大小,发生数组溢出.
image.png
5.如上图所示添加a6时,rear指针发生溢出.我们使用一个小技巧,当rear=6时与数组大小6进行取模, (rear+1) % maxLen,让rear指针回到开始处rear=0,问题来了,我
们无法判断数组是否满?因为初始化时front=rear=0, 现在数组满也是front=rear=0
image.png
6.解决以上问题有三种办法,我们采用第3种方法实现.
image.png

使用第3种方法: 即当(rear+1) % maxLen == front时,判断环形数组满,则无法添加元素

image.png

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
image.png

本文来自:Segmentfault

感谢作者:百里

查看原文:golang环形队列实现

入群交流(和以上内容无关):Go中文网 QQ 交流群:729884609 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

104 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传