环形队列(Circular Queue)和应用场景

简书博主「筑梦之队」收录于 Go

2023-02-24 约 1100 字预计阅读 2 分钟 - 次阅读

本文为转载文章，主要讲环形队列(Circular Queue)和应用场景。

1. 前言

环形队列的特点是,不需要进行动态的内存释放和分配,使用固定大小的内存空间反复使用。非常的简单和高效
相信大家对队列都不陌生。队列是一种具有先进先出（FIFO）的抽象数据类型。如下图所示：

/images/20230224/img.png
队列原理示意图

可以使用多种数据结构来实现一个基本的队列：

数组
链表简单队列的应用场景有限，但是它的一些变种却有着非常广泛的应用。
环形队列
双端队列
优先队列在这里，我们只介绍环形队列

2. 环形队列

/images/20230224/img_1.png

3. 判断队列是否满

front：表示队列的第一个元素的位置，front初始值默认为0
rear：表示队列的最后一个元素的后一个位置，rear初始值默认为0，因为需要空出一个空间作为“约定”
当队列满时，条件是(rear + 1) % maxSize == front
当队列为空，条件是rear = front
当这样分析后，队列中有效的数据个数为(rear + maxSize - front) % maxSize
队列满了取出一个，再添加一个时，showqueue方法会越界的，要取模

4. 应用场景

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.

5. 实现方式

环形队列使用数组来实现。

5.1 Go

circular_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
}

circular_queue_test.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
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")
    }
}

6. 时间复杂度

O(1)

原文链接：https://www.jianshu.com/p/8691a82d433a