队列(queue)

队列特点

FIFO（先进先出）

队列介绍

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

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

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

当我们将数组存入队列时称为AddQueue,其处理有两个步骤

1. 将尾指针往后移：rear+1, front==rear(空)

2. 若尾指针rear小于等于数组最大下表MaxSize-1则将数组存入rear所指的数组元素中，否则无法存入数据。此时rear == MaxSize - 1（队列满）

基本实现如下：

type Queue struct {
    maxSize int
    array [3]int
    front int
    rear  int
}
​
// 初始化
var queue = &Queue{
    maxSize : 3,
    front   : -1,
    rear    : -1,
}

思路：

1. 创建数组array,作为队列的字段

2. front初始化为-1

3. rear表示队列尾部初始化为-1

4. 完成队列的基本查找

AddQueue //加入数据到队列

GetQueue //从队列去除数据

ShowQueue // 显示队列

代码如下：

package main

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

type Queue struct {
    maxSize int
    array   [5]int // 数组=>模拟队列
    front   int    // 表示指向队列首
    rear    int    // 表示指向队列尾
}

// 添加数据到队列
func (this *Queue) Add(val int) (err error) {
    // 先判断队列是否已满
    if this.rear == this.maxSize-1 { // 重要提示：rear是队列尾部（含最后元素）
        return errors.New("queue full")
    }
    this.rear++
    this.array[this.rear] = val
    return
}

// 显示队列
func (this *Queue) Show() {
    fmt.Println("队列当前情况是：")
    for i := this.front + 1; i <= this.rear; i++ {
        fmt.Printf("array[%d]=%d\t", i, this.array[i])
    }
    fmt.Println()
}

// 从队列中取出数据
func (this *Queue) Get() (val int, err error) {
    // 判断队列是否为空
    if this.rear == this.front { // 队列为空
        val = -1
        err = errors.New("queue empty")
        return
    }
    this.front++
    val = this.array[this.front]
    return
}

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.Add(val)
            if err != nil {
                fmt.Println(err.Error())
            } else {
                fmt.Println("加入队列ok")
            }
        case "get":
            val, err := queue.Get()
            if err != nil {
                fmt.Println(err.Error())
            } else {
                fmt.Println("从队列中取出了一个数", val)
            }
        case "show":
            queue.Show()
        case "exit":
            os.Exit(0)
        }
    }
}

这个程序就没有办法用go playground运行了，各位自己下载go编译器在本地跑一下或者在下面空降27:47