一个60行的C语言FIFO队列的demo

前言

因为需求只需要实现出队和入队操作，不必实现访问操作。只需要实现 Pop 和 Push 就行。

FIFO代码

#include       // printf
#include      // size_t
#include      // malloc

typedef struct _MyList {
    void *_item;        // must be malloced
    struct _MyList *_next;
} MyList;

// 禁止改变容量 capa
typedef struct _MyQueue {
    MyList *_head;       // 头指针
    MyList *_tail;       // 尾指针
    size_t  _size;       // 已用空间
    size_t  _capa;       // 最大容量
} MyQueue;

MyQueue* MyQueueInit(size_t capa) {
    // calloc 会把空间置零, 故指针为 NULL
    MyQueue *queue = (MyQueue *) calloc(4, sizeof(void *));

    queue->_capa = capa;
    return queue;
}

void* MyQueuePopFront(MyQueue *_this) {
    if (_this->_size == 0)
        return NULL;
    
    -- _this->_size;
    MyList *tmp_head = _this->_head;
    void *ret_val = _this->_head->_item;
    _this->_head = _this->_head->_next;
    free(tmp_head);
    return ret_val;
}

// 入队 item, 如果满了，队首元素出队
void* MyQueuePushBack(MyQueue *_this, void *item) {
    // calloc 会把空间置零, 故 new_node->_next == NULL
    MyList *new_node = calloc(2, sizeof(void *));
    if (new_node == NULL) {
        printf("[CRIT WARN]: bad malloc in MyQueuePushBack!\n");
        return NULL;
    }
    new_node->_item = item;

    // 如果 size == 0, 则 head == tail == NULL
    if (_this->_size == 0)
        _this->_head = new_node;
    else
        _this->_tail->_next = new_node;
    
    _this->_tail = new_node;
    ++ _this->_size;

    // 如果满了, 就要出队
    if (_this->_size > _this->_capa)
        return MyQueuePopFront(_this);
    else
        return NULL;
}
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

注意事项

建议不要动 _capa 成员，理论上可以增大， 但不要减小到比 size 小。

含测试代码的完整代码

#include       // printf
#include      // size_t
#include      // malloc

typedef struct _MyList {
    void *_item;        // must be malloced
    struct _MyList *_next;
} MyList;

// 禁止改变容量 capa
typedef struct _MyQueue {
    MyList *_head;       // 头指针
    MyList *_tail;       // 尾指针
    size_t  _size;       // 已用空间
    size_t  _capa;       // 最大容量
} MyQueue;

MyQueue* MyQueueInit(size_t capa) {
    // calloc 会把空间置零, 故指针为 NULL
    MyQueue *queue = (MyQueue *) calloc(4, sizeof(void *));

    queue->_capa = capa;
    return queue;
}

void* MyQueuePopFront(MyQueue *_this) {
    if (_this->_size == 0)
        return NULL;
    
    -- _this->_size;
    MyList *tmp_head = _this->_head;
    void *ret_val = _this->_head->_item;
    _this->_head = _this->_head->_next;
    free(tmp_head);
    return ret_val;
}

// 入队 item, 如果满了，队首元素出队
void* MyQueuePushBack(MyQueue *_this, void *item) {
    // calloc 会把空间置零, 故 new_node->_next == NULL
    MyList *new_node = calloc(2, sizeof(void *));
    if (new_node == NULL) {
        printf("[CRIT WARN]: bad malloc in MyQueuePushBack!\n");
        return NULL;
    }
    new_node->_item = item;

    // 如果 size == 0, 则 head == tail == NULL
    if (_this->_size == 0)
        _this->_head = new_node;
    else
        _this->_tail->_next = new_node;
    
    _this->_tail = new_node;
    ++ _this->_size;

    // 如果满了, 就要出队
    if (_this->_size > _this->_capa)
        return MyQueuePopFront(_this);
    else
        return NULL;
}

// 打印输出
typedef void (*PrintFun)(void *);

void MyQueuePrintAll(MyQueue *_this, PrintFun print_fun) {
    printf("(size = %d): [", _this->_size); 
    MyList *tmp_head = _this->_head;
    while (tmp_head != NULL) {
        print_fun(tmp_head->_item);
        printf(", ");
        tmp_head = tmp_head->_next;
    }
    printf("]\n");
}

// --------------------- 测试代码 --------------------- //

void TestPrintInt(void *item) {
    if (item == NULL)
        printf("NULL");
    else
        printf("%d", *(int *)item);
}

void TestPrintRetVal(void *item) {
    printf("ret_val = ");
    TestPrintInt(item);
    printf("\n");
}

void* TestNewInt(int num) {
    int *item = (int *)malloc(sizeof(int));
    *item = num;
}

int main() {
    // 1. 创建一个容量为4的队列
    MyQueue *queue = MyQueueInit(4);
    MyQueuePrintAll(queue, TestPrintInt);
    int *ret_val;
    // 2. push 一个 1
    ret_val = MyQueuePushBack(queue, TestNewInt(1));
    TestPrintRetVal(ret_val);
    MyQueuePrintAll(queue, TestPrintInt);
    // 3. push 2, 3
    ret_val = MyQueuePushBack(queue, TestNewInt(2));
    TestPrintRetVal(ret_val);
    ret_val = MyQueuePushBack(queue, TestNewInt(3));
    TestPrintRetVal(ret_val);
    MyQueuePrintAll(queue, TestPrintInt);
    // 4. pop
    ret_val = MyQueuePopFront(queue);
    TestPrintRetVal(ret_val);
    MyQueuePrintAll(queue, TestPrintInt);
    // 5. push 一个 4
    ret_val = MyQueuePushBack(queue, TestNewInt(4));
    TestPrintRetVal(ret_val);
    MyQueuePrintAll(queue, TestPrintInt);
    // 6. push 一个 5
    ret_val = MyQueuePushBack(queue, TestNewInt(5));
    TestPrintRetVal(ret_val);
    MyQueuePrintAll(queue, TestPrintInt);
    // 7. push 一个 6
    ret_val = MyQueuePushBack(queue, TestNewInt(6));
    TestPrintRetVal(ret_val);
    MyQueuePrintAll(queue, TestPrintInt);
    // 8. push 一个 7
    ret_val = MyQueuePushBack(queue, TestNewInt(7));
    TestPrintRetVal(ret_val);
    MyQueuePrintAll(queue, TestPrintInt);
    // 9. pop
    ret_val = MyQueuePopFront(queue);
    TestPrintRetVal(ret_val);
    MyQueuePrintAll(queue, TestPrintInt);
}
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

测试结果