Golang算法与数据结构：队列(queue)

1. 基本介绍

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

2. 数组模拟队列

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

2.1. 非环形队列(数组实现)

当我们将数据存入队列时称为” addqueue”, addqueue的处理需要有两个步骤:
1)将尾指针往后移: rear+1，front== rear [空]

2)若尾指针rear小于等于队列的最大下标MaxSize-1,则将数据存入rear所指的数组元素中，否则无法存入数据。rear == MaxSize-1[队列满]

2.1.1. 思路分析

1.创建一个数组arrary, 作为队列的一个字段

front,表示队列头部,初始化为-1
rear,表示队列尾部,初始化为-1
4.完成队列的基本查找

1
2
3

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

2.1.2. 实现

package main

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

//创建结构体来管理
type Queue struct {
	maxSize int    //队列最大长度
	array   [5]int //数组模拟队列
	front   int    //指向队首(不包括第一个元素)
	rear    int    // 指向队尾(包括最后一个元素)
}

func (this *Queue) addQueue(num int) (err error) {
	if this.rear == this.maxSize-1 {
		//证明已经是队尾元素了，不能再加了
		return errors.New("queue full")
	}
	this.rear++
	this.array[this.rear] = num
	return
}
func (this *Queue) getQueue() (num int, err error) {
	if this.front == this.rear {
		//证明头尾指针已经到了一起，队列元素为空
		err = errors.New("queue empty")
		return
	}
	this.front++
	num = this.array[this.front]
	return
}
func (this *Queue) showQueue() {
	fmt.Println("当前队列:")
	for i := this.front + 1; i <= this.rear; i++ {
		fmt.Printf("array[%d]=%d\n", i, this.array[i])
	}
}
func main() {
	var key string
	var queue = &Queue{
		maxSize: 5,
		rear:    -1,
		front:   -1,
	}
	var num int
	for {
		fmt.Println("show 查看队列:")
		fmt.Println("add 添加数据到队列")
		fmt.Println("get 从队列获取元素")
		fmt.Println("exit 退出")
		fmt.Println("请输入操作名称:")
		fmt.Scanf("%s\n", &key)
		switch key {
		case "show":
			queue.showQueue()
		case "add":
			fmt.Println("请输入数据:")
			fmt.Scanf("%d\n", &num)
			err := queue.addQueue(num)
			if err != nil {
				fmt.Println(err.Error())
			}
		case "get":
			num, err := queue.getQueue()
			if err != nil {
				fmt.Println(err.Error())
			} else {
				fmt.Println(num)
			}
		case "exit":
			os.Exit(0)
		default:
			fmt.Println("输入有误，请重新输入")
		}
	}

}

2.2. 环形队列实现(数组实现)

对前面的数组模拟队列的优化，充分利用数组，因此将数组看做是一个环形的。(通过取模的方式来实现)

提醒:

(tail+1)%maxSize == head

2) tail == head [空]

2.2.1. 思路分析

(tail + 1) % maxSize = heddtail == headtail=0，head=0(tail + maxSize - head ) % maxSize

2.2.2. 实现

package main

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

type circleQueue struct {
	maxSize int
	array   [5]int
	head    int //指向队首，包含队首元素。先弹出，指针再向下移动
	tail    int //指向队尾，不包含队尾元素。先推入，指针再向下移动
	//这里的包含不包含的意思是，当直接取 this.array[head] 或者 this.array[tail]时，是否有值
}

func (this *circleQueue) Push(num int) (err error) {
	//判断队列是否已满
	//因为是+1来判断是否到达了头指针，如果回到头指针，证明队列就满了
	//故意将数组留了一个位置，来判断是否到达头指针。因为tail是不包含队尾的
	if (this.tail+1)%this.maxSize == this.head {
		err = errors.New("queue full")
		return
	}
	this.array[this.tail] = num
	this.tail = (this.tail + 1) % this.maxSize
	return
}
func (this *circleQueue) Pop() (num int, err error) {
	//判断队列是否为空
	if this.head == this.tail {
		err = errors.New("queue empty")
		return
	}
	num = this.array[this.head]
	this.head = (this.head + 1) % this.maxSize
	return
}

//
func (this *circleQueue) Size() (num int) {
	//因为tail有可能回到0开始，所以需要加上长度
	//取模是因为这是一个万能公式，可以通用
	return (this.tail + this.maxSize - this.head) % this.maxSize
}

func (this *circleQueue) List() {
	size := this.Size()
	if size == 0 {
		fmt.Println("队列为空")
	} else {
		tempHead := this.head
		for i := 0; i < size; i++ {
			fmt.Printf("array[%d]=%d ", tempHead, this.array[tempHead])
			tempHead = (tempHead + 1) % this.maxSize
		}
		fmt.Println()
	}
}

func main() {
	var key string
	var queue = &circleQueue{
		maxSize: 5,
		head:    0,
		tail:    0,
	}
	var num int
	for {
		fmt.Println("show 查看队列:")
		fmt.Println("add 添加数据到队列")
		fmt.Println("get 从队列获取元素")
		fmt.Println("exit 退出")
		fmt.Println("请输入操作名称:")
		fmt.Scanf("%s\n", &key)
		switch key {
		case "show":
			queue.List()
		case "add":
			fmt.Println("请输入数据:")
			fmt.Scanf("%d\n", &num)
			err := queue.Push(num)
			if err != nil {
				fmt.Println(err.Error())
			}
		case "get":
			num, err := queue.Pop()
			if err != nil {
				fmt.Println(err.Error())
			} else {
				fmt.Println(num)
			}
		case "exit":
			os.Exit(0)
		default:
			fmt.Println("输入有误，请重新输入")
		}
	}
}