记录下使用Go语言，利用silce实现循环队列。
本文代码github: https://github.com/zboyco/go-test/tree/master/queue/slice
需要链表实现队列可以参考：
Go 利用链表实现循环队列
1. 列举一下准备实现的功能列举一下准备实现的功能
- InitQueue 初始化队列
- Lenght 获取当前队列长度
- IsFull 是否满
- IsEmpty 是否空
- EnQueue 入队
- DeQueue 出队
队列使用slice作为存储数据的容器，使用slice而不使用array的原因是想在初始化的时候再指定队列长度，提高灵活性.
2. 简单实现:
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
| package queue
import "errors"
type Queue struct {
data []interface{}
front int
rear int
max int
}
func InitQueue(lenght int) (queue *Queue, err error) {
if lenght < 1 {
err = errors.New("长度不正确")
return
}
queue = &Queue{
data: make([]interface{}, lenght+1),
front: 0,
rear: 0,
max: lenght + 1,
}
return
}
func (q *Queue) Lenght() int {
return (q.rear - q.front + q.max) % q.max
}
func (q *Queue) IsFull() bool {
return ((q.rear + 1) % q.max) == q.front
}
func (q *Queue) IsEmpty() bool {
return q.front == q.rear
}
func (q *Queue) EnQueue(item interface{}) error {
if q.IsFull() {
return errors.New("队列已满")
}
q.data[q.rear] = item
q.rear = (q.rear + 1) % q.max
return nil
}
func (q *Queue) DeQueue() (item interface{}, err error) {
if q.IsEmpty() {
err = errors.New("队列为空")
return
}
item = q.data[q.front]
q.front = (q.front + 1) % q.max
return
}
|
3. 测试使用：
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
| package main
import (
"log"
"time"
"github.com/zboyco/go-test/queue/queue"
)
func main() {
q, err := queue.InitQueue(10)
if err != nil {
log.Panicln(err)
}
go read(q, 1)
go read(q, 2)
go read(q, 3)
i := 0
for {
time.Sleep(50 * time.Millisecond)
err := q.EnQueue(i)
if err != nil {
continue
}
i++
}
}
func read(q *queue.Queue, id int) {
for {
item, err := q.DeQueue()
if err != nil {
continue
}
log.Println("id", id, "------", item.(int))
}
}
|
注意上面测试输出：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 2019/03/20 15:42:43 id 1 ------ 0
2019/03/20 15:42:43 id 2 ------ 0
2019/03/20 15:42:43 id 3 ------ 0
2019/03/20 15:42:43 id 2 ------ 1
2019/03/20 15:42:43 id 1 ------ 1
2019/03/20 15:42:43 id 3 ------ 1
2019/03/20 15:42:43 id 3 ------ 2
2019/03/20 15:42:43 id 2 ------ 2
2019/03/20 15:42:43 id 1 ------ 2
2019/03/20 15:42:43 id 2 ------ 3
2019/03/20 15:42:43 id 1 ------ 3
2019/03/20 15:42:43 id 3 ------ 3
2019/03/20 15:42:43 id 3 ------ 4
2019/03/20 15:42:43 id 1 ------ 4
2019/03/20 15:42:43 id 2 ------ 4
|
可以看出队列里每一个值几乎都被三个goroutine取到了，这显然不是我们想要的结果，队列中的每一个值应该只能被一个goroutine获取才对。
4. 增加锁保证goroutine安全
可以看出上面的队列实现goroutine不安全，下面我们在数据操作中增加互斥锁，保证goroutine安全。
在队列结构体中增加读写锁:
1
2
3
4
5
6
7
| type Queue struct {
data []interface{}
front int
rear int
max int
sync.RWMutex
}
|
在入队EnQueue和出队DeQueue方法中使用写锁，其他方法中使用读锁，保证队列数据goroutine安全性。
加锁后代码如下：
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
|
func (q *Queue) Lenght() int {
q.RLock()
defer q.RUnlock()
return (q.rear - q.front + q.max) % q.max
}
func (q *Queue) IsFull() bool {
q.RLock()
defer q.RUnlock()
return q.isFull()
}
func (q *Queue) isFull() bool {
return ((q.rear + 1) % q.max) == q.front
}
func (q *Queue) IsEmpty() bool {
q.RLock()
defer q.RUnlock()
return q.isEmpty()
}
func (q *Queue) isEmpty() bool {
return q.front == q.rear
}
func (q *Queue) EnQueue(item interface{}) error {
q.Lock()
defer q.Unlock()
if q.isFull() {
return errors.New("队列已满")
}
q.data[q.rear] = item
q.rear = (q.rear + 1) % q.max
return nil
}
func (q *Queue) DeQueue() (item interface{}, err error) {
q.Lock()
defer q.Unlock()
if q.isEmpty() {
err = errors.New("队列为空")
return
}
item = q.data[q.front]
q.front = (q.front + 1) % q.max
return
}
|
5. 测试加锁后的队列
测试代码相同，直接运行，结果如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 2019/03/20 16:22:36 id 3 ------ 0
2019/03/20 16:22:36 id 2 ------ 1
2019/03/20 16:22:36 id 3 ------ 2
2019/03/20 16:22:36 id 1 ------ 3
2019/03/20 16:22:36 id 1 ------ 4
2019/03/20 16:22:36 id 2 ------ 5
2019/03/20 16:22:36 id 3 ------ 6
2019/03/20 16:22:36 id 2 ------ 7
2019/03/20 16:22:36 id 2 ------ 8
2019/03/20 16:22:37 id 3 ------ 9
2019/03/20 16:22:37 id 3 ------ 10
2019/03/20 16:22:37 id 2 ------ 11
2019/03/20 16:22:37 id 3 ------ 12
2019/03/20 16:22:37 id 3 ------ 13
2019/03/20 16:22:37 id 1 ------ 14
2019/03/20 16:22:37 id 2 ------ 15
2019/03/20 16:22:37 id 3 ------ 16
2019/03/20 16:22:37 id 2 ------ 17
2019/03/20 16:22:37 id 1 ------ 18
2019/03/20 16:22:37 id 3 ------ 19
2019/03/20 16:22:37 id 3 ------ 20
|
可以看到结果已经按照我们期望的顺序被不同的goroutine输出。
6. 结语
队列的实现还是比较简单的，我们只使用了slice实现，下次尝试使用channel实现。