本文探讨在 C 语言中如何实现一个队列。
用 C 语言实现队列（或其他数据结构）有以下几个要点：
- 如何实现泛型？即所有类型适用，即使是自定义结构体。C++ 使用模板可轻松实现。C 语言中实现泛型主要有两种方式：
void *和宏定义。 - 如何高效地进行内存管理？由谁负责队列本身和数据的内存管理？调用者还是队列模块本身？
- 基于数组还是链表？一般基于数组比较简单
- 时空性能？时间复杂度和空间占用。对于时间复杂度，队列主要有两个操作：入队列和出队列，这通常都是O(1)。空间占用一般取决于采用数组还是链表，后者往往会由于至少多一个 next 指针而多些内存占用，但数组一般会预分配固定大小的空间，如果有部分未使用，也存在浪费。
- 错误处理？有的实现返回 void，在操作失败时直接提前返回，不进行实际操作，有的返回 bool，失败时会返回 false。
标准库
首先想到的肯定还是直接使用标准库，那么 C 标准库中有队列吗？答案是否定的。为什么没有呢？我的理解是 C 语言中很难实现一个大家都认可的、使用方便的队列库。首先最重要的一点是 C 语言并不原生支持泛型，或者支持起来很麻烦（通常是使用 void *），此外 C 语言是原始的，比较低级的语言（这里的“低级”指它接近硬件，越“高级”越远离硬件），这就意味着在高级语言中很简单的事在 C 语言中实现起来都比较麻烦，另外 C 是灵活的，实现队列的方式非常多，甚至很难评价哪个是最好的。除了队列，其他数据结构，如链表、栈等更是如此。
非标准库
那么退而求其次，非标准库呢？当然是有的，而且还比较多：
- https://github.com/SMFSW/cQueue：支持 FIFO 和 LIFO（话说 LIFO 不就是栈吗？），支持静态和动态内存分配，使用
void *方式实现泛型，基于数组实现队列，队列模块负责所有内存管理。License 为 BSD 3。 - https://github.com/attractivechaos/klib: 追求极致性能和极小内存占用，宏定义方式实现泛型，代码简洁，功能简单纯粹，使用起来会觉得有点难用。其中 kvec.h 可以作为栈使用，klist.h 可以作为队列使用。MIT License
- linux kernel list.h: Linux 内核中的双向链表
list.h很容易作为队列使用。相比前面两种，在实现泛型方面，它的实现方式非常特别：它既未使用void *，也未使用宏，而是采用嵌入链表结构体list_head到自定义数据结构体的方式来实现泛型，这样一来，它的实现代码非常简洁纯粹，但链表和数据的内存管理就全部交给了调用者。具体可参考图文讲解｜玩转内核链表 list - 知乎理解其原理和使用方法。 - https://code.google.com/archive/p/c-generic-library/：谷歌开发的一个 C 语言实现的算法库
- https://github.com/fragglet/c-algorithms:
void *方式实现泛型，类 MIT License。甚至于可以说没有实现泛型，它通过typedef将void *定义为QueueValue，然后一直使用的QueueValue，所以使用时应该需要将自定义结构体typedef为QueueValue，但这种不属于模块支持泛型，因为它无法在一个程序中使用多次。 sys/queue.h- https://github.com/bitwiseworks/libcx