《2022年数据结构：循环队列文件 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构：循环队列文件 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构：循环队列（C 语言实现）生活中有很多队列的影子，比如打饭排队，买火车票排队问题等，可以说与时间相关的问题，一般都会涉及到队列问题；从生活中，可以抽象出队列的概念，队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列；静态队列一般用数组来实现，但此时的队列必须是循环队列，否则会造成巨大的内存浪费；链式队列是用链表来实现队列的。这里讲的是循环队列，首先我们必须明白下面几个问题一、循环队列的基础知识1.循环队列需要几个参数来确定循环队列需要2 个参数，front 和 rear2.循环队列各个参数的含义（1）队列初始化时，front 和 rear 值都为零；（2）当队列不为
2、空时，front 指向队列的第一个元素，rear 指向队列最后一个元素的下一个位置；（3）当队列为空时，front 与 rear 的值相等，但不一定为零；3.循环队列入队的伪算法（1）把值存在 rear 所在的位置；（2）rear=（rear+1）%maxsize，其中 maxsize 代表数组的长度；程序代码：cppview plaincopy1.bool Enqueue(PQUEUE Q,int val)2.3.if(FullQueue(Q)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -4.returnfalse;5.else6.7.Q-pBaseQ-rear=v
3、al;8.Q-rear=(Q-rear+1)%Q-maxsize;9.returntrue;10.11.4.循环队列出队的伪算法（1）先保存出队的值；（2）front=（front+1）%maxsize，其中 maxsize 代表数组的长度；程序代码：cppview plaincopy1.bool Dequeue(PQUEUE Q,int *val)2.3.if(EmptyQueue(Q)4.5.returnfalse;6.7.else8.9.*val=Q-pBaseQ-front;10.Q-front=(Q-front+1)%Q-maxsize;11.returntrue;12.13.5.如
4、何判断循环队列是否为空if（front=rear）队列空；else名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -队列不空；cppview plaincopy1.bool EmptyQueue(PQUEUE Q)2.3.if(Q-front=Q-rear)/判断是否为空4.returntrue;5.else6.returnfalse;7.6.如何判断循环队列是否为满这个问题比较复杂，假设数组的存数空间为7，此时已经存放 1，a，5,7,22,90 六个元素了，如果在往数组中添加一个元素，则rear=front；名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共
5、 6 页 -此时，队列满与队列空的判断条件front=rear 相同，这样的话我们就不能判断队列到底是空还是满了；解决这个问题有两个办法：一是增加一个参数，用来记录数组中当前元素的个数；第二个办法是，少用一个存储空间，也就是数组的最后一个存数空间不用，当（rear+1）%maxsiz=front时，队列满；cppview plaincopy1.bool FullQueue(PQUEUE Q)2.3.if(Q-front=(Q-rear+1)%Q-maxsize)/判断循环链表是否满，留一个预留空间不用4.returntrue;5.else6.returnfalse;7.附录：queue.h 文
6、件代码：cppview plaincopy1.#ifndef _QUEUE_H_2.#define _QUEUE_H_3.typedefstruct queue 4.5.int *pBase;6.int front;/指向队列第一个元素7.int rear;/指向队列最后一个元素的下一个元素8.int maxsize;/循环队列的最大存储空间9.QUEUE,*PQUEUE;10.11.void CreateQueue(PQUEUE Q,int maxsize);12.void TraverseQueue(PQUEUE Q);13.bool FullQueue(PQUEUE Q);14.bool
7、 EmptyQueue(PQUEUE Q);15.bool Enqueue(PQUEUE Q,int val);16.bool Dequeue(PQUEUE Q,int *val);17.#endif名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -queue.c 文件代码：cppview plaincopy1.#include2.#include3.#includemalloc.h4.#includequeue.h5./*6.Function:Create a empty stack;7.*/8.void CreateQueue(PQUEUE Q,int maxsize
8、)9.10.Q-pBase=(int *)malloc(sizeof(int)*maxsize);11.if(NULL=Q-pBase)12.13.printf(Memory allocation failure);14.exit(-1);/退出程序15.16.Q-front=0;/初始化参数17.Q-rear=0;18.Q-maxsize=maxsize;19.20./*21.Function:Print the stack element;22.*/23.void TraverseQueue(PQUEUE Q)24.25.int i=Q-front;26.printf(队中的元素是:n);
9、27.while(i%Q-maxsize!=Q-rear)28.29.printf(%d ,Q-pBasei);30.i+;31.32.printf(n);33.34.bool FullQueue(PQUEUE Q)35.36.if(Q-front=(Q-rear+1)%Q-maxsize)/判断循环链表是否满，留一个预留空间不用37.returntrue;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -38.else39.returnfalse;40.41.bool EmptyQueue(PQUEUE Q)42.43.if(Q-front=Q-rear)/判断是否为空
10、44.returntrue;45.else46.returnfalse;47.48.bool Enqueue(PQUEUE Q,int val)49.50.if(FullQueue(Q)51.returnfalse;52.else53.54.Q-pBaseQ-rear=val;55.Q-rear=(Q-rear+1)%Q-maxsize;56.returntrue;57.58.59.60.bool Dequeue(PQUEUE Q,int *val)61.62.if(EmptyQueue(Q)63.64.returnfalse;65.66.else67.68.*val=Q-pBaseQ-front;69.Q-front=(Q-front+1)%Q-maxsize;70.returntrue;71.72.名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -