Go数据结构队列

二 队列

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 数组模拟队列代码实现

// 队列先入先出
// 思路分析
// 创建一个数组array，是作为队列的一个字段
// fronnt初始化为-1
// real表示队列尾部，初始化-1
// 完成队列的进本操作
// AddQueue 加入数据到队列  GetQueue 从队列中取出数据 ShowQueue显示队列

//使用一个结构体管理队列

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 { //重要的一个提示;rear是队列尾部，含最后的元素
		return errors.New("queue full")
	}
	this.rear++ //rear 后移
	this.array[this.rear] = val
	return
}

//显示队列,找到队首然后遍历到队尾

func (this *Queue) ShowQueue() {
	
	fmt.Println("队列当前的情况是")
	//this.front不包含队首的元素
	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)

		}

	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

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    //4
	array      [5]int //数组
	head, tail int    //指向队列的队首，指向队列的队尾
}

//入队列

func (this *CircleQueue) Push(val int) (err error) {
	if this.isFull() {
		return errors.New("队列已经满了")
	}
	//分析出this.tail，在队列尾部，但是不包含最后的元素
	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("队列空了")
	}
	//取出,head指向队首并且包含这个元素就是含队首的元素
	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("队列为空")
	}
	//设计一个辅助变量,指向head
	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,
	}
	//入队列 AddQueue（push） GetQueue（pop）

	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)

		}

	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124