目录
前言
本篇博客介绍栈和队列的表示和实现。
1.为啥要使用循环队列
上篇文章中我们知道了顺序队列的用法，但是顺序队列有个缺点就是会“假溢出”，浪费大量的存储空间，关于假溢出的问题，个人感觉数据结构里里面的这段解释比较好，就直接截图放下面了，大家自行阅读吧。
图1.顺序队列假溢出的问题
2.队列的顺序表示和实现
1.定义
#define MAX_QUEUE_SIZE 100 // 循环队列的最大容量
typedef int Status;
typedef int ElemType;
typedef struct {
ElemType *data; // 存储数据的数组
int front; // 头指针，指向队首元素
int rear; // 尾指针，指向队尾元素的下一个位置
int maxSize; // 循环队列的最大容量
} CircularQueue;2.初始化
队列初始化的时候，队头和队尾指针均为0
// 初始化循环队列
Status initCircularQueue(CircularQueue *queue, int maxSize) {
queue->data = (ElemType *)malloc(sizeof(ElemType) * maxSize);
if (!queue->data) {
return 0; // 内存分配失败
}
queue->front = queue->rear = 0;
queue->maxSize = maxSize;
return 1; // 初始化成功
}3.销毁
释放队列存储空间
// 销毁循环队列
void destroyCircularQueue(CircularQueue *queue) {
free(queue->data);
}4.清空
// 清空循环队列
void clearCircularQueue(CircularQueue *queue) {
queue->front = queue->rear = 0;
}5.空队列
队头和队尾相同的时候为空队列。
// 判断循环队列是否为空
Status isEmptyCircularQueue(CircularQueue *queue) {
return queue->front == queue->rear;
}6.队列长度
比较栈顶和栈顶的指针
// 获取循环队列长度
int circularQueueLength(CircularQueue *queue) {
return (queue->rear - queue->front + queue->maxSize) % queue->maxSize;
}7.获取队头
获取队头元素。
// 获取循环队列的队首元素
Status getCircularQueueFront(CircularQueue *queue, ElemType *element) {
if (isEmptyCircularQueue(queue)) {
return 0; // 队列为空
}
*element = queue->data[queue->front];
return 1; // 成功获取队首元素
}8.入队
// 入队
Status enCircularQueue(CircularQueue *queue, ElemType element) {
if ((queue->rear + 1) % queue->maxSize == queue->front) {
return 0; // 队列已满
}
queue->data[queue->rear] = element;
queue->rear = (queue->rear + 1) % queue->maxSize;
return 1; // 入队成功
}9.出队
// 出队
Status deCircularQueue(CircularQueue *queue, ElemType *element) {
if (isEmptyCircularQueue(queue)) {
return 0; // 队列为空
}
*element = queue->data[queue->front];
queue->front = (queue->front + 1) % queue->maxSize;
return 1; // 出队成功
}10.遍历队列
// 遍历循环队列
void traverseCircularQueue(CircularQueue *queue) {
for (int i = queue->front; i != queue->rear; i = (i + 1) % queue->maxSize) {
printf("%d ", queue->data[i]);
}
printf("\n");
}11.完整代码
int main(int argc, const char *argv[]) {
CircularQueue queue;
int maxSize = 10; // 循环队列的最大容量
initCircularQueue(&queue, maxSize); // 初始化循环队列
// 测试入队
for (int i = 1; i <= 5; ++i) {
enCircularQueue(&queue, i * 10);
}
// 输出队列元素
printf("队列元素：");
traverseCircularQueue(&queue);
// 获取队首元素
ElemType frontElement;
if (getCircularQueueFront(&queue, &frontElement)) {
printf("队首元素：%d\n", frontElement);
}
// 测试出队
ElemType element;
for (int i = 0; i < 3; ++i) {
if (deCircularQueue(&queue, &element)) {
printf("出队元素：%d\n", element);
}
}
// 输出队列元素
printf("队列元素：");
traverseCircularQueue(&queue);
// 判断队列是否为空
if (isEmptyCircularQueue(&queue)) {
printf("队列为空\n");
} else {
printf("队列不为空\n");
}
// 获取队列长度
printf("队列长度：%d\n", circularQueueLength(&queue));
// 清空队列
clearCircularQueue(&queue);
// 判断队列是否为空
if (isEmptyCircularQueue(&queue)) {
printf("清空队列后，队列为空\n");
} else {
printf("清空队列后，队列不为空\n");
}
// 销毁队列
destroyCircularQueue(&queue);
return 0;
}