白羊的空间

Go 利用链表实现循环队列

记录下使用Go语言，利用silce实现循环队列。

本文代码github: https://github.com/zboyco/go-test/tree/master/queue/link

需要slice实现队列可以参考：
Go 利用slice实现循环队列

1. 列举一下准备实现的功能列举一下准备实现的功能

这里只使用单向链表实现队列功能，实现下列方法:

  • Enqueue 入队
  • Dequeue 出队

使用链表实现队列相比较slice的优势是，队列容量可以不受限制。（当然也可以在结构体中增加容量和长度字段，限制队列长度）

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

import (
	"errors"
	"sync"
)

// 节点
type node struct {
	value interface{} // 值
	next  *node       // 下一个节点
}

// Queue 队列
type Queue struct {
	front      *node // 头
	rear       *node // 尾
	sync.Mutex       // 锁
}

// Enqueue 入队
func (q *Queue) Enqueue(item interface{}) error {
	q.Lock()
	defer q.Unlock()
	if item == nil {
		return errors.New("数据不可为空")
	}
	newNode := &node{value: item}
	if q.front == nil {
		q.front = newNode
	}
	if q.rear != nil {
		q.rear.next = newNode
	}
	q.rear = newNode
	return nil
}

// Dequeue 出队
func (q *Queue) Dequeue() (item interface{}, err error) {
	q.Lock()
	defer q.Unlock()
	if q.front == nil {
		err = errors.New("队列为空")
		return
	}
	item = q.front.value
	if q.front.next == nil {
		q.front = nil
	} else {
		q.front = q.front.next
	}
	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
package main

import (
	"log"
	"time"

	"github.com/zboyco/go-test/queue/link/queue"
)

func main() {
	q := &queue.Queue{}

	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 {
			// log.Println(err)
			continue
		}
		i++
	}
}

func read(q *queue.Queue, id int) {
	for {
		item, err := q.Dequeue()
		if err != nil {
			// log.Println(err)
			// time.Sleep(100 * time.Millisecond)
			continue
		}
		log.Println("id", id, "------", item.(int))
	}
}

输出结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2019/03/20 17:44:43 id 2 ------ 0
2019/03/20 17:44:43 id 2 ------ 1
2019/03/20 17:44:43 id 2 ------ 2
2019/03/20 17:44:43 id 2 ------ 3
2019/03/20 17:44:43 id 3 ------ 4
2019/03/20 17:44:44 id 2 ------ 5
2019/03/20 17:44:44 id 1 ------ 6
2019/03/20 17:44:44 id 1 ------ 7
2019/03/20 17:44:44 id 1 ------ 8
2019/03/20 17:44:44 id 3 ------ 9
2019/03/20 17:44:44 id 2 ------ 10
2019/03/20 17:44:44 id 2 ------ 11
2019/03/20 17:44:44 id 1 ------ 12
2019/03/20 17:44:44 id 1 ------ 13
2019/03/20 17:44:44 id 3 ------ 14
2019/03/20 17:44:44 id 1 ------ 15

5. 结语

需要注意：
**- 入队时队列为空

  • 出队后队列为空**
Golang