golang环形队列实现

jiezi

5 年前

什么是环形队列
实现环形队列图示过程
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, 问题来了, 我
们无法判断数组是否满? 因为初始化时 front=rear=0, 现在数组满也是 front=rear=0

6. 解决以上问题有三种办法, 我们采用第 3 种方法实现.

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

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环形队列实现

Summary

什么是环形队列

实现环形队列图示过程

golang 版代码实现过程

参考全部代码