本博客（）贴出作者（阿波）相关研究、学习内容所做的笔记，欢迎广大朋友指正！
Content
0.序
1.队列结构
2.队列操作
2.1在头节点之后插入
2.2在尾节点之后插入
2.3删除节点
2.4分割队列
2.5链接队列
2.6获取中间节点
2.7队列排序
2.8如何获取队列节点数据
3.一个例子
3.1代码
3.2如何编译
3.3运行结果
4.小结
0.序
1.队列结构
typedef struct ngx_queue_s ngx_queue_t;struct ngx_queue_s {//队列结构ngx_queue_t *prev;ngx_queue_t *next;};
2.队列操作
队列有如下操作。
//初始化队列ngx_queue_init(q)//判断队列是否为空ngx_queue_empty(h)//在头节点之后插入新节点ngx_queue_insert_head(h, x)//在尾节点之后插入新节点ngx_queue_insert_tail(h, x)//删除节点xngx_queue_remove(x)//分割队列ngx_queue_split(h, q, n)//链接队列ngx_queue_add(h, n)//获取队列的中间节点ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue)//排序队列(稳定的插入排序)void ngx_queue_sort(ngx_queue_t *queue,ngx_int_t (*cmp)(const ngx_queue_t*, const ngx_queue_t*))
其中，插入节点、取队列头、取队列尾等操作由宏实现，获取中间节点、排序等操作由函数实现。下面简单介绍。
2.1在头节点之后插入
#define ngx_queue_insert_head(h, x)\(x)->next = (h)->next;\(x)->next->prev = x;\(x)->prev = h;\(h)->next = x画出该操作的逻辑图，如下。
2.2在尾节点之后插入
#define ngx_queue_insert_tail(h, x)\(x)->prev = (h)->prev;\(x)->prev->next = x;\(x)->next = h;\(h)->prev = x
该操作的逻辑图如下。
2.3删除节点
#if (NGX_DEBUG)#define ngx_queue_remove(x)\(x)->next->prev = (x)->prev;\(x)->prev->next = (x)->next;\(x)->prev = NULL;\(x)->next = NULL#else#define ngx_queue_remove(x)\(x)->next->prev = (x)->prev;\(x)->prev->next = (x)->next#endif该操作的逻辑图如下。
2.4分割队列
#define ngx_queue_split(h, q, n)\(n)->prev = (h)->prev;\(n)->prev->next = n;\(n)->next = q;\(h)->prev = (q)->prev;\(h)->prev->next = h;\(q)->prev = n;
2.5链接队列
#define ngx_queue_add(h, n)\(h)->prev->next = (n)->next;\(n)->next->prev = (h)->prev;\(h)->prev = (n)->prev;\(h)->prev->next = h;
2.6获取中间节点
/* * find the middle queue element if the queue has odd number of elements * or the first element of the queue’s second part otherwise */ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue){ngx_queue_t *middle, *next;middle = ngx_queue_head(queue);if (middle == ngx_queue_last(queue)) {return middle;}next = ngx_queue_head(queue);for ( ;; ) {middle = ngx_queue_next(middle);next = ngx_queue_next(next);if (next == ngx_queue_last(queue)) {//偶数个节点，在此返回后半个队列的第一个节点return middle;}next = ngx_queue_next(next);if (next == ngx_queue_last(queue)) {//奇数个节点，在此返回中间节点return middle;}}}
为什么该算法能够找到中间节点？
因害怕失败而不敢放手一搏，永远不会成功
