2021-05-26

╰半橙微兮° 2021-07-24 14:28 227阅读 0赞

# 一 点睛 #

对数组模拟非环形队列进行优化，充分利用数组，可以将数组看做是一个环形的。通过取模的方式来实现。

1 尾索引的前一个为真正的尾节点，尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意。当（tail+1）% maxSize == head 时，表示队列满。

2 tail == head 表示队列空。

# 二 分析 #

1 当满足 (tail + 1) % maxSize = head 时，表示队列满。

2 当 tail == head 表示队列空。

3 初始化时，tail = 0，head = 0。

4 队列元素个数：(tail + maxSize - head ) % maxSize

# 三 代码 #

package main
    
    import (
       "errors"
       "fmt"
       "os"
    )
    
    // 使用一个结构体管理环形队列
    type CircleQueue struct {
       maxSize int    // 实际最大只能装 4 个元素
       array   [5]int // 数组
       head    int    // 指向队首 0
       tail    int    // 指向队尾 0
    }
    
    // 入队列
    func (this *CircleQueue) Push(val int) (err error) {
       if this.IsFull() {
          return errors.New("queue full")
       }
       // this.tail 索引的前一个才是真正的队尾
       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")
       }
       // 出队列，head 指向队首，并且含队首元素
       val = this.array[this.head]
       this.head = (this.head + 1) % this.maxSize
       return
    }
    
    // 显示队列
    func (this *CircleQueue) ListQueue() {
       fmt.Println("环形队列情况如下：")
       // 取出当前队列有多少个元素
       size := this.Size()
       if size == 0 {
          fmt.Println("队列为空")
       }
       // 辅助变量，指向 head
       tempHead := this.head
       for i := 0; i < size; i++ {
          fmt.Printf("arr[%d]=%d\t", tempHead, this.array[tempHead])
          tempHead = (tempHead + 1) % this.maxSize
       }
       fmt.Println()
    }
    
    // 判断环形队列是否满
    func (this *CircleQueue) IsFull() bool {
       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
    }
    
    func main() {
       //初始化一个环形队列
       queue := &CircleQueue{
          maxSize: 5,
          head:    0,
          tail:    0,
       }
       var key string
       var val int
       for {
          fmt.Println("1. 输入add 表示添加数据到队列")
          fmt.Println("2. 输入get 表示从队列获取数据")
          fmt.Println("3. 输入show 表示显示队列")
          fmt.Println("4. 输入exit 表示显示队列")
          fmt.Scanln(&key)
          switch key {
          case "add":
             fmt.Println("输入你要入队列数")
             fmt.Scanln(&val)
             err := queue.Push(val)
             if err != nil {
                fmt.Println(err.Error())
             } else {
                fmt.Println("加入队列ok")
             }
          case "get":
             val, err := queue.Pop()
             if err != nil {
                fmt.Println(err.Error())
             } else {
                fmt.Println("从队列中取出了一个数=", val)
             }
          case "show":
             queue.ListQueue()
          case "exit":
             os.Exit(0)
          }
       }
    }

# 四 测试 #

1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列
    add
    输入你要入队列数
    1
    加入队列ok
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列
    add
    输入你要入队列数
    2
    加入队列ok
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列
    add
    输入你要入队列数
    3
    加入队列ok
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列
    add
    输入你要入队列数
    4
    加入队列ok
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列
    add
    输入你要入队列数
    5
    queue full
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列
    get
    从队列中取出了一个数= 1
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列
    get
    从队列中取出了一个数= 2
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列
    show
    环形队列情况如下：
    arr[2]=3    arr[3]=4    
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示显示队列

2021-05-26

发表评论取消回复

还没有评论，来说两句吧...

相关阅读