什么是隊(duì)列

隊(duì)列是一種常用的數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)保證了數(shù)據(jù)是按照“先進(jìn)先出”的原則進(jìn)行操作的，即最先進(jìn)去的元素也是最先出來(lái)的元素.環(huán)形隊(duì)列是一種特殊的隊(duì)列結(jié)構(gòu)，保證了元素也是先進(jìn)先出的，但與一般隊(duì)列的區(qū)別是，他們是環(huán)形的，即隊(duì)列頭部的上個(gè)元素是隊(duì)列尾部，通常是容納元素?cái)?shù)固定的一個(gè)閉環(huán)。

環(huán)形隊(duì)列的優(yōu)點(diǎn)

1. 保證元素是先進(jìn)先出的
2. 元素空間可以重復(fù)利用

環(huán)形隊(duì)列設(shè)的特征

1. 隊(duì)首(head)與隊(duì)尾(tail)索引位置
2. 是否隊(duì)滿
3. 是否隊(duì)空
4. 隊(duì)列的總數(shù)據(jù)

結(jié)合以上的特征來(lái)看golang實(shí)現(xiàn)代碼

package main

import (
    "errors"
    "fmt"
)

//環(huán)狀隊(duì)列的基本實(shí)現(xiàn)
type CircleQueue struct {
    maxSize int    // 假設(shè)最大長(zhǎng)度為5
    array   [5]int //假設(shè)長(zhǎng)度為5，也可以用切片來(lái)實(shí)現(xiàn)
    head    int    //指向隊(duì)首
    tail    int    //指向隊(duì)尾
}

func main() {
    queue := &CircleQueue{
        maxSize: 5,        // 假設(shè)最大長(zhǎng)度為5
        array:   [5]int{}, //假設(shè)長(zhǎng)度為5，也可以用切片來(lái)實(shí)現(xiàn)
        head:    0,        // 指向隊(duì)首，初始化時(shí)，隊(duì)首索引位為0
        tail:    0,        // 指向隊(duì)尾，初始化時(shí)，隊(duì)尾索引位為0
    }
    _ = queue.Push(1) // 入隊(duì)
    _ = queue.Push(2) // 入隊(duì)
    queue.ListQueue()
    _, _ = queue.Pop() // 出隊(duì)
}

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

    return
}

// 出隊(duì)列
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
}

// 遍歷隊(duì)列
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 // 計(jì)算出下一隊(duì)首索引
    }
    fmt.Println()
}

// 隊(duì)列是否滿了
func (this *CircleQueue) IsFull() bool {
    /*
        隊(duì)滿情況[ (tail+1)%maxSize == head ]
        head    tail
        0       4
        1       0
        2       1
        3       2
        4       3
    */
    return (this.tail+1)%this.maxSize == this.head
}

// 隊(duì)列是否為空
func (this *CircleQueue) IsEmpty() bool {
    return this.tail == this.head
}

// 隊(duì)列多少個(gè)元素
func (this *CircleQueue) Size() int {
    return (this.tail + this.maxSize - this.head) % this.maxSize
}

幾個(gè)功能點(diǎn)算法

1. 隊(duì)首(head)與隊(duì)尾(tail)索引位置

    // 出隊(duì)
    head = (head + 1) % maxSize
    // 入隊(duì)
    tail = (tail + 1) % maxSize

2. 是否隊(duì)滿

    // 判斷是否隊(duì)滿
    (tail+1)%maxSize == head

3. 是否隊(duì)空

    // 是否隊(duì)空
    tail == head

4. 隊(duì)列的數(shù)據(jù)總數(shù)據(jù)

    // 隊(duì)列的數(shù)據(jù)總數(shù)據(jù)
    (tail + maxSize - head) % maxSize

5. 遍歷時(shí)隊(duì)首索引

    // 計(jì)算出下一隊(duì)首索引
    index = (index + 1) % this.maxSize

只要把這個(gè)幾個(gè)公式弄清，就能很容易的操作環(huán)形隊(duì)列