007 go 语言实现循环队列

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 技术总结

1. 队列总长度为4, 那么我们需要一个总长度为 4+1 的数组
2. 判断为空 head == tail
3. 判断满 tail + 1 = head
4. 初始化的时候, 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)
    }
}