- 环形队列的特点是,不需要进行动态的内存释放和分配,使用固定大小的内存空间反复使用。
非常的简单和高效
- 相信大家对队列都不陌生。队列是一种具有先进先出（FIFO）的抽象数据类型。如下图所示：
队列原理示意图
可以使用多种数据结构来实现一个基本的队列：
环形队列
判断队列是否满
-
front：表示队列的第一个元素的位置，front初始值默认为0
-
rear：表示队列的最后一个元素的后一个位置，rear初始值默认为0，因为需要空出一个空间作为“约定”
-
当队列满时，条件是(rear + 1) % maxSize == front
-
当队列为空，条件是rear = front
-
当这样分析后，队列中有效的数据个数为(rear + maxSize - front) % maxSize
-
队列满了取出一个，再添加一个时，showqueue方法会越界的，要取模
应用场景
Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues.
Traffic system: In computer controlled traffic system, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set.
CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.
Lock Free Queue: When high performance is required, we don’t want to use lock. Circular Queue can is the top 1 data structure for lock free queue.
实现方式
环形队列使用数组来实现。
Go
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
|
package circular_queue
import (
"errors"
)
type CircularQueue struct {
n int64
head int64
tail int64
data []int
}
func (this *CircularQueue) IsEmpty() bool {
return this.head == this.tail
}
func (this *CircularQueue) IsFull() bool {
return this.tail-this.head == this.n-1
}
func (this *CircularQueue) Push(value int) error {
if this.IsFull() {
return errors.New("The queue is full")
}
this.data[this.tail&(this.n-1)] = value
this.tail += 1
return nil
}
func (this *CircularQueue) Pop() (value int, err error) {
if this.IsEmpty() {
err = errors.New("The queue is empty")
return
}
value = this.data[this.head&(this.n-1)]
this.head += 1
return
}
func New(n int64) (*CircularQueue, error) {
if n&(n-1) != 0 {
return nil, errors.New("n must be the power of 2")
}
return &CircularQueue{
n: n,
head: 0,
tail: 0,
data: make([]int, n, n),
}, nil
}
|
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
|
package circular_queue
import (
"testing"
)
func TestQueue(t *testing.T) {
var n int64 = 7
queue, err := New(n)
if err == nil {
t.Error("There should be an error")
}
n = 8
queue, err = New(n)
if err != nil {
t.Error("There should be no error")
}
if queue.IsEmpty() == false {
t.Error("The queue should be empty now")
}
if queue.IsFull() {
t.Error("The queue should not be full now")
}
for i := 1; i < 8; i++ {
queue.Push(i)
}
if queue.IsEmpty() {
t.Error("The queue should not be empty now")
}
if queue.IsFull() == false {
t.Error("The queue shoule be full now")
}
for i := 1; i < 8; i++ {
value, err := queue.Pop()
if err != nil {
t.Error("There should be no error")
}
if value != i {
t.Errorf("The value poped should be %d, but now is %d", i, value)
}
}
if queue.IsEmpty() == false {
t.Error("The queue should be empty now")
}
_, err = queue.Pop()
if err == nil {
t.Error("There should be an error")
}
}
|
时间复杂度
O(1)
原文链接：https://www.jianshu.com/p/8691a82d433a
