golang 用数组实现环形队列的方法

什么是队列

队列是一种常用的数据结构，这种结构保证了数据是按照“先进先出”的原则进行操作的，即最先进去的元素也是最先出来的元素.环形队列是一种特殊的队列结构，保证了元素也是先进先出的，但与一般队列的区别是，他们是环形的，即队列头部的上个元素是队列尾部，通常是容纳元素数固定的一个闭环。

环形队列的优点

1. 保证元素是先进先出的
2. 元素空间可以重复利用

环形队列设的特征

1. 队首(head)与队尾(tail)索引位置
2. 是否队满
3. 是否队空
4. 队列的总数据

结合以上的特征来看golang实现代码

package main

import (
    "errors"
    "fmt"
)

//环状队列的基本实现
type CircleQueue struct {
    maxSize int    // 假设最大长度为5
    array   [5]int //假设长度为5，也可以用切片来实现
    head    int    //指向队首
    tail    int    //指向队尾
}

func main() {
    queue := &CircleQueue{
        maxSize: 5,        // 假设最大长度为5
        array:   [5]int{}, //假设长度为5，也可以用切片来实现
        head:    0,        // 指向队首，初始化时，队首索引位为0
        tail:    0,        // 指向队尾，初始化时，队尾索引位为0
    }
    _ = queue.Push(1) // 入队
    _ = queue.Push(2) // 入队
    queue.ListQueue()
    _, _ = queue.Pop() // 出队
}

// 入队列
func (this *CircleQueue) Push(val int) (err error) {
    if this.IsFull() {
        return errors.New("queue full")
    }
    this.array[this.tail] = val
    //算法，计算队尾的位置
    this.tail = (this.tail + 1) % this.maxSize

    return
}

// 出队列
func (this *CircleQueue) Pop() (val int, err error) {
    if this.IsEmpty() {
        return 0, errors.New("queue empty")
    }
    val = this.array[this.head]
    this.head = (this.head + 1) % this.maxSize
    return
}

// 遍历队列
func (this *CircleQueue) ListQueue() {
    size := this.Size()
    if size == 0 {
        fmt.Println("queue empty")
    }
    index := this.head
    for i := 0; i < size; i++ {
        fmt.Printf("arr[%d]=%d\n", index, this.array[index])
        index = (index + 1) % this.maxSize // 计算出下一队首索引
    }
    fmt.Println()
}

// 队列是否满了
func (this *CircleQueue) IsFull() bool {
    /*
        队满情况[ (tail+1)%maxSize == head ]
        head    tail
        0       4
        1       0
        2       1
        3       2
        4       3
    */
    return (this.tail+1)%this.maxSize == this.head
}

// 队列是否为空
func (this *CircleQueue) IsEmpty() bool {
    return this.tail == this.head
}

// 队列多少个元素
func (this *CircleQueue) Size() int {
    return (this.tail + this.maxSize - this.head) % this.maxSize
}

几个功能点算法

1. 队首(head)与队尾(tail)索引位置

    // 出队
    head = (head + 1) % maxSize
    // 入队
    tail = (tail + 1) % maxSize

2. 是否队满

    // 判断是否队满
    (tail+1)%maxSize == head

3. 是否队空

    // 是否队空
    tail == head

4. 队列的数据总数据

    // 队列的数据总数据
    (tail + maxSize - head) % maxSize

5. 遍历时队首索引

    // 计算出下一队首索引
    index = (index + 1) % this.maxSize

只要把这个几个公式弄清，就能很容易的操作环形队列