队列的实现 queue

队列是规定一头只进、另一头只出的线性结构。其一般由循环队列实现，这样可以使得存储空间固定且快捷。

因此需要申请一段固定的空间，设定队头front和队尾rear。

入队操作是队头添加一个元素front+1，出队操作是队尾去除一个元素rear+1。

初始条件（空队）：规定front和rear在同一个位置，front == rear。

一般状态：rear位于队尾元素的后一个位置，即下一个新入队元素的位置。

队满状态：(rear+1)%n == front。

[cpp] view plaincopy

1. # include<stdio.h>  
2. # include<string.h>  
3. # include<malloc.h>  
4.    
5. #define N 6  
6. typedef struct Queue  
7. {  
8.     /* data */  
9.     int *pBase;  
10.     int front;  
11.     int rear;  
12. }QUEUE;  
13.   
14. void initQueue(QUEUE *pQueue)  
15. {  
16.     pQueue->pBase = (int *)malloc(sizeof(int)*N);  
17.     pQueue->front = 0;  
18.     pQueue->rear = 0;  
19.     return;  
20. }  
21.   
22. bool isFull(QUEUE *pQueue)  
23. {  
24.     if( (pQueue->rear + 1)%N == pQueue->front )  
25.         return true;  
26.     else  
27.         return false;  
28. }  
29.   
30. bool isEmpty(QUEUE *pQueue)  
31. {  
32.     if(pQueue->front == pQueue->rear)  
33.         return true;  
34.     else  
35.         return false;  
36. }  
37.   
38.   
39. bool enQueue(QUEUE *pQueue, int value)  
40. {  
41.     if(isFull(pQueue))  
42.     {  
43.         printf("QUEUE is Full.\n");  
44.         return false;  
45.     }  
46.     else  
47.     {  
48.         pQueue->pBase[pQueue->rear] = value;  
49.         pQueue->rear = (pQueue->rear+1)%N;  
50.         return true;  
51.     }  
52. }  
53.   
54. bool outQueue(QUEUE *pQueue, int *pvalue)  
55. {  
56.     if(isEmpty(pQueue))  
57.     {  
58.         printf("QUEUE is Empty.\n");  
59.         return false;  
60.     }  
61.     else  
62.     {  
63.         *pvalue = pQueue->pBase[pQueue->front];  
64.         pQueue->front = (pQueue->front+1)%N;  
65.         return true;  
66.     }  
67. }  
68.   
69. void traverseQueue(const QUEUE *pQueue)  
70. {  
71.     int i = pQueue->front;  
72.     printf("The QUEUE: ");  
73.     while(i != pQueue->rear)  
74.     {  
75.         printf("%d ", pQueue->pBase[i]);  
76.         i = (i+1)%N;  
77.     }  
78.     printf("\n");  
79.     return;  
80. }  
81.   
82. int main()  
83. {  
84.     int out;  
85.     QUEUE mq;  
86.     initQueue(&mq); //这里的实参都是用引用类型  
87.     enQueue(&mq, 10);  
88.     enQueue(&mq, 8);  
89.     traverseQueue(&mq);  
90.     outQueue(&mq, &out);  
91.     traverseQueue(&mq);  
92. }  

队列的应用：和先后顺序有关的场景，比如BFS，消息，进程管理。