1 循环队列FIFO介绍
循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。
入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针。
1.1 循环队列结构
1
2
3
4
5
| #define FIFO_HEAD(name, type) \
struct name { \
struct type *fifo; \
int front, tail, capacity; \
}
|
1
2
3
4
| front表示首元素索引
tail表示最后一个元素索引
capacity表示队列的长度
struct type fifo表示该队列中的元素指针，可以指向任意结构体指针
|
举个例子：
1
2
3
4
5
6
7
8
9
10
11
| struct person{
int age;
int id;
char name[20];
};
FIFO_HEAD(person_q, person*);
struct person_q { \
struct person* *fifo; \
int front, tail, capacity; \
}
|
1.2 FIFO初始化
分配一个连续的空间存储队列元素。用户自定义队列容量。
1
2
3
4
5
| #define FIFO_INIT(head, _capacity) do { \
(head)->fifo = malloc(sizeof(*(head)->fifo) * _capacity); \
(head)->front = (head)->tail = -1; \
(head)->capacity = _capacity; \
} while (0)
|
1.3 FIFO销毁
1
2
3
4
5
6
| #define FIFO_EXIT(head) do { \
(head)->front = (head)->tail = -1; \
(head)->capacity = 0; \
if ((head)->fifo) \
free((head)->fifo); \
} while (0)
|
1.4 入队列
入队列就是尾元素的索引++，也就是tail++，让新元素放进队列的尾部。
1
2
3
4
5
6
7
8
| #define FIFO_PUSH(head, elm) do { \
if (FIFO_EMPTY(head)) \
(head)->front = (head)->tail = 0; \
else \
(head)->tail = ((head)->tail == (head)->capacity - 1) \
? 0 : (head)->tail + 1; \
(head)->fifo[(head)->tail] = elm; \
} while (0)
|
如果队列是空的，则第一个元素入队列，front和tail索引都指向第一个元素，front = tail = 0;
其他情况入队，让tail++
1.5 出队列
出队列就是让font对应的元素丢出去，font++。
1
2
3
4
5
6
7
8
| #define FIFO_POP(head, pelm) do { \
*(pelm) = (head)->fifo[(head)->front]; \
if ((head)->front == (head)->tail) \
(head)->front = (head)->tail = -1; \
else \
(head)->front = ((head)->front == (head)->capacity - 1)\
? 0 : (head)->front + 1; \
} while (0)
|
当front追上tail后，表示队列空了，重新设置起始点，需要将front = tail = -1 。
其他情况出队，丢出front元素，让front++
1.6 FIFO判空
1
| #define FIFO_EMPTY(head) ((head)->front == -1)
|
①队列初始化时，队列是空的，会让front为-1
②出队列时，font++, 当font追上tail表示空了，则可以重新设置起始点，令front = tail = -1
综合①②所以可以用-1判断
1.6 FIFO判满
1
| #define FIFO_FULL(head) (((head)->front == ((head)->tail + 1)%(head)->capacity))
|
①当front=0时，那么tail到达capacity-1表示FIFO full。
②否则，tail追上front后(front = tail + 1)表示FIFO full。
1.7 FIFO容量
1
| #define FIFO_CAPACITY(head) ((head)->capacity)
|
1.8 FIFO中有效元素个数
1
2
| #define FIFO_SIZE(head) (FIFO_EMPTY(head) ? \
0 : ((((head)->tail + (head)->capacity - (head)->front) % (head)->capacity) + 1))
|
用tail - front就表示有效元素个数，不过由于循环FIFO,可能tail<front,这个时候就需要取余运算，如下图:
1.9 FIFO遍历
1
2
3
4
| #define FIFO_FOREACH(var, head, idx) \
for (idx = (head)->front, var = (head)->fifo[idx]; \
idx < (head)->front + FIFO_SIZE(head); \
var = (head)->fifo[++idx % (head)->capacity])
|
1.10 队列元素获取
1.10.1 第一个元素
1
| #define FIFO_GET_FRONT(head, pelm) (*(pelm) = (head)->fifo[(head)->front])
|
1.10.2 最后一个元素
1
| #define FIFO_GET_TAIL(head, pelm) (*(pelm) = (head)->fifo[(head)->tail])
|
2 测试用例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
| #include "fifo.h"
#include <stdio.h>
struct person{
int age;
int id;
char name[20];
};
FIFO_HEAD(person_q, person*);
struct person_q person1_queue;
struct person_q person2_queue;
int main(void){
FIFO_INIT(&person1_queue, 1);
FIFO_INIT(&person2_queue, 5);
if (FIFO_CAPACITY(&person1_queue) != 1) {
printf( "FIFO_CAPACITY 1 NG.\n");
return -1;
}
if (FIFO_CAPACITY(&person2_queue) != 5) {
printf( "FIFO_CAPACITY 2 NG.\n");
return -1;
}
if (FIFO_SIZE(&person1_queue) != 0) {
printf( "FIFO_SIZE 1 NG.\n");
return -1;
}
if (FIFO_SIZE(&person2_queue) != 0) {
printf( "FIFO_SIZE 2 NG.\n");
return -1;
}
if (!FIFO_EMPTY(&person1_queue)) {
printf( "FIFO_EMPTY 1 NG.\n");
return -1;
}
if (!FIFO_EMPTY(&person2_queue)) {
printf( "FIFO_EMPTY 2 NG.\n");
return -1;
}
struct person *person_a = malloc(sizeof(*person_a));
person_a->age = 20;
person_a->id = 1001;
FIFO_PUSH(&person1_queue, person_a);
if (!FIFO_FULL(&person1_queue)) {
printf( "FIFO_FULL 1 NG.\n");
return -1;
}
person_a = malloc(sizeof(*person_a));
person_a->age = 30;
person_a->id = 1002;
FIFO_PUSH(&person2_queue, person_a);
if (FIFO_FULL(&person2_queue)) {
printf( "FIFO_FULL 2 NG.\n");
return -1;
}
if (FIFO_SIZE(&person1_queue) != 1) {
printf( "FIFO_SIZE 3 NG.\n");
return -1;
}
if (FIFO_SIZE(&person2_queue) != 1) {
printf( "FIFO_SIZE 4 NG.\n");
return -1;
}
FIFO_POP(&person1_queue, &person_a);
if (person_a->age != 20) {
printf( "FIFO_POP content NG.\n");
return -1;
}
free(person_a);
if (FIFO_SIZE(&person1_queue) != 0) {
printf( "FIFO_SIZE 5 NG.\n");
return -1;
}
person_a = malloc(sizeof(*person_a));
person_a->age = 40;
person_a->id = 1003;
FIFO_PUSH(&person2_queue, person_a);
FIFO_GET_FRONT(&person2_queue, &person_a);
if (person_a->age != 30) {
printf( "FIFO_GET_FRONT NG.\n");
return -1;
}
FIFO_GET_TAIL(&person2_queue, &person_a);
if (person_a->age != 40) {
printf( "FIFO_GET_TAIL NG.\n");
return -1;
}
FIFO_POP(&person2_queue, &person_a);
if (person_a->age != 30) {
printf( "FIFO_POP content NG.\n");
return -1;
}
free(person_a);
if (FIFO_SIZE(&person2_queue) != 1) {
printf( "FIFO_SIZE 6 NG.\n");
return -1;
}
FIFO_POP(&person2_queue, &person_a);
if (person_a->age != 40) {
printf( "FIFO_POP content NG.\n");
return -1;
}
free(person_a);
if (FIFO_SIZE(&person2_queue) != 0) {
printf( "FIFO_SIZE 7 NG.\n");
return -1;
}
struct person *person_arr[5];
int i=0;
while (!FIFO_FULL(&person2_queue)) {
person_arr[i] = malloc(sizeof(*person_arr[0]));
person_arr[i]->age = i;
person_arr[i]->id = 1000 + i;
FIFO_PUSH(&person2_queue, person_arr[i]);
i++;
}
while (!FIFO_EMPTY(&person2_queue) {
FIFO_POP(&person2_queue, &person_a);
printf( "age:%d, id:%d.\n", person_a->age, person_a->id);
free(person_a);
}
FIFO_EXIT(&person1_queue);
FIFO_EXIT(&person2_queue);
return 0;
}
|
结果如下：
