golang算法练习：基于array的队列实现

发表于 | 阅读次数：
本文字数： 4.5k | 阅读时长 ≈ 4 分钟

##

需求

队列，很常用的FIFO(先入先出)数据模型，下面尝试使用golang的array数据结构来实现队列模型
备注：需求和运行输出结果均已在代码中注释

简单队列

代码：

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
package main

import (
	"fmt"
)

type SingleQueue struct {
	Cap  int    `json:cap`  // 容量
	Arr  [5]int `json:arr`  // 成员数组
	Head int    `json:head` // index编号
	Tail int    `json:tail` // index编号
}

func (singleQueue *SingleQueue) append(i int) {
	// 队尾加入
	if singleQueue.isFull() {
		fmt.Println("Queue is already full")
		return
	}
	if singleQueue.Head == -1 {
		// 第一次加入元素时
		singleQueue.Head = 0
		singleQueue.Tail = 0
		singleQueue.Arr[singleQueue.Tail] = i
	} else {
		singleQueue.Tail += 1
		singleQueue.Arr[singleQueue.Tail] = i
	}
	fmt.Printf("Append %d ok!\n", i)
}

func (singleQueue *SingleQueue) isFull() (isFull bool) {
	if singleQueue.Tail == (singleQueue.Cap - 1) {
		return true
	}
	return
}

func (singleQueue *SingleQueue) getQueLength() (length int) {
	// 获取singleQueue当前元素数量
	return singleQueue.Tail - singleQueue.Head + 1
}

func (singleQueue *SingleQueue) isEmpty() (isEmpty bool) {
	// 队列是否为空
	if singleQueue.Tail == singleQueue.Head {
		return true
	}
	return
}

func (singleQueue *SingleQueue) pop() (elem int) {
	// 队首弹出
	if singleQueue.isEmpty() {
		fmt.Println("Queue is already empty")
		return
	}

	elem = singleQueue.Arr[singleQueue.Head]
	singleQueue.Head += 1
	fmt.Printf("Pop %d ok!\n", elem)
	return
}

func (singleQueue *SingleQueue) list() {
	// 列出singleQueue当前所有的元素
	fmt.Println("Here are all elements in this queue:")
	for i := singleQueue.Head; i <= singleQueue.Tail; i++ {
		fmt.Printf("index[%d],value=%d\n", i, singleQueue.Arr[i])
	}
}

func main() {
	var s = SingleQueue{
		Cap:  5,
		Head: -1,
		Tail: -1,
	}
	s.append(1)
	s.append(2)
	s.append(3)
	s.append(4)
	s.append(5)
	s.append(6) // Queue is already full
	s.list()
	fmt.Println(s.getQueLength()) // 5
	s.pop()                       // Pop 1 ok!
	fmt.Println(s.getQueLength()) // 4
	s.append(6)                   // Queue is already full
	/*
		分析:单向队列，队首弹出后，腾出了空间，却无法给新的元素加入使用，因为容量评估无法感知head的偏移，因此，实用性很低，改进呢？改为可循环队列
	*/

}

问题
array容量是有限的，这个队列存在空间浪费的问题，拥有空闲空间却无法再插入元素。怎么解决? 对代码简单改造,实现为循环队列即可，在关键位置进行取模运算。

循环队列

代码:

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
package main

import (
	"fmt"
)

type CircleQueue struct {
	Cap  int    `json:cap`  // 容量
	Arr  [5]int `json:arr`  // 成员数组
	Head int    `json:head` // index编号
	Tail int    `json:tail` // index编号
}

func (circleQueue *CircleQueue) append(i int) {
	// 队尾加入
	if circleQueue.isFull() {
		fmt.Println("Queue is already full")
		return
	}
	if circleQueue.Head == -1 {
		// 第一次加入元素时
		circleQueue.Head = 0
		circleQueue.Tail = 0
		circleQueue.Arr[circleQueue.Tail] = i
	} else {
		circleQueue.Tail = (circleQueue.Tail + 1) % circleQueue.Cap
		circleQueue.Arr[circleQueue.Tail] = i
	}
	fmt.Printf("Append %d ok!\n", i)
}

func (circleQueue *CircleQueue) isFull() (isFull bool) {
	if (circleQueue.Tail+1)%circleQueue.Cap == circleQueue.Head {
		// 环形队列，尾部下一个是首部，则说明空间已用完，因为是环形的，所以需要取模后再比较
		return true
	}
	return
}

func (circleQueue *CircleQueue) getQueLength() (length int) {
	// 获取circleQueue当前元素数量
	length = ((circleQueue.Tail + circleQueue.Cap - circleQueue.Head) % circleQueue.Cap) + 1
	return
}

func (circleQueue *CircleQueue) isEmpty() (isEmpty bool) {
	// 队列是否为空
	if circleQueue.Tail == circleQueue.Head {
		return true
	}
	return
}

func (circleQueue *CircleQueue) pop() (elem int) {
	// 队首弹出
	if circleQueue.isEmpty() {
		fmt.Println("Queue is already empty")
		return
	}

	circleQueue.Head = (circleQueue.Head + 1) % circleQueue.Cap
	elem = circleQueue.Arr[circleQueue.Head]
	fmt.Printf("Pop %d ok!\n", elem)
	return
}

func (circleQueue *CircleQueue) list() {
	// 列出circleQueue当前所有的元素
	//fmt.Println(circleQueue.Head)
	fmt.Println("Here are all elements in this queue:")
	for i := 0; i < circleQueue.getQueLength(); i++ {
		index := (i + circleQueue.Head) % circleQueue.Cap
		fmt.Printf("index[%d],value=%d\n", index, circleQueue.Arr[index])
	}
}

func main() {
	var c = CircleQueue{
		Cap:  5,
		Head: -1,
		Tail: -1,
	}
	c.append(1)
	c.append(2)
	c.append(3)
	c.append(4)
	c.append(5)
	c.append(6) // Queue is already full
	c.list()
	fmt.Println(c.getQueLength()) // 5
	c.pop()                       // Pop 1 ok!
	fmt.Println(c.getQueLength()) // 4
	c.append(6)                   // Append 6 ok!
	c.list()                      // 6加入了队尾
	/*
		分析:环形队列，弹出后的空间可循环复利用，符合实际使用价值
	*/

}

问题
循环队列更满足实际使用需求，但毕竟array容量有限，一次申请太大的容量也很浪费资源，怎么解决这个问题？答曰：链表，动态加减元素，独立的内存空间，不需要一次性申请大量内存。
链表实现参考下篇

赏一瓶快乐回宅水吧～
-------------本文结束感谢您的阅读-------------