数组队列

使数组中的一个元素始终保留不用，这样当队列“满”时front和rear的值便不相同，可以和队列为空的情况区分开来。通过不允许数组完全填满，问题得以避免。

若数组元素共有ARRAY_SIZE个，则有效利用的只有QUEUE_SIZE = ARRAY_SIZE - 1个。

当满足下列条件时数组队列为空：

　　（rear + 1) % ARRAY_SIZE == front

当满足下列条件时数组队列为“满”：

　　（rear + 2) % ARRAY_SIZE == front

数组队列实现如下：

 queue.h
 1 /*                                                                                                                  
 2  * 一个队列模块的接口
 3  */
 4 #include <stdlib.h>
 5 
 6 typedef QUEUE_TYPE int;
 7 
 8 /*
 9  * create_queue
10  * 创建一个队列，参数指定队列可以存储的元素的最大数量
11  * 注意：这个函数只适用于使用动态分配数组的队列。
12  */
13 void create_queue(size_t size);
14 
15 /*
16  * destroy_queue
17  * 销毁一个队列。注意：这个函数只适用于链式和动态分配数组的队列。
18  */
19 void destroy_queue(void);
20 
21 /*
22  * insert
23  * 向队列添加一个新元素，参数就是需要添加的元素。
24  */
25 void insert(QUEUE_TYPE value);
26 
27 /*
28  * delete
29  * 从对列中移除一个元素并将其丢弃。
30  */
31 void delete(void);
32 
33 /*
34  * first
35  * 返回队列中第一个元素的值，但不修改队列本身。
36  */
37 QUEUE_TYPE first(void);
38 
39 /*
40  * is_empty
41  * 如果队列为空，返回TRUE，否则返回FALSE.
42  */
43 int is_full(void);

queue.c
 1 /*                                                                                                                  
 2  * 一个用静态数组实现的队列，数组的长度只能通过修改#define定义并重新编译模块来调整.
 3  */
 4 #include "queue.h"
 5 #include <stdio.h>
 6 #include <assert.h>
 7 
 8 #define QUEUE_SIZE 100/*队列中元素的最大数量*/
 9 #define ARRAY_SIZE (QUEUE_SIZE + 1)/*数组的长度*/
10 
11 /*
12  * 用于存储队列元素的数组和指向队列头和尾的指针.
13  */
14 static QUEUE_TYPE queue[ARRAY_SIZE];
15 static size_t front = 1;
16 static size_t rear = 0;
17 
18 /*
19  * insert
20  */
21 void insert(QUEUE_TYPE value)
22 {
23     assert(!is_full());
24     rear = (rear + 1) % ARRAY_SIZE;
25     queue[rear] = value;
26 }
27 
28 /*
29  * delete
30  */
31 void delete(void)
32 {
33     assert(!is_empty());
34     front = (front + 1) % ARRAY_SIZE;
35 }
36 
37 /*
38  * first
39  */
40 QUEUE_TYPE first(void)
41 {
42     assert(!is_empty());
43     return queue[front];
44 }
45 
46 /*
47  * is_empty
48  */
49 int is_empty(void)
50 {
51     return (rear + 1) % ARRAY_SIZE == front;
52 }
53 
54 /*
55  * is_full
56  */
57 int is_full(void)
58 {
59     return (rear + 2) % ARRAY_SIZE == front;
60 }