go循环队列的实现

1、循环队列

队列的概念在顺序队列中，而使用循环队列的目的主要是规避假溢出造成的空间浪费，在使用循环队列处理假溢出时，本文采用以下两种方式来判断队满

• 在循环队列的结构体中加上一个length长度标识
• 少使用一个位置

2、初始化

//循环队列的数据结构
type Queue struct {
    //这里的指针并不是指针变量，而是用来表示数组当中元素下标的位置
    front int //头指针
    rear int //尾指针
    length int //顺序表中元素的个数
    queueSize int //初始化动态分配存储空间
    queueList []interface{}
}

3、判断队空、队满

3.1 在循环队列的结构体中加上一个length长度标识

//方法一是根据Length作为一个判断依据
//判断队满(方法一)
func (queue *Queue) isFullByLen() bool {
    if queue.length == queue.queueSize {
        fmt.Println("队列已满")
        return true
    }
    return false
}

//判断队空(方法一)
func (queue Queue) isNullByLen() bool {
    if queue.length == 0 {
        return true
    }
    return false
}

3.2 少使用一个位置

//方法二是少使用一个位置
//判断队满(方法二)
func (queue *Queue) isFullByLocation() bool {
    if (queue.rear + 1) % queue.queueSize == queue.front {
        fmt.Println("队列已满")
        return true
    }
    return false
}

//判断队空(方法二)
func (queue Queue) isNullByLocation() bool {
    if queue.front == queue.rear {
        return true
    }
    return false
}

4、入队

func (queue *Queue) push(val interface{}) {
    //判断队满
    if queue.isFullByLocation() {
        return
    }

    queue.queueList[queue.rear] = val
    queue.rear = (queue.rear + 1) % queue.queueSize
    queue.length ++
}

5、出队

func (queue *Queue) pop() interface{} {
    if queue.isNullByLocation() {
        fmt.Println("队空")
        return nil
    }

    val := queue.queueList[queue.front]
    queue.queueList[queue.front] = nil
    queue.front = (queue.front + 1) % queue.queueSize
    queue.length --
    return val
}

6、完整代码及结果展示

package main

import "fmt"

//循环队列的数据结构
type Queue struct {
    //这里的指针并不是指针变量，而是用来表示数组当中元素下标的位置
    front int //头指针
    rear int //尾指针
    length int //顺序表中元素的个数
    queueSize int //初始化动态分配存储空间
    queueList []interface{}
}

//初始化
func initQueue(size int) *Queue {
    if size <= 0 {
        return nil
    }
    return &Queue{
        front: 0,
        rear: 0,
        length: 0,
        queueSize: size,
        queueList: make([]interface{}, size),
    }
}


//方法一是根据Length作为一个判断依据
//判断队满(方法一)
func (queue *Queue) isFullByLen() bool {
    if queue.length == queue.queueSize {
        fmt.Println("队列已满")
        return true
    }
    return false
}

//判断队空(方法一)
func (queue Queue) isNullByLen() bool {
    if queue.length == 0 {
        return true
    }
    return false
}

//入队(方法一)
func (queue *Queue) push(val interface{}) {
    //判断队满
    if queue.isFullByLocation() {
        return
    }

    queue.queueList[queue.rear] = val
    queue.rear = (queue.rear + 1) % queue.queueSize
    queue.length ++
}

//出队(方法一)
func (queue *Queue) pop() interface{} {
    if queue.isNullByLocation() {
        fmt.Println("队空")
        return nil
    }

    val := queue.queueList[queue.front]
    queue.queueList[queue.front] = nil
    queue.front = (queue.front + 1) % queue.queueSize
    queue.length --
    return val
}

//方法二是少使用一个位置
//判断队满(方法二)
func (queue *Queue) isFullByLocation() bool {
    if (queue.rear + 1) % queue.queueSize == queue.front {
        fmt.Println("队列已满")
        return true
    }
    return false
}

//判断队空(方法二)
func (queue Queue) isNullByLocation() bool {
    if queue.front == queue.rear {
        return true
    }
    return false
}

func main() {
    data := [...]interface{}{
        "bala",
        "aa",
        12,
        66,
    }
    L := initQueue(4)
    for i := range data {
        L.push(data[i])
    }
    fmt.Println(L)
    L.pop()
    fmt.Println(L)
    L.pop()
    fmt.Println(L)
    L.pop()
    fmt.Println(L)
    L.pop()
    fmt.Println(L)
    L.push(1)
    fmt.Println(L)
    L.push(1)
    fmt.Println(L)
    L.push(1)
    fmt.Println(L)
    L.push(1)
    fmt.Println(L)
}

//输出
队列已满
&{0 3 3 4 [bala aa 12 <nil>]}
&{1 3 2 4 [<nil> aa 12 <nil>]}
&{2 3 1 4 [<nil> <nil> 12 <nil>]}
&{3 3 0 4 [<nil> <nil> <nil> <nil>]}
队空
&{3 3 0 4 [<nil> <nil> <nil> <nil>]}
&{3 0 1 4 [<nil> <nil> <nil> 1]}
&{3 1 2 4 [1 <nil> <nil> 1]}
&{3 2 3 4 [1 1 <nil> 1]}
队列已满
&{3 2 3 4 [1 1 <nil> 1]}

总结

关于队列中的指针：

顺序队和循环队列是一种特殊的线性表，与顺序栈类似，都是使用一组地址连续的存储单元依次存放自队头到队尾的数据元素，同时附设队头(front)和队尾(rear)两个指针，但我们要明白一点，这个指针并不是指针变量，而是用来表示数组当中元素下标的位置。

本文使用切片来完成的循环队列，由于一开始使用三个参数的make关键字创建切片，在输出的结果中不包含nil值(看起来很舒服)，而且在验证的过程中发现使用append()函数时切片内置的cap会发生变化，在消除了种种障碍后得到了一个四不像的循环队列，即设置的指针是顺序队列的指针，但实际上进行的操作是顺序队列的操作。最后是对make()函数和append()函数的一些使用体验和小结，队列的应用放在链队好了。

关于make()函数

官方描述(片段)

//For example, make([]int, 0, 10) allocates an underlying array of size 10 and 
//returns a slice of length 0 and capacity 10 that is backed by this underlying array.

例如，make([]int, 0, 10)分配一个大小为10的底层数组，并返回由该底层数组
支持的长度为0、容量为10的片。

即切片是一个抽象层，底层是对数组的引用。

当我们使用

make([]interface{}, 10)

构建出来的切片的每个位置的值都被赋为interface类型的初始值nil，但是nil值也是有大小的。

而使用

make([]interface{}, 0, 10)

来进行初始化时，虽然生成的切片中不包含nil值，但是无法通过设置的指针变量来完成入队和出队的操作，只能使用append()函数来进行操作

关于append()函数

//The append built-in function appends elements to the end of a slice. If it has 
//sufficient capacity, the destination is resliced to accommodate the new elements.
//If it does not, a new underlying array will be allocated. Append returns the 
//updated slice. It is therefore necessary to store the result of append, often 
//in the variable holding the slice itself:
append内置函数将元素追加到片段的末尾。如果目的地有足够的容量，那么它将
被重新许可以容纳新元素。否则，将分配一个新的基础数组。Append返回更新的
切片。因此，有必要将append的结果存储在保存切片本身的变量中：

在go语言中，切片是一片连续的内存空间加上长度与容量的标识，比数组更为常用。使用 append 关键字向切片中追加元素也是常见的切片操作

• 在切片容量足够的前提下，使用append()函数进行操作是很快的。

正是基于此，在使用go语言完成循环队列时，首先想到的就是使用make(type, len, cap)关键字方式完成切片初始化，然后使用append()函数来操作该切片，但这一方式出现了很多问题。在使用append()函数时，切片的cap可能会发生变化，用不好就会发生扩容或收缩。最终造成的结果是一个四不像的结果，入队和出队操作变得与指针变量无关，失去了作为循环队列的意义，用在顺序队列还算合适。

参考博客：
Go语言中的Nil
Golang之nil
Go 语言设计与实现

有疑问加站长微信联系（非本文作者）