目录
前言
1.为啥要使用循环队列
2.队列的顺序表示和实现
1.定义
2.初始化
3.销毁
4.清空
5.空队列
6.队列长度
7.获取队头
8.入队
9.出队
10.遍历队列
11.完整代码
前言
本篇博客介绍栈和队列的表示和实现。
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;
}