c语言中的循环队列介绍（CC数据结构）

前言

上一章节针对于C语言栈结构做了解析，不清楚的可以回顾一下。

本章节主要针对于C语言的基础数据结构队列做以解析。

数据结构之队列

队列是一种特殊的 线性表 ，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队友。

故队列基本操作如下：

（1）创建队列

（2）入队

（3）出队

（4）判断队列是否为NULL

（5）获取队头元素

数据结构之队列分类

根据队列实现方式与出队方式，我们可以把栈分为以下三种描述方式：

（1）原生数组队列

（2）动态申请内存的数组描述(普通队列和循环队列）

（3）链式结构描述

优先队列

原生数组描述队列

数组描述栈，只不过多了先进先出的限制而已，它是静态分配的，即使用前，它的内存就已经以数组的形式分配好了，所以在使用时，需要注意队头队尾的标记。

原生数组描述队列实现试题案例:逆序整数

动态数组描述队列

动态申请内存的数组描述不再采用上述实用性的方法了，而是通过封装相关队列函数去描述这种结构。这是写数据结构的一种大致方法。

1.结构体定义与队列的创建过程：

结构体定义:描述队列的属性：队头标记，队尾标记，队列空间

创建队列其实就是创建结构体变量

具体代码

ps:队头和队尾顶标记初始值一般都是-1 ，为了满足队列标记和数组下标一致

2.入队操作

注意: 我们的实现是将最新的元素放在了数组的末尾, 那么数组末尾的元素就是我们的队列队尾元素，故可以使用队尾标记去计算队列中的元素个数。然后每次入队后，队尾标记往后移动。

具体实现代码：

3.出队操作和获取队头元素

注意: 出队操作应该是将队头元素删除,由于数组实现的队列无法删除，故只能把队头标记往队尾移动，简称为一种"伪删除"。

具体实现代码：

4.判断栈是否为空

用户判断栈中是否有元素，通过队尾和队头标记去做即可

具体实现代码：

动态申请内存的数组描述队列测试代码

ps:循环队列是通过区域形成的循环，这里不过多介绍，有兴趣的可以看看相关资料。

链式队列

链式队列： 链表的尾插法即可

具体实现源码线上

#include <stdio.h> #include <stdlib.h> typedef struct { int data; struct Node* next; }NODE,*LPNODE; LPNODE createNode(int data) { LPNODE newNode = (LPNODE)malloc(sizeof(NODE)); newNode->data = data; newNode->next = NULL; return newNode; } typedef struct { int queueSize; LPNODE frontNode; LPNODE tailNode; }QUEUE,*LPQUEUE; LPQUEUE createQueue() { LPQUEUE queue = (LPQUEUE)malloc(sizeof(QUEUE)); queue->queueSize = 0; queue->frontNode = NULL; queue->tailNode = NULL; return queue; } void push(LPQUEUE queue, int data) { //无头表头链表的在封装法 LPNODE newNode = createNode(data); if (queue->queueSize == 0) { queue->frontNode = newNode; queue->tailNode = newNode; } else { //无表头链表的表尾插入 queue->tailNode->next = newNode; queue->tailNode = newNode; } queue->queueSize ; } //FILO FIFO void pop(LPQUEUE queue) { if (queue->queueSize != 0) { LPNODE nextNode = queue->frontNode->next; free(queue->frontNode); queue->frontNode = nextNode; queue->queueSize--; } } int front(LPQUEUE queue) { return queue->frontNode->data; } int empty(LPQUEUE queue) { return queue->queueSize==0; } int size(LPQUEUE queue) { return queue->queueSize; } int main() { LPQUEUE queue = createQueue(); for (int i = 1; i <= 3; i ) { push(queue, i); } while (!empty(queue)) { printf("%d\t", front(queue)); pop(queue); } printf("\n"); system("pause"); return 0; }

优先队列:根据优先权去决定你出队的元素，故数据中存在优先权衡量的值，相关实现代码如下：

#include <iostream> #define MaxQueueSize 100 //队列的大小 //数据类型 数据本身 优先权 typedef int ElementType; //定义数据类型地 别名 //数据 结构体 typedef struct { int priority; //优先权---工作量 ElementType element;//队列中的元素 }DataType; //队列的结构体 typedef struct { int size; //结构体的嵌套 DataType Queue[MaxQueueSize]; }PriQueue; //读取文件作业---调度读取 //队列操作 //初始化---初始化基本成员 //size Queue void InitQueue(PriQueue *Q) { Q->size = 0; } //判断队列是否为空 NULL //和它的初始化比较 int QueueEmpty(PriQueue *Q) { // -> 指向运算符 C：结构体指针 C ： 类和结构体 // :: 作用域限定符 if (Q->size <= 0) return 0; //标志 else return 1; //不为空 // return 0 函数结束 } //入队 文件操作 int Push(PriQueue *Q, DataType data) { //入队前判断是否满 if (Q->size >= MaxQueueSize) { std::cout << "杯子已满，无法再倒水" << std::endl; return 0; } else { //Q->size=0; Q->Queue[Q->size] = data; //入队了队列长度就要增长 Q->size ; return 1; } } //出队 int Pop(PriQueue *Q, DataType *A) { DataType min; //最小的开始，排序 int minIndex = 0; //短作业优先法 //喝水，先判断杯子有没有水 if (Q->size <= 0) { std::cout << "为空，无法出队" << std::endl; return 0; } else { //假设第一个作业是最短的 min = Q->Queue[0]; //1 for (int i = 1; i < Q->size; i ) { //多了一个数据项 按照权值排序 //0 if (Q->Queue[i].priority < min.priority) { min = Q->Queue[i]; minIndex = i; //出队依据就是最小作业序号 } } *A = Q->Queue[minIndex]; //难点 //删除完数组后，后面的元素往前移动 for (int i = minIndex 1; i < Q->size; i ) { Q->Queue[i - 1] = Q->Queue[i]; minIndex = i; } Q->size--; return 1; } } //获取队头元素 int GetQueue(PriQueue *Q, DataType *A) { DataType min; //最小的开始，排序 int minIndex = 0; //短作业优先法 //喝水，先判断杯子有没有水 if (Q->size <= 0) { std::cout << "为空，无法出队" << std::endl; return 0; } else { //假设第一个作业是最短的 min = Q->Queue[0]; //1 for (int i = 1; i < Q->size; i ) { //多了一个数据项 按照权值排序 //0 if (Q->Queue[i].priority < min.priority) { min = Q->Queue[i]; minIndex = i; //出队依据就是最小作业序号 } } *A = Q->Queue[minIndex]; return 1; } }

希望对大家有帮助！

另外如果你想更好的提升你的编程能力，学好C语言C 编程！弯道超车，快人一步！

编程学习软件分享：

编程学习视频分享：

分享（源码、项目实战视频、项目笔记，基础入门教程）

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！

C语言C 编程学习交流圈子，点击下方【了解更多】获取更多学习资料哦~

,