网站优化报表,龙岗做网站公司,义乌设计工作室,wordpress 4.6.10以下是关于 C 语言中队列的详细知识#xff0c;包括队列的生成、相关函数使用以及其他重要概念#xff1a;
一、队列的概念
队列是一种线性数据结构#xff0c;它遵循先进先出#xff08;First In First Out#xff0c;FIFO#xff09;的原则#xff0c;就像日常生活中…以下是关于 C 语言中队列的详细知识包括队列的生成、相关函数使用以及其他重要概念
一、队列的概念
队列是一种线性数据结构它遵循先进先出First In First OutFIFO的原则就像日常生活中的排队一样先进入队列的元素先被取出。队列有两个端点一端是队头front用于删除元素另一端是队尾rear用于插入元素。
二、队列的顺序存储结构实现数组实现
结构体定义
#define MAX_SIZE 100 // 定义队列的最大容量可根据实际需求调整typedef struct {int data[MAX_SIZE]; // 存放队列元素的数组int front; // 队头指针int rear; // 队尾指针
} Queue;队列的初始化
// 初始化队列
void initQueue(Queue *q) {q-front 0;q-rear 0;
}判断队列是否为空
// 判断队列是否为空
int isEmpty(Queue *q) {return q-front q-rear;
}判断队列是否已满针对顺序存储的循环队列情况
// 判断队列是否已满循环队列
int isFull(Queue *q) {return (q-rear 1) % MAX_SIZE q-front;
}入队操作向队尾插入元素
// 入队操作
void enqueue(Queue *q, int element) {if (isFull(q)) {printf(队列已满无法入队\n);return;}q-data[q-rear] element;q-rear (q-rear 1) % MAX_SIZE;
}出队操作从队头删除元素
// 出队操作
int dequeue(Queue *q) {if (isEmpty(q)) {printf(队列为空无法出队\n);return -1; // 可以根据实际情况返回合适的错误标识}int element q-data[q-front];q-front (q-front 1) % MAX_SIZE;return element;
}三、队列的链式存储结构实现链表实现 节点结构体定义
typedef struct QNode {int data;struct QNode *next;
} QNode;队列结构体定义包含队头和队尾指针
typedef struct {QNode *front;QNode *rear;
} LinkQueue;队列的初始化
// 初始化链式队列
void initLinkQueue(LinkQueue *q) {q-front q-rear (QNode *)malloc(sizeof(QNode));if (!q-front) {printf(内存分配失败\n);exit(1);}q-front-next NULL;
}判断链式队列是否为空
// 判断链式队列是否为空
int isEmptyLinkQueue(LinkQueue *q) {return q-front q-rear;
}入队操作向链式队列的队尾插入节点
// 链式队列入队操作
void enqueueLinkQueue(LinkQueue *q, int element) {QNode *newNode (QNode *)malloc(sizeof(QNode));if (!newNode) {printf(内存分配失败\n);exit(1);}newNode-data element;newNode-next NULL;q-rear-next newNode;q-rear newNode;
}出队操作从链式队列的队头删除节点
// 链式队列出队操作
int dequeueLinkQueue(LinkQueue *q) {if (isEmptyLinkQueue(q)) {printf(队列为空无法出队\n);return -1; // 同样可按需返回错误标识}QNode *temp q-front-next;int element temp-data;q-front-next temp-next;if (q-rear temp) { // 如果删除的是最后一个节点要更新队尾指针q-rear q-front;}free(temp);return element;
}四、队列的应用场景 广度优先搜索BFS在图的遍历算法中比如在迷宫求解、寻找最短路径等场景下利用队列来存储待访问的节点按照层次依次访问节点。操作系统中的任务调度可以将等待执行的进程等任务放入队列中按照先来先服务等调度策略依次执行。消息队列在多线程、多进程通信或者分布式系统中用于暂存消息实现异步通信保证消息按照发送顺序依次被处理。
五、队列操作的时间复杂度分析 入队操作 对于顺序存储的队列循环队列情况入队操作平均时间复杂度是0(1)只是对队尾指针进行简单的更新和赋值操作在不考虑已满的判断情况下已满判断通常也是常数时间复杂度的操作。对于链式存储的队列入队操作也是0(1)主要涉及到创建新节点、调整指针等常数时间内可完成的操作。 出队操作 顺序存储的队列出队操作同样平均时间复杂度为0(1)对队头指针进行更新和获取元素操作不考虑队列为空的判断情况。链式存储的队列出队操作也是0(1)主要是调整指针和释放节点内存等操作时间消耗不随队列元素个数线性增长。
