# 数据结构-循环队列的应用和实现

作者：HerryLo (opens new window) 博客原文链接 (opens new window)

常见的线性结构应用有栈和队列，这次主要是聊一下队列。队列是一种先入先出的数据结构，类似的🌰🌰：排队买票，排在前面的先买，排在后面的后买(这里不说插队的情况)。

在软件开发中，就有应用到队列知识，比如：任务队列、事件队列、消息队列，和时间相关的东西都有队列的影响。

队列分为两种，链式队列和静态队列，前者是链表构成，后者是数组构成；这里说到的循环队列属于静态队列，而有一点必须要说的是：静态队列必须是循环队列。

为什么静态队列必须是循环队列？

对于长度一定的数组，存储的空间是确认的，在队列的入队和出队的过程中，数组中的存储空间需要不断的重复使用，那么这里的“不断重复使用”，就需要循环来实现，否则会出现空间的浪费。对于循环队列，只需要两个参数：front、rear，front代表的是队列第一个元素的下标，而rear代表的是队列最后一个有效元素的下一个元素的下标。

请看下图中出队和入队的过程：

图片来自于网络

有以上可以知道出队和入队算法如下：

入队算法：rear = (rear +1)%数组长度

出队算法：front = (front+1)%数组长度

在了解到出队、入队算法之后基本就可以自己来创建和维护一个循环队列了！

# C语言循环队列实现

首先我们先来做好初始化的准备：

// 这里直接将数据类型定为整型,同时确定队列的长度为6
int len = 6;

typedef struct Queue {
    int *pArray; // 数组
    int pFront;  // 头下标
    int pRear;   // 尾下标
}Queue;

// 队列初始化
void initQueue(Queue * q);
// 入队
bool inputQueue(Queue * q, int value)
// 出队
bool outputQueue(Queue * q, int *value)
// 遍历
void traverseQueue(Queue * q)
// 是否满队
bool isFullQueue(Queue * q)
// 是否空队
bool isEmptyQueue(Queue * q)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我们需要以上这些基本的函数来保证队列的正常操作。下面是函数的实现

void initQueue(Queue * q){
    // 动态分配内存
    q->pArray = (int *)malloc(sizeof(int)*len); 
    q->pFront = 0;
    q->pRear = 0;
}
// 是否满队
bool isFullQueue(Queue * q){
    if((q->pRear+1)/len == q->pFront)
        return true;
    return false;
}
// 是否空队
bool isEmptyQueue(Queue * q){
    if(q->pRear == q->pFront)
        return true;
    return false;
}
// 入队
bool inputQueue(Queue * q, int value){
    if(isFullQueue(q))
        return false
    else
        q->pArray[(q->qRear+1)%len] = value
        q->qRear = (q->qRear+1)%len
}
// 出队
bool outputQueue(Queue * q, int *value){
    if(isFullQueue(q))
        return false
    else
        *value = q->pArray[q->qFront]
        q->qFront = (q->qFront+1)%len
}
void traverseQueue(Queue * q){
    printf("遍历队列中的值\n");
    int front = q->qFront
    while(index != q->qRear){
        printf("%d\n", q->PArrry[front]);
        front = (q->qFront+1)%len;
    }
}

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

main函数中创建链表：

int main(int argc, const char * argv[]) {
    printf("---------循环队列构建---------\n");
    Queue q;
    int value;
    
    initQueue(&q);
    // 入队
    inputQueue(&q, 12);
    inputQueue(&q, 4556);
    // 遍历
    traverseQueue(&q);
    // 出队
    outputQueue(&q, &value);
    printf("出队值为：%d\n", value);
    traverseQueue(&q);
    
    return 0;
}