【数据结构算法经典题目刨析（c语言）】使用数组实现循环队列（图文详解）

💓 博客主页：C-SDN花园GGbond

⏩ 文章专栏：数据结构经典题目刨析(c语言)

一.题目描述

二.解题思路

1.循环队列的结构定义

2.队列初始化

3.判空

4.判满

5.入队列

6.出队列

7.取队首元素

8.取队尾元素

三.完整代码实现

Circular_Queue.h

Circular_Queue.c

一.题目描述

二.解题思路

1.循环队列的结构定义

包含

指向数组的指针，这是循环队列的底层结构
指向队首和队尾的整型变量front和rear
循环队列的空间大小k

typedef int CQueueDataType;
typedef struct MyCircularQueue//循环队列结构定义
{CQueueDataType* a;int front;int rear;int k;
} MyCircularQueue;

2.队列初始化

动态开辟一块循环队列结构体大小的空间
为数组指针的指向地址分配一块动态申请的内存，大小为k+1个空间，但实际使用k个（不申请k个是为了区别队列空和队列满，保留一个空间）
front和rear初始为0（要注意rear初始为0，意味着指向的是队尾的下一个元素）
k初始化为输入的值
最后返回该队列的地址

MyCircularQueue* myCircularQueueCreate(int k) //循环队列初始化
{MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));tmp->a = (CQueueDataType*)malloc(sizeof(CQueueDataType) * (k + 1));tmp->front = tmp->rear = 0;tmp->k = k;return tmp;
}

3.判空

对形参接收的地址判空
然后返回front==rear的结果

bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判空
{assert(obj);return obj->front == obj->rear;
}

4.判满

对形参接收的地址判空
队列满的条件理应是rear+1==front，但考虑到队列是一个"环形"的，要考虑值的溢出，所以改为（rear + 1 )% （k +1)==front

bool myCircularQueueIsFull(MyCircularQueue* obj) //判满
{assert(obj);return (obj->rear + 1) % (obj->k + 1)==(obj->front);
}

5.入队列

首先对形参接收的地址判空
然后判断队列是否满
如果有空间可用的话，在rear指向的位置插入数据
调整rear的位置，向后移动注意考虑循环的问题（rear+1）%（k+1），先对rear+1再对数组长度取模

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //入队列
{assert(obj);if (myCircularQueueIsFull(obj))return false;obj->a[obj->rear] = value;obj->rear = (obj->rear + 1) % (obj->k + 1);return true;
}

6.出队列

首先对形参接收的地址判空
然后判断队列是否为空
如果有数据可出的话，直接调整front的位置即可（不过应当考虑循环值溢出的问题）（front+1)%（k+1）
先对front+1再对数组长度取模

bool myCircularQueueDeQueue(MyCircularQueue* obj) //出队列
{assert(obj);if (myCircularQueueIsEmpty(obj))return false;obj->front = (obj->front + 1) % (obj->k + 1);return true;
}

7.取队首元素

首先对形参接收的地址判空
然后判断队列是否为空（空队列无数据可取）
然后返回front位置的元素即可

int myCircularQueueFront(MyCircularQueue* obj) //取队首元素
{assert(obj);if (myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}

8.取队尾元素

首先对形参接收的地址判空
然后判断队列是否为空（空队列无数据可取）
队尾元素是rear位置的前一个元素，考虑到直接-1可能会出错，正确的位置应该是（rear - 1 + k + 1) % (k + 1)，也可以简化成（rear +k ) % (k + 1)
返回该位置数据即可

int myCircularQueueRear(MyCircularQueue* obj) //取队尾元素
{assert(obj);if (myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}

三.完整代码实现

Circular_Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int CQueueDataType;
typedef struct MyCircularQueue//循环队列结构定义
{CQueueDataType* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k); //循环队列初始化bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);//入队列bool myCircularQueueDeQueue(MyCircularQueue* obj);//出队列int myCircularQueueFront(MyCircularQueue* obj);//取队首元素int myCircularQueueRear(MyCircularQueue* obj); //取队尾元素bool myCircularQueueIsEmpty(MyCircularQueue* obj); //判空bool myCircularQueueIsFull(MyCircularQueue* obj);//判满void myCircularQueueFree(MyCircularQueue* obj); //循环队列销毁

Circular_Queue.c

#include"Circular_Queue.h"MyCircularQueue* myCircularQueueCreate(int k) //循环队列初始化
{MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));tmp->a = (CQueueDataType*)malloc(sizeof(CQueueDataType) * (k + 1));tmp->front = tmp->rear = 0;tmp->k = k;return tmp;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //入队列
{assert(obj);if (myCircularQueueIsFull(obj))return false;obj->a[obj->rear] = value;obj->rear = (obj->rear + 1) % (obj->k + 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) //出队列
{assert(obj);if (myCircularQueueIsEmpty(obj))return false;obj->front = (obj->front + 1) % (obj->k + 1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) //取队首元素
{assert(obj);if (myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) //取队尾元素
{assert(obj);if (myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判空
{assert(obj);return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) //判满
{assert(obj);return (obj->rear + 1) % (obj->k + 1)==(obj->front);
}void myCircularQueueFree(MyCircularQueue* obj) //循环队列销毁
{free(obj->a);obj->front = obj->rear = 0;obj->k = 0;free(obj);obj = NULL;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/403358.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！