数据结构与算法学习笔记三---循环队列的表示和实现(C语言)

目录

前言

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