Golang数据结构与算法之队列

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

1.思路分析

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下其中maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如图所示：

使用数组实现队列的思路：
1.创建一个数组array,是作为队列的一个字段。
2.front初始化为-1。
3.real,表示队列尾部，初始化为-1。
4.完成队列的基本查找
AddQueue加入数据到队列 GetQueue从队列取出数据 showQueue显示队列

入队列时称为addQueue处理需要有两个步骤:
1.将尾指针往后移:rear+1
2.若尾指引rear小于等于队列的最大下标 MaxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。
rear == MaxSize - 1【队列满】 front == rear【队列空】

2.代码实现

package main

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

//定义结构体
type Queue struct {
	maxSize int
	arr     [5]int
	front   int
	rear    int
}

//加入数据到队列
func (this *Queue) addQueue(val int) (err error) {
	//判断队列是否满
	if this.rear == this.maxSize-1 {
		return errors.New("queue is full")
	}
	this.rear++               //队尾指针+1
	this.arr[this.rear] = val //存入数据
	return
}

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

//显示队列
func (this *Queue) showQueue() {
	fmt.Println("队列当前的情况是:")
	//this.front 不包含队首的元素
	for i := this.front + 1; i <= this.rear; i++ {
		fmt.Printf("arr[%d]=%d\t", i, this.arr[i])

	}
	fmt.Printf("front = %d , real = %d\n", this.front, this.rear)
}
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)
		}
	}
}