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

相信大家对队列都不陌生。队列是一种具有先进先出（FIFO）的抽象数据类型。如下图所示：

队列原理示意图

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

• 数组
• 链表

简单队列的应用场景有限，但是它的一些变种却有着非常广泛的应用。

• 环形队列
• 双端队列
• 优先队列

在这里，我们只介绍环形队列

环形队列

应用场景

• 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

• circular_queue.go

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

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)