数据结构：循环队列(C语言实现).doc

(完整word)数据结构：循环队列(C语言实现)

数据结构:循环队列（C语言实现）
生活中有很多队列的影子，比如打饭排队，买火车票排队问题等，可以说与时间相关的问题，一般都会涉及到队列问题；从生活中，可以抽象出队列的概念，队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列;静态队列一般用数组来实现，但此时的队列必须是循环队列，否则会造成巨大的内存浪费；链式队列是用链表来实现队列的。这里讲的是循环队列，首先我们必须明白下面几个问题
一、循环队列的基础知识
1。循环队列需要几个参数来确定
循环队列需要2个参数，front和rear
2。循环队列各个参数的含义
（1）队列初始化时，front和rear值都为零;
(2）当队列不为空时，front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置；
（3)当队列为空时，front与rear的值相等，但不一定为零;
3.循环队列入队的伪算法
(1）把值存在rear所在的位置；
（2）rear=（rear+1）%maxsize ，其中maxsize代表数组的长度;
程序代码:
[cpp] view plaincopy
1. bool Enqueue（PQUEUE Q， int val)  
2. ｛  
3.     if(FullQueue（Q)）  
4.         return false；  
5.     else  
6.     {  
7.         Q-〉pBase［Q—〉rear］=val；  
8.         Q—>rear=(Q—〉rear+1)％Q-〉maxsize;  
9.         return true;  
10.     ｝  
11. ｝  

4。循环队列出队的伪算法
（1）先保存出队的值；
（2）front=（front+1)％maxsize ，其中maxsize代表数组的长度；
程序代码：
［cpp] view plaincopy
1. bool Dequeue（PQUEUE Q, int ＊val）  
2. ｛  
3.     if（EmptyQueue（Q)）  
4.     {  
5.         return false；  
6.     ｝  
7.     else  
8.     ｛  
9.         ＊val=Q—>pBase[Q—〉front］;  
10.         Q—>front=(Q-〉front+1）%Q—>maxsize；  
11.         return true；  
12.     ｝  
13. ｝  

5。如何判断循环队列是否为空
if（front==rear）
队列空；
else
  队列不空；
［cpp］ view plaincopy
1. bool EmptyQueue(PQUEUE Q)  
2. {  
3.     if(Q—>front==Q-〉rear)    //判断是否为空  
4.         return true;  
5.     else  
6.         return false;  
7. ｝  

6.如何判断循环队列是否为满

    这个问题比较复杂,假设数组的存数空间为7，此时已经存放1,a，5，7,22，90六个元素了,如果在往数组中添加一个元素,则rear=front;此时，队列满与队列空的判断条件front=rear相同,这样的话我们就不能判断队列到底是空还是满了；
解决这个问题有两个办法:一是增加一个参数，用来记录数组中当前元素的个数;第二个办法是,少用一个存储空间，也就是数组的最后一个存数空间不用，当(rear+1）％maxsiz=front时，队列满；
[cpp］ view plaincopy
1. bool FullQueue(PQUEUE Q）  
2. {  
3.     if（Q-〉front==(Q-〉rear+1）%Q—>maxsize）    //判断循环链表是否满,留一个预留空间不用  
4.         return true；  
5.     else  
6.         return false；  
7. }  

附录：
queue。h文件代码：
［cpp] view plaincopy
1. #ifndef __QUEUE_H_  
2. #define __QUEUE_H_  
3. typedef struct 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 EmptyQueue（PQUEUE Q)；  
15. bool Enqueue（PQUEUE Q, int val);  
16. bool Dequeue（PQUEUE Q, int *val）;  
17. ＃endif  

queue。c文件代码:
[cpp］ view plaincopy
1. ＃include<stdio。h〉  
2. #include<stdlib。h〉  
3. ＃include”malloc.h"  
4. #include"queue.h"  
5. /＊＊＊＊*＊**＊＊*******＊＊＊*******＊＊***＊＊＊*＊＊*******＊* 
6. Function: Create a empty stack; 
7. ＊*＊＊*＊*＊＊＊＊**＊**＊＊**＊＊**＊**＊＊*＊＊***＊＊＊*＊*＊*＊*＊**/  
8. void CreateQueue（PQUEUE Q,int maxsize）  
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"）；  
27.     while（i%Q—>maxsize!=Q—〉rear）  
28.     {  
29.         printf（”%d ”,Q—〉pBase[i］）;  
30.         i++；  
31.     }  
32.     printf("\n”）;  
33. ｝  
34. bool FullQueue（PQUEUE Q）  
35. {  
36.     if(Q—〉front==(Q->rear+1)％Q—〉maxsize)    //判断循环链表是否满，留一个预留空间不用  
37.         return true；  
38.     else  
39.         return false；  
40. ｝  
41. bool EmptyQueue(PQUEUE Q）  
42. {  
43.     if（Q-〉front==Q-〉rear）    //判断是否为空  
44.         return true;  
45.     else  
46.         return false;  
47. ｝  
48. bool Enqueue(PQUEUE Q， int val)  
49. ｛  
50.     if(FullQueue（Q））  
51.         return false；  
52.     else  
53.     {  
54.         Q—〉pBase[Q—>rear]=val;  
55.         Q—〉rear=（Q->rear+1）%Q-〉maxsize;  
56.         return true;  
57.     ｝  
58. }  
59.   
60. bool Dequeue(PQUEUE Q， int *val)  
61. {  
62.     if(EmptyQueue(Q））  
63.     ｛  
64.         return false;  
65.     }  
66.     else  
67.     ｛  
68.         *val=Q—>pBase［Q—〉front];  
69.         Q-〉front=（Q—>front+1）％Q-〉maxsize;  
70.         return true;  
71.     }  
72. }