点击上方蓝色字体，选择“置顶或者星标”
优质文章第一时间送达！
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
一个队列为z=(a1,a2,...,an), 如图
那么a1为对头元素，an为队尾元素。最早进入队列的元素也会最早出来，只有当最先进入队列的元素都出来以后，后进入的元素才能退出。 在日常生活中，人们去银行办理业务需要排队，这就类似我们提到的队列。每一个新来办理业务的需要按照机器自动生成的编号等待办理，只有前面的人办理完毕，才能轮到排在后面的人办理业务。新来的人进入排队状态就相当于入队，前面办理完业务离开的就相当于出队。队列有两种存储表示：顺序存储和链式存储。采用顺序存储结构的队列被称为顺序队列，采用链式存储结构的队列称为链式队列。 基本运算 InitQueue（） ——初始化队列 EnQueue（） ——进队列 DeQueue（） ——出队列 IsQueueEmpty（） ——判断队列是否为空 IsQueueFull（） ——判断队列是否已满 顺序队列 由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素。 队列为空时，队头指针front和队尾指针rear都指向下标为0的存储单元，当元素a,b,c,d,e,f,g依次进入队列后，元素a~g分别存放在数组下标为0~6的存储单元中，队头指针front指向元素a，队尾指针指rear向元素g的下一位置。如图所示。
假溢出 在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径———采用循环队列。 例如在图中队列删除a和b，然后依次插入h、i和j，当插入j后，就会出现队尾指针rear越出数组的下界造成“假溢出”，如图
顺序循环队列 为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。即：循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。 队空和队满 在循环队列中，队空和队满时队头front和队尾指针rear同时都会指向同一存储单元，即front==rear，如图所示。
队空
队满 如何区分队空和队满呢？有以下两种方法： （1）增加一个标志位。设标志位为tag,初始时，tag=0;当入队成功，则tag=1；出队成功，tag=0。则判断队空的条件为：front==rear&&tag==0;队满的条件为：front==rear&&tag==1; （2）少用一个存储单元。队空的判断条件为front==rear；队满的判断条件为front==(rear 1）%QueueSize。队满的状态如图。
存储结构 #define MAXQSIZE 5 // 存储空间的初始分配量 typedef struct { ElemType *base; int front; int rear; int maxSize; } SqQueue; 基本运算 初始化 Status InitQueue(SqQueue &Q) { //分配存储空间 Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType)); if(!Q.base) exit(OVERFLOW); //置Q为空队列 Q.front = Q.rear = 0; Q.maxSize = MAXQSIZE; return OK; } 判队列是否为空 Status QueueEmpty(SqQueue Q) { if(Q.rear == Q.front) return TRUE; else return FALSE; } 入队函数 Status EnQueue(SqQueue &Q, ElemType e) { if((Q.rear 1) % MAXQSIZE == Q.front)//队列已满 return ERROR; Q.base[Q.rear] = e;//插入队尾 Q.rear = (Q.rear 1) % MAXQSIZE;//尾部指针后移，如果到最后则转到头部 return OK; } 出队函数 Status DeQueue(SqQueue &Q, ElemType &e) { if(Q.front == Q.rear) //队列空 return ERROR; //返回队头元素 e = Q.base[Q.front]; //队头指针后移，如到最后转到头部 Q.front = (Q.front 1) % MAXQSIZE; return OK; } 输出循环队列函数 void OutQueue(SqQueue Q) { ElemType e; if(QueueEmpty(Q)){ printf("这是一个空队列！"); } else { while(!QueueEmpty(Q)){ DeQueue(Q, e); printf("m", e); } printf("n"); } } 输出循环队列长度 Status QueueLength(SqQueue Q) { return (Q.rear - Q.front MAXQSIZE) % MAXQSIZE; } 销毁队列 Status ClearQueue(SqQueue Q) { ///销毁队列Q，Q不再存在 if(Q.base) free(Q.base); Q.base = NULL; Q.front = Q.rear = 0; return OK; } 主函数 int main() { SqQueue q; int cord; ElemType a; printf("第一次使用必须初始化！n"); //调用初始化算法 InitQueue(q); do{ printf("n 主菜单 n"); printf(" 1 初始化循环队列 "); printf(" 2 进队一个元素 "); printf(" 3 出队一个元素 "); printf(" 4 队列长度 "); printf(" 5 销毁队列 "); printf(" 6 结束程序运行 "); printf("n------------------------------------------------------------------n"); printf("请输入您的选择( 1, 2, 3, 4, 5, 6)"); scanf("%d", &cord); printf("n"); switch(cord) { case 1: InitQueue(q); //调用初始化算法; OutQueue(q); break; case 2: printf("请输入要插入的数据元素：a="); scanf("%d", &a); EnQueue (q, a); //调用进队算法; printf("%d 进队之后的队列：",a); OutQueue(q); break; case 3: DeQueue (q, a); //调用出队算法; printf("队头元素 %d 出队之后的队列：", a); OutQueue(q); break; case 4: printf("该队列长度为: %d", QueueLength(q)); break; case 5: ClearQueue(q); break; case 6: exit(0); } } while(cord <= 4); return 0; } 更多推荐内容 ↓↓↓ 图解 Java 垃圾回收机制 Linux 运维必备的 40 个命令总结，收好了~ 系统架构性能优化思路 如果你喜欢本文 请长按二维码，关注公众号
转发朋友圈，是对我最大的支持哟 以上，便是今天的分享，希望大家喜欢，觉得内容不错的，欢迎「分享」「赞」或者点击「在看」支持，谢谢各位。 ❤️爱心三连击
