忽忆故人今总老。贪梦好。茫然忘了邯郸道。
简述
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的先进先出，其实就对应了我们生活中的先到先得。比如你在食堂打饭，肯定是队头的人先打饭。还有在银行的叫号系统，那其实也是一个队列。
定义
队列肯定要装不只一个对象，所以我们需要一个切片作为容器。并且，我们还需要两个标记位，一个指向队列的头 front ，一个指向队列的尾 rear 。并且我们也需要一个队列的容量 size 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| package main
type Queue struct {
container []int
front int
rear int
size int
}
func NewQueue(size int) *Queue {
return &Queue{
container: make([]int,size),
front: 0,
rear: 0,
size: 0,
}
}
|
队列的基本操作
队列的基本操作包括如下几种
- 初始化队列：InitQueue（size） 操作结果：初始化一个空队列。
- 判断队列是否为空：IsEmpty（） 操作结果：若队列为空则返回 true，否则返回 false。
- 判断队列是否已满：IsFull（）。 操作结果：若队列为满则返回 true，否则返回 false。
- 入队操作：EnQueue（data） 操作结果：在队列的队尾插入 data。
- 出队操作：DeQueue（） 操作结果：将队列的队头元素出队，并返回出队元素的值。
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
| package main
import "fmt"
type Queue struct {
container []int
front int
rear int
size int
}
func NewQueue(size int) *Queue {
return &Queue{
container: make([]int,size),
front: 0,
rear: 0,
size: 0,
}
}
func (q *Queue) IsEmpty () bool {
if q.size == 0 {
return true
}
return false
}
func (q *Queue) IsFull () bool {
if q.size == len(q.container) {
return true
}
return false
}
func (q *Queue) EnQueue (a int) bool {
if q.IsFull() {
return false
}
q.container[q.rear] = a
q.rear++
q.size++
return true
}
func (q *Queue) Dequeue () (bool,int) {
if q.IsEmpty() {
return false,0
}
ret := q.container[q.front]
q.front++
q.size--
return true,ret
}
func main() {
queue := NewQueue(10)
for i := 0; i < 5 ; i++ {
queue.EnQueue(i)
}
for i := 0; i < 6; i++ {
fmt.Println(queue.Dequeue())
}
}
|
循环队列
我们在每次让元素出队的时候，队列的头指针是不断的在往后移的。总有一天，队头指向的索引值比我们的容器长度还要大，那种情况出现的时候要怎么办呢？
既然在使用过程中，front 和 rear 都只能往后移导致有用的空间被浪费了。那么能不能去做一个可以再利用，不浪费一点空间的队列呢？
答案就是我们可以做一个循环队列。循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。
判断队列的状态
用 size 表示队列的实际长度，而不用 rear - front 呢？其实就是为了循环队列。各位想一想，在循环时，rear 和 front 是说不清谁大谁小的，有可能减出一个负数。而我们使用 size 就不会出现这种问题，因为只有入队操作才会让 size + 1， 也只有出队操作能让 size - 1。所以这里我们的判断队列状态的函数可以直接不变就拿来使用。解决了循环队列中的最难点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func (this *Queue) IsEmpty() bool {
if this.size == 0 {
return true
}
return false
}
func (this *Queue) IsFull() bool {
if this.size == len(this.arr) {
return true
}
return false
}
|
计算索引
解决了判断状态问题，我们可以继续解决索引值的计算问题了。首先是入队操作，在入队时。我们只要对 rear 先对队列的容量取余，计算出的索引值就是我们要插入的位置。
对于出队操作，我们要出队的元素是 front 对队列容量取余所指向的元素，取出之后下一个 front 的值需要先对队列的容量取余再加 1。 到这里我们就可以写出新的队列的完整代码了。
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
| package main
import (
"fmt"
)
type Queue struct {
container []int
front int
rear int
size int
}
func NewQueue (k int) *Queue {
return &Queue{
make([]int, k),
0,
0,
0,
}
}
func (this *Queue) EnQueue(value int) bool {
if this.container == nil || this.IsFull() {
return false
}
this.container[this.rear%len(this.container)] = value
this.rear = this.rear%len(this.container) + 1
this.size++
return true
}
func (this *Queue) DeQueue() (bool,int) {
if this.container == nil || this.IsEmpty() {
return false,0
} else {
ret := this.container[this.front%len(this.container)]
this.front = this.front%len(this.container) + 1
this.size--
return true,ret
}
}
func (this *Queue) IsEmpty() bool {
if this.size == 0 {
return true
}
return false
}
func (this *Queue) IsFull() bool {
if this.size == len(this.container) {
return true
}
return false
}
func main() {
queue := NewQueue(5)
for i:=0; i<3; i++{
for j:=0;j<5;j++ {
queue.EnQueue(j)
}
for k:=0;k<3;k++ {
fmt.Println(queue.DeQueue())
}
}
}
|