线性结构常见应用之队列[基于郝斌课程]
定义：一种可以实现“先进先出”的存储结构
队列类似于排队买票
分类：
链式队列：基于列表
静态队列：基于数组
静态队列通常都必须是循环队列
静态队列为什么是循环队列？
减少对内存的浪费
用传统数组来实现队列的话，参数只能加不能减
循环队列需要几个参数来确定以及各个参数的含义
需要两个参数来确定：front 和 rear
两个参数不同场合有不同的含义
队列初始化： front 和 rear 都是0
队列非空：front 代表的是队列的第一个元素， rear 代表的是队列的最后一个有效元素的下一个元素
队列空：front 和 rear 是相等的，但是不一致是0
循环队列的入队伪算法
rear = (rear + 1) % 数组的长度
循环队列的出队伪算法
front = (front + 1) % 数组的长度
如何判断循环队列是否为空？
如果 front == rear，则队列为空
如何判断循环队列是否已满？
front 和 rear 大小没有规律，可以 front 比 rear 大，也可以是 front 比 rear 小
规定放入的元素比数组长度少1，只要 rear 和 front 相邻，则满了
如果 ((rear + 1) % 数组长度) == front，则队列满了
队列的应用：
所有和时间有关的操作都与队列有关
/*
@file main.c
@brief 线性结构常见应用之队列
@author EricsT (EricsT@163.com)
@version v1.0.0
@date 2025-09-24
@history 2025-09-24 EricsT - 新建文件
*/
#include <stdio.h>
#include <malloc.h>
#define LEN 6
typedef struct QUEUE
{
int* pBase;
int front;
int rear;
}Queue, *PtrQueue;
void InitQueue(PtrQueue ptrQueue);//初始化
bool InQueue(PtrQueue ptrQueue, int inValue);//入队
bool OutQueue(PtrQueue ptrQueue);//出队
bool isEmptyQueue(const PtrQueue ptrQueue);//判断是否为空
bool isFullQueue(const PtrQueue ptrQueue);//判断是否满了
void TraverseQueue(const PtrQueue ptrQueue);//遍历
int main(void)
{
Queue queue;
InitQueue(&queue);
if (isEmptyQueue(&queue))
printf("队列为空\n");
else
printf("队列不空\n");
int inVaule;
printf("请输入要入队的值：");
scanf("%d", &inVaule);
InQueue(&queue, inVaule);
printf("请输入要入队的值：");
scanf("%d", &inVaule);
InQueue(&queue, inVaule);
printf("请输入要入队的值：");
scanf("%d", &inVaule);
InQueue(&queue, inVaule);
printf("请输入要入队的值：");
scanf("%d", &inVaule);
InQueue(&queue, inVaule);
printf("请输入要入队的值：");
scanf("%d", &inVaule);
InQueue(&queue, inVaule);
printf("请输入要入队的值：");
scanf("%d", &inVaule);
InQueue(&queue, inVaule);
printf("请输入要入队的值：");
scanf("%d", &inVaule);
InQueue(&queue, inVaule);
if (isEmptyQueue(&queue))
printf("队列为空\n");
else
printf("队列不空\n");
if (isFullQueue(&queue))
printf("队列已满\n");
else
printf("队列未满\n");
TraverseQueue(&queue);
OutQueue(&queue);
TraverseQueue(&queue);
return 0;
}
void InitQueue(PtrQueue ptrQueue)
{
ptrQueue->pBase = (int*)malloc(sizeof(int) * LEN);
ptrQueue->front = 0;
ptrQueue->rear = 0;
}
bool InQueue(PtrQueue ptrQueue, int inValue)
{
if (isFullQueue(ptrQueue))
return false;
ptrQueue->pBase = inValue;
ptrQueue->rear = (ptrQueue->rear + 1) % LEN;//从后面加入
return true;
}
bool OutQueue(PtrQueue ptrQueue)
{
if (isEmptyQueue(ptrQueue))
return false;
ptrQueue->front = (ptrQueue->front + 1) % LEN;//先进先出//从前面出去
return true;
}
bool isEmptyQueue(const PtrQueue ptrQueue)
{
if (ptrQueue->front == ptrQueue->rear)
return true;
return false;
}
bool isFullQueue(const PtrQueue ptrQueue)
{
if (ptrQueue->front == ((ptrQueue->rear + 1) % LEN))
return true;
return false;
}
void TraverseQueue(const PtrQueue ptrQueue)
{
int i = ptrQueue->front;
while (ptrQueue->rear != i)
{
printf("%d ", ptrQueue->pBase);
i = (i + 1) % LEN;
}
printf("\n");
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]