-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQueueBasedOnArray.go
More file actions
66 lines (57 loc) · 1.37 KB
/
Copy pathQueueBasedOnArray.go
File metadata and controls
66 lines (57 loc) · 1.37 KB
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
package queue
import (
"fmt"
)
type QueueBasedOnArray struct {
items []interface{}
capacity uint
head uint//指向队列的头部索引(索引位置保存第一个元素的值,0特殊,tail==0 && head==0 时,head索引处不存在值)
tail uint//指向队列的尾部索引(索引位置不保存值)
}
func NewQueueBasedOnArray(capacity uint) *QueueBasedOnArray {
return &QueueBasedOnArray{
items: make([]interface{}, 0, capacity),
capacity: capacity,
head: uint(0),
tail: uint(0),
}
}
func (this *QueueBasedOnArray) IsFull() bool {
return this.tail >= this.capacity && this.head == uint(0)
}
func (this *QueueBasedOnArray) IsEmpty() bool {
return this.head == this.tail
}
func (this *QueueBasedOnArray) Enqueue(v interface{}) bool {
if this.IsFull() {
return false
}
//需要搬移数据
if this.tail == this.capacity {
for i := this.head; i < this.tail; i++ {
this.items[i - this.head] = this.items[i]
}
this.tail = this.tail - this.head
this.head = uint(0)
}
if this.tail >= uint(len(this.items)) {
this.items = append(this.items, v)
} else {
this.items[this.tail] = v
}
this.tail++
return true
}
func (this *QueueBasedOnArray) Dequeue() interface{} {
if this.IsEmpty() {
return nil
}
item := this.items[this.head]
this.head++
if this.head == this.tail {
this.head = uint(0)
this.tail = uint(0)
}
fmt.Println(this)
return item
}