数据结构—循环队列（环形队列）

循环队列的概念及结构

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

注：循环队列的空间大小是固定的

循环队列的实现

环形队列可以使用数组实现（超出数组的范围回到起始位置），也可以使用循环链表实现（尾指针的next指向头节点）。选用数组实现循环队列更好，因为数组缓存利用率更高，没有扩容的代价。

环形队列实际开辟的空间大小要比所存数据的队列长度多开辟一个空间的大小。如果环形队列实际开辟的空间大小和所存储数据个数一样时，会导致环形队列所处空的状态和满的状态是一样的。这样便无法区分。

因此环形队列必须多留出一个空间，这个空间不能存放数据，这样才能很好的区别环形队列的状态是空还是满。

在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。

循环队列的定义

循环队列选择用数组实现，循环队列需要用一个指针来指向存储队列数据的空间，用两个变量来记录队列中存储数据的起始（对头）和末尾（队尾）的数组位置，最后用一个变量记录队列的存储数据的最大容量。

typedef struct {
    int *a;
    int front;
    int tail;
    int k;
} MyCircularQueue;
1
2
3
4
5
6

循环队列的初始化

循环队列的初始化首先创建一个循环队列，其次对该结构体的成员进行初始化即可。

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cur=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cur->a=(int *)malloc(sizeof(int)*(k+1));
    cur->k=k;
    cur->front=0;
    cur->tail=0;
    return cur;
}
1
2
3
4
5
6
7
8

注：k表示的是设置队列的长度

循环队列的入队列

入队列操作首先要判断循环队列是否已满，如果满了则返回假；如果没满则向循环队列插入一个数据（即在tail位置放数据）然后tail向后挪动一个位置，最后返回真。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }

    obj->a[obj->tail]=value;
    obj->tail++;
    obj->tail=obj->tail%(obj->k+1);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

注：tail的位置为k+1时，就需要对tail进行处理防止tail对数组进行越界访问。这也遵循了循环队列的原则，当访问到数组末尾时再次访问应该访问到数组的起始位置。

循环队列的出队列

出队列操作首先判断循环队列是否为空，如果为空了，则出队列失败返回假；如果不为空则从循环队列中删除一个元素（即只需将front往后挪一个位置即可），如果成功删除则返回真。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front++;
    obj->front%=obj->k+1;
    return true;
}
1
2
3
4
5
6
7
8
9
10

注：当front为k+1时处理方式和入队列的tail类似。

获取循环队列的对头数据

获取循环队列的对头数据首先判断循环队列是否为空，如果为空则返回-1；如果不为空只需通过front的位置获取数组中的数据并返回该数据即可。

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}
1
2
3
4
5
6
7
8

获取循环队列的对尾数据

获取循环队列的对尾数据首先判断循环队列是否为空，如果为空则返回-1；如果不为空只需通过tail获取tail的前一个位置的数组中的数据并返回该数据即可。

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    int prevtail=obj->tail-1;
    if(obj->tail==0)
    {
        prevtail=obj->k;
    }
    
    return obj->a[prevtail];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注：当tail为0时，此时取队尾数据时取的是数组下标为k的元素数据。因为tail表示的是最后一个有效数据的下一个位置。

循环队列的判空

循环队列的判空只需判断队头和队尾是否相等即可

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->front==obj->tail;
}
1
2
3
4

循环队列的判满

循环队列的判满只需判断队尾的下一个位置和队头是否相等即可

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return obj->front==((obj->tail)+1)%(obj->k+1);
}
1
2
3
4

注：当tail为k时tail的下一个位置为0，此时处理情况和出入队列的处理情况类似。

循环链表的销毁

循环链表的销毁首先要对循环链表结构体中的成员进行释放，然后再对循环链表进行释放即可。

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    free(obj->a);
    free(obj);
    obj=NULL;
}

1
2
3
4
5
6
7

注意：

• 环形队列中存储数据的空间是一开始就要创建好的，删除数据时是front指针往后走，存储数据的空间不销毁。插入数据时是往tail所指向的空间放数据，不申请空间，tail往后走。
• 循环队列如果用链表实现最好用双向链表实现，单向链表不好去找循环队列的队尾数据，而且采用链表的形式实现需要定义节点的结构体以及在初始化方面需要创建k+1个节点并建立连接，这样操作起来很麻烦没有数组省事，因此用数组实现循环队列更好。