1 代码参考
所有代码以及测试代码
https://gitee.com/babyb/data_srtuct/tree/master/007circleQueue
2 循环队列定义
循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。
3 循环队列思路
1 初始化
初始化的时候, head , tail 都在下标为0的地方, head == tail 表明循环队列为空
| 下标 0 |
1 |
2 |
3 |
4 |
| head, tail |
空 |
空 |
空 |
空 |
2 添加一个元素后
| 下标 0 |
1 |
2 |
3 |
4 |
| head, 元素 |
tail |
空 |
空 |
空 |
3 添加4个元素后
添加四个元素后, 下标 0 1 2 3 被占满, tail 位于最后一个元素的地方
| 下标 0 |
1 |
2 |
3 |
4 |
| head, 元素 |
元素 |
元素 |
元素 |
tail |
tail + 1 = head, 表明 循环队列已满, 无法继续添加
4 弹出队头元素后
弹出队头元素后, tail.next != head, 所以可以继续添加,
| 下标 0 |
1 |
2 |
3 |
4 |
| 空 |
head 元素 |
元素 |
元素 |
tail |
5 继续添加元素
元素添加到下标为 4 的位置上, tail 移动到下标为 0的位置上, 这时候, tail + 1 = head , 表明循环队列又满了, 无法继续添加
| 下标 0 |
1 |
2 |
3 |
4 |
| tail |
head 元素 |
元素 |
元素 |
元素 |
6 把四个元素都弹出后
6.1 弹第一个元素
| 下标 0 |
1 |
2 |
3 |
4 |
| tail |
空 |
head 元素 |
元素 |
元素 |
6.2 弹第二个元素
| 下标 0 |
1 |
2 |
3 |
4 |
| tail |
空 |
空 |
head 元素 |
元素 |
6.3 弹第三个元素
| 下标 0 |
1 |
2 |
3 |
4 |
| tail |
空 |
空 |
空 |
head元素 |
6.4 弹第四个元素
| 下标 0 |
1 |
2 |
3 |
4 |
| tail, head |
空 |
空 |
空 |
空 |
head = = tail , 表明 队列为空
7 假定从其他位置开始
7.0 满
| 下标 0 |
1 |
2 |
3 |
4 |
| 元素 |
元素 |
元素 |
tail |
head元素 |
7.1 弹第一个
| 下标 0 |
1 |
2 |
3 |
4 |
| head元素 |
元素 |
元素 |
tail |
空 |
7.2 弹第二个
| 下标 0 |
1 |
2 |
3 |
4 |
| 空 |
head元素 |
元素 |
tail |
空 |
7.3 弹第三个
| 下标 0 |
1 |
2 |
3 |
4 |
| 空 |
空 |
head元素 |
tail |
空 |
7.4 弹第四个
| 下标 0 |
1 |
2 |
3 |
4 |
| 空 |
空 |
空 |
head, tail |
空 |
head == tail , 表明循环队列为空
8 技术总结
- 队列总长度为4, 那么我们需要一个总长度为 4+1 的数组
- 判断为空 head == tail
- 判断满 tail + 1 = head
- 初始化的时候, head, tail 下标都在为0 的位置, head = tail, 满足条件2, 队列为空
4 数据结构
//Object 数据结构
type Object interface{}
// len 表示我们用于存储数据的数组的长度
var len int
/*
Queue 队列
*/
type Queue struct {
data []Object
head int
tail int
}
5 各个方法
5.1 InitCircleQueue 队列初始化操作
func InitCircleQueue(size int) Queue {
len = size + 1
array := make([]Object, len)
q := Queue{}
q.data = array
q.head = 0
q.tail = 0
return q
}
5.2 Empty 判断是否为空
/*
Empty 判断是否为空
*/
func (q *Queue) Empty() bool {
if q.head == q.tail {
return true
}
return false
}
5.3 Full 判断是否已满
func (q *Queue) Full() bool {
next := q.tailNext()
if next == q.head {
return true
}
return false
}
//next 获取下一个元素的下标
func (q *Queue) tailNext() int {
var next int
if q.tail == len-1 {
//当tail 位于最后一个元素时, next = 0
next = 0
} else {
next = q.tail + 1
}
return next
}
5.4 Push 从尾部添加元素添加元素
// Push 从尾部添加元素添加元素
func (q *Queue) Push(data Object) (err error) {
// head 所处的下标先添加元素, 然后, head 下标 + 1
curr := q.tail
if q.Full() {
fmt.Println("队列已满, 无法继续添加")
return errors.New("队列已满, 无法继续添加")
}
q.data[curr] = data
// //head 下标向后移动
if q.tail == len-1 {
q.tail = 0
} else {
q.tail++
}
fmt.Println("添加元素成功:", data)
return nil
}
5.5 从头部弹出元素
func (q *Queue) Pop() (data Object) {
if q.Empty() {
fmt.Println("队列为空, 无法继续弹出")
return nil
}
first := q.head
// 头元素下标后移
if q.head == len-1 {
q.head = 0
} else {
q.head++
}
data = q.data[first]
//元素拿出后, q.data 中对应下标的值 设定为null
q.data[first] = nil
fmt.Println("弹出元素:", data)
return data
}
5.6 ShowAll q.data下标从0开始, 展示到最后一个元素, 用于观察队列是否循环
func (q *Queue) ShowAll() {
for index := 0; index < len; index++ {
item := q.data[index]
fmt.Printf("下标为%d的元素为%v \n", index, item)
}
}
