队列（queue）

队列原理：先进先出；

• 队列是一个有序列表，可以用数组或是链表来实现；
• 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出；

队列的应用场景：
银行排队叫号；

使用数组模拟队列：

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下，其中maxSize是该队列的最大容量。

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

• 当我们将数据存入队列时称为"addqueue", addqueue的处理需要两个步骤：

  • 将尾指针往后移，rear+1，front == rear [空]
  • 若尾指针 rear小于等于队列的最大下标MaxSize-1,则将数据存入rear所指的数组元素中，否则无法存入数据。

先完成一个非环形的队列(数组来实现)

思路：

• 1.创建一个数组 array，是作为队列的一个字段；
• 2.front，表示队列的头部，初始化为-1
• 3.rear，表示队列尾部，初始化为-1
• 4.完成队列的基本查找：

AddQueue  //加入数据到队列；
GetQueue  //从队列取出数据；
ShowQueue //显示队列

package main

import (
    "errors"
    "fmt"
    "os"
)

//使用一个结构体管理队列
type Queue struct {
    maxSize int
    array   [4]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)
            } 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)
        default:
            fmt.Println("输入有误，请按照提示输入!")
        }
    }
}

上述代码的不足：

• 当front指针，即从队列中取数据，取到队列末尾后，队列就不能再继续使用了；
• AddQueue()报，队列已满；而GetQueue报队列为空；