数据结构之环形队列

@TOC

一.环形队列的定义及其特点

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

特点：

对于一个普通队列来说，每出队一次，头指针就必须往后移一位，这样使用过的空间就无法再重复使用，（头指针无法回移），即使队列元素小于队列大小，也无济于事，造成空间的浪费。

而对于循环队列来说，可以重复利用使用过的空间。解决了普通队列的问题。

基于循环队列的特点：我们可以使用数组或者循环链表来实现循环队列。

使用数组实现的话，尾指针到数组的大小时，回溯到头位置即可。

在这里给出一道题来实现环形队列。数据

二.使用数组来实现环形队列

首先，需要了解清楚的一件事是：如何判断环形队列的数据是否为空或者是否满了？

假如创建一个大小为4的环形队列，判断环形队列是否为空很简单，如果头指针和尾指针相等，则队列是空的，因为如果插入数据，尾指针一定往后移动。

环形队列插满数据是这样的：

此时头指针和尾指针指向的位置也是相同的！

所以当队列满队的时候无法区分是队空还是队满。

解决办法：

假如环形队列大小是k，我们就创建k+1大小的环形队列。

只需判断 （tail+1）%（k+1）是否等于head 即可。

1.创建一个队列

解读：对于普通队列来说，需要头指针和尾指针来维护入队和出队操作，入队时尾指针后移，出队时头指针后移。在环形队列中也是如此。

以下代码中的head和front是一样的。

typedef struct 
{
    int*a;
    int head;//队头
    int tail;//队尾,指向插入元素的下一个
    int k; //环形队列大小
} MyCircularQueue;

2.初始化队列

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue*p = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    assert(p);
    p->a = (int*)malloc(sizeof(int)*(k+1));
    p->head = p->tail = 0;
    p->k = k; //环形队列大小
    return p;
}

开辟两块空间，一块空间是结构体的空间，一块空间是结构体的数组的空间。

3. 判断环形队列是否为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

解读：环形队列是否为空就是判断头指针和尾指针是否相等，如果相等整个环形队列就为空，如果是其他情况，则环形队列至少有一个以上的数据。

4.判断环形队列是否已满

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->tail+1)%(obj->k+1) ==obj->head)
    {
        return true;
    }
    return false;
}

判断环形队列是否已满，就是判断tail+1是否等于head，如果

5. 向循环队列插入元素，插入成功返回真

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        //满了
        return false;
    }
    obj->a[obj->tail] =value;
    //考虑特殊情况，如果插入之后tail是在外面，应该让tail回到0位置
    if(obj->tail+1 == obj->k+1) 
    {
        obj->tail = 0;
    }  
    else
    {
        ++obj->tail;
    }
    //也可以这样写
    // ++obj->tail;
    // obj->tail%=(obj->k+1);
    return true;
}

解读：

1. 这里应该考虑的一种特殊情况是，假如插入的数据在环形队列的末尾，尾指针应该指向下一个位置，此时走出了数组的范围，所以需要回到数组0位置。2.如果环形队列满了，则不能再插入了。

6.删除环形链表的数据

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //也是考虑特殊情况，如果删除后head在队列外面，则应让head回到0位置
    if(obj->head+1 == obj->k+1)
    {
        obj->head = 0;
    }
    else
    {
        ++obj->head;
    }
    //也可以这样写
    // ++obj->head;
    // obj->head%=obj->k+1;
    return true;
}

解读：
需要考虑特殊情况：特殊情况如下图：

7. 取队头元素

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->head];
}

8.取队尾元素

int myCircularQueueRear(MyCircularQueue* obj) {
    //取队尾元素有特殊情况，如果tail在0位置，那么需要返回
    //它的前一个，也就是第k个
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    if(obj->tail == 0)
    {
        return obj->a[obj->k];
    }
    else
    {
        return obj->a[obj->tail-1];
    }
    //也可以这样写
    //return (obj->tail+obj->k)%(obj->k+1);
}

取队尾元素有一种特殊情况：

假如tail是在0位置，取队尾元素之后，tail需要回退到上一个位置，即k+1位置处。

8.释放空间

void myCircularQueueFree(MyCircularQueue* obj) {
    //注意结构体有两层，需要先释放内层
    free(obj->a);
    obj->a = NULL;
    free(obj);
}

总结

环形队列在普通队列的基础上优化了空间重复利用问题，使空间利用率更高。实际生活中使用队列的问题还是有很多的，比如营业厅，医院，银行的自动排队出票的机子，也是通过队列的先进先出的特点来实现的。