go 数组实现非环形队列

我就是我 2021-07-24 23:38 446阅读 0赞

# 一 队列的应用场景 #

银行排队

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 二 队列介绍 #

1 队列是一个有序列表，可以用数组或是链表来实现。

2 队列遵循先入先出的原则。即：先存入队列的数据，先取出。后存入的后取出。

3 示意图——使用数组模拟队列

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1][]

说明：front 指向首节点的前一个节点

# 三 数组模拟队列 #

## 1 需求 ##

完成一个非环形的队列，要求数组来实现。

## 2 分析 ##

队列本身是有序列表，使用数组的结构来存储队列的数据，用maxSize来表示队列的最大容量。

因为队列的输出和输入是分别从前后端来处理，因此需要两个变量 front 和 rear 分别记录队列前后端的下标，front 会随着数据的输出而改变，而 rear 则是随着数据输入而改变，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 2][]

思路分析

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 3][]

## 3 代码 ##

package main
    
    import (
       "errors"
       "fmt"
       "os"
    )
    
    // 使用一个结构体管理队列
    type Queue struct {
       maxSize int
       array   [5]int // 用数组模拟队列
       front   int    // 表示指向队列首
       rear    int    // 表示指向队列尾
    }
    
    // 添加数据到队列
    func (this *Queue) AddQueue(val int) (err error) {
       // 先判断队列是否已满
       if this.rear == this.maxSize-1 { // rear：是队列尾部，含最后元素
          return errors.New("queue full")
       }
       this.rear++ // rear 后移
       this.array[this.rear] = val
       return
    }
    
    // 从队列中取出数据
    func (this *Queue) GetQueue() (val int, err error) {
       // 先判断队列是否为空
       if this.rear == this.front { // 队空
          return -1, errors.New("queue empty")
       }
       this.front++
       val = this.array[this.front]
       return val, err
    }
    
    // 显示队列, 找到队首，然后遍历到队尾
    func (this *Queue) ShowQueue() {
       fmt.Println("队列当前的情况是:")
       // this.front 队首的元素的前一个下标
       for i := this.front + 1; i <= this.rear; i++ {
          fmt.Printf("array[%d]=%d\t", i, this.array[i])
       }
       fmt.Println()
    }
    
    // 编写一个主函数
    func main() {
       // 先创建一个队列
       queue := &Queue{
          maxSize: 5,
          front:   -1,
          rear:    -1,
       }
       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.AddQueue(val)
             if err != nil {
                fmt.Println(err.Error())
             } else {
    
    
                fmt.Println("加入队列ok")
             }
          case "get":
             val, err := queue.GetQueue()
             if err != nil {
                fmt.Println(err.Error())
             } else {
                fmt.Println("从队列中取出了一个数=", val)
             }
          case "show":
             queue.ShowQueue()
          case "exit":
             os.Exit(0)
          }
       }
    }

## 4 测试 ##

1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示退出程序
    add
    输入你要入队列数
    1
    加入队列ok
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示退出程序
    show
    队列当前的情况是:
    array[0]=1    
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示退出程序
    add
    输入你要入队列数
    2
    加入队列ok
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示退出程序
    show
    队列当前的情况是:
    array[0]=1    array[1]=2    
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示退出程序
    get
    从队列中取出了一个数= 1
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示退出程序
    show
    队列当前的情况是:
    array[1]=2    
    1. 输入add 表示添加数据到队列
    2. 输入get 表示从队列获取数据
    3. 输入show 表示显示队列
    4. 输入exit 表示退出程序

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/31006a5c7172479587469869b3a5a0f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/52ab1bcd62324901af22875710cbe2ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 2]: /images/20210724/aaf945eaa6744920b0f7394e35e0ac8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 3]: /images/20210724/dbb496cf5a0248fea6d7bee6662d5862.png