二 队列
2.1 队列的介绍
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即:先存入队列的数据，要先取出。后存入的要后取出
2.2 数组模拟队列思路
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下
其maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如下图所示：
当我们将数据存入队列时称为”AddQueue”，AddQueue的处理需要有两个步骤:
将尾指针往后移:rear+1 , front == rear时队列是空的
若尾指引rear小于等于队列的最大下标 MaxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear == MaxSize -1（队列满）
思路分析：
创建一个数组 arrary ，最为队列的一个字段
front 初始化为-1
rear 表示队列的尾部，初始化为-1
完成队列的基本查找
AddQueue：加入数据到队列
GetQueue：从队列中取出数据
ShowQueue：显示队列
; 2.3 数组模拟队列代码实现
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 {
return errors.New("queue full")
}
this.rear++
this.array[this.rear] = val
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])
}
fmt.Println()
}
func main() {
queue := &Queue{
maxSize: 5,
front: -1,
rear: -1,
}
fmt.Printf("%p", queue)
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("加入队列成功")
} else {
fmt.Println(err.Error())
}
case "get":
case "show":
queue.ShowQueue()
case "exit":
os.Exit(0)
}
}
}
2.4 数组模拟队列弊端
上面代码实现了基本队列结构，但是没有有效的利用数组空间，队列只能使用一次。
使用数组实现一个环形的队列进行优化(通过取模的方式改进)
三 环形队列
3.1 数组模拟环形队列思路
尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意(tail+1) % maxSize ==head [满]
tail == head [空]
分析思路:
队列满：(tail+1) % maxSize = head
tail ==head 表示空
初始化时，tail= 0 ，head= 0
怎么统计该队列有多少个元素被取出：(tail + maxSize – head ) % maxSize
3.2 数组模拟环形队列代码实现
package main
import (
"errors"
"fmt"
"os"
)
type CircleQueue struct {
maxSize int
array [5]int
head, tail int
}
func (this *CircleQueue) Push(val int) (err error) {
if this.isFull() {
return errors.New("队列已经满了")
}
this.array[this.tail] = val
this.tail = (this.tail + 1) % this.maxSize
return
}
func (this *CircleQueue) Pop() (val int, err error) {
if this.isEmpty() {
return 0, errors.New("队列空了")
}
val = this.array[this.head]
this.head = (this.head + 1) % this.maxSize
return
}
func (this *CircleQueue) ListQueue() {
size := this.Size()
if size == 0 {
fmt.Println("队列为空")
}
tempHead := this.head
for i := 0; i < size; i++ {
fmt.Printf("arr[%d]=%d\t", tempHead, this.array[tempHead])
tempHead = (tempHead + 1) % this.maxSize
}
fmt.Println()
}
func (this *CircleQueue) isFull() bool {
return (this.tail+1)%this.maxSize == this.head
}
func (this *CircleQueue) isEmpty() bool {
return this.tail == this.head
}
func (this *CircleQueue) Size() int {
return (this.tail + this.maxSize - this.head) % this.maxSize
}
func main() {
queue := &CircleQueue{
maxSize: 5,
head: 0,
tail: 0,
}
fmt.Printf("%p", queue)
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.Push(val)
if err != nil {
fmt.Println("加入队列成功")
} else {
fmt.Println(err.Error())
}
case "get":
val, err := queue.Pop()
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println("从中取出了一个数", val)
}
case "show":
queue.ListQueue()
case "exit":
os.Exit(0)
}
}
}
Original: https://blog.csdn.net/ZN175623/article/details/127814827
Author: 南桑爱吃牛筋
Title: Go数据结构队列
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/653442/
转载文章受原作者版权保护。转载请注明原作者出处！