循环队列的应用和实现

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

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

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

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

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

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

img

图片来自于网络

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

入队算法: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)

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

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

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

代码示例:C语言创建循环队列

参考:

郝斌老师数据结构视频

ps: 微信公众号:Yopai,有兴趣的可以关注,每周不定期更新。不断分享,不断进步

上次更新: 3/14/2020, 7:38:21 AM

评 论: