1 循环队列FIFO介绍

1.1 循环队列结构

1.2 FIFO初始化

1.3 FIFO销毁

1.4 入队列

1.5 出队列

1.6 FIFO判空

1.6 FIFO判满

1.7 FIFO容量

1.8 FIFO中有效元素个数

1.9 FIFO遍历

1.10 队列元素获取

1.10.1 第一个元素

1.10.2 最后一个元素

2 测试用例

1 循环队列FIFO介绍#循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针。

1.1 循环队列结构#12345#define FIFO_HEAD(name, type) \ struct name { \ struct type *fifo; \ int front, tail, capacity; \ }

1234front表示首元素索引tail表示最后一个元素索引capacity表示队列的长度struct type fifo表示该队列中的元素指针，可以指向任意结构体指针

举个例子：

1234567891011struct 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初始化#分配一个连续的空间存储队列元素。用户自定义队列容量。

12345#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销毁#123456#define FIFO_EXIT(head) do { \ (head)->front = (head)->tail = -1; \ (head)->capacity = 0; \ if ((head)->fifo) \ free((head)->fifo); \} while (0)

1.4 入队列#入队列就是尾元素的索引++，也就是tail++，让新元素放进队列的尾部。

12345678#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++。

12345678#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中有效元素个数#12#define FIFO_SIZE(head) (FIFO_EMPTY(head) ? \ 0 : ((((head)->tail + (head)->capacity - (head)->front) % (head)->capacity) + 1))

用tail - front就表示有效元素个数，不过由于循环FIFO,可能tail

1.9 FIFO遍历#1234#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 测试用例#123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151#include "fifo.h"#include 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);//把person_a这个结构体指针元素丢进FIFO, //后面对它pop出来又能拿到它，所以不用担心地址弄丢导致无法释放. 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;}

结果如下：