nginx 的队列定义在 core/ngx_queue.h中
struct ngx_queue_s {
ngx_queue_t *prev;
ngx_queue_t *next;
};
首先这个队列很奇怪，因为它只有上一元素与下一元素的指针，却没有数据的结构成员。
那么它是如何存储与取得队列节点中的数据呢？看core/ngx_queue.h中的定义：
#define ngx_queue_data(q, type, link) \
(type *) ((u_char *) q - offsetof(type, link))
其实ngx_queue只是一个幌子，真正存储在队列中的元素是包含ngx_queue成员的结构。换句话说：如果一个结构想使用队列的方式存储，那么这个结构就要包含ngx_queue成员。
offset这里用到了C语言的一个技巧：offsetof 函数：根据结构的成员的指针定位结构的指针：理解了这个，ngx_queue 就明白了。
例如
struct x_s{
int a;
int b;
} x;
则 &x.b = ＆x + (&x.b - &x) = &x + offsetof(struct x_s, b);
所以只要一个结构里有ngx_queue成员，就可以根据ngx_queue成员的指针获得这个结构的指针。
如http/ngx_http_cache.h中的ngx_http_file_cache_node_t结构，包含一个ngx_queue的成员queue，然后在http/ngx_http_file_cache.c文件中采用这种方法从队列中获取结构：
ngx_http_file_cache_node_t *fcn = ngx_queue_data(q, ngx_http_file_cache_node_t, queue);
根据上面的ngx_queue_data的定义: type=ngx_http_file_cache_node_t, offset=queue，所以可以展开为：
ngx_http_file_cache_node_t *fcn =
(ngx_http_file_cache_node_t*) ((u_char*)q - offset(ngx_http_file_cache_node_t, queue));
ngx_http_file_cache_node结构如下所示：
+-------+---------+----+
| node | queue | ... |
+-------+---------+----+
结构的起始指针 = queue的起始位置 - queue在结构内的偏移.
nginx 的一个四节点的队列 ngx_queue 如下所示：
1的next指向2，2的next指向3，3的next指向4，4的next指向1
2的prev指向1，3的prev指向2，4的prev指向3，1的prev指向4
每个要使用队列存储的结构必须包含ngx_queue成员，有点像继承，其实是组合，组合优于继承！
nginx 的队列基本操作和传统队列没有什么区别，基本都用宏的方式定义在core/ngx_queue.h中，与众不同的操作有两个，定义在core/ngx_queue.c中：
取队列中间元素：
从ngx_queue的定义可以看出，nginx 的队列设计非常简单，没有存储队列的长度信息。所以要取得队列中间的一个元素，最简单的方法是：先遍历队列计算出队列长度n，然后再从队列头走n/2步，就找到队列中间的元素了。算法复杂度为O(n)+O(n/2)=O(3n/2)
但 nginx 没有采取这种方式，而是用了两个指针，一个步长为1,另一个步长为2,同时向前移动，当步长为2的指针到达队列末尾的时候，步长为1的指针刚好在队列的开头。
算法复杂度也是O(n)+(n/2)=O(3n/2)
但它的优点有两个，一是局部性较好，二是代码比较优雅。一个循环比两个循环看起来好看一些:)。
代码见core/ngx_queue.c的ngx_queue_middle函数：
middle = ngx_queue_head(queue); //步长为1的指针m
next = ngx_queue_head(queue); //步长为2的指针n
for ( ;; ) {//遍历队列
middle = ngx_queue_next(middle); //m走一步
next = ngx_queue_next(next); //n走一步
if (next == ngx_queue_last(queue)) {
return middle;//n到头了
}
next = ngx_queue_next(next); //n再走一步
if (next == ngx_queue_last(queue)) {
return middle;//n到头了
}
}
队列排序：排序算法主要有插入，选择，快排，堆排等，考虑到队列没有随机访问能力的问题，使用插入排序是队列排序的一个较好的选择，而 nginx 也确实选用了这种方法：
从队列的第2个节点开始，针对每个节点，先从队列里拿出来，然后再向前找适当的位置，再插入。
代码见core/ngx_queue.c的ngx_queue_sort函数：
q = ngx_queue_head(queue);
for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) { //2-n
prev = ngx_queue_prev(q); //记录前一个节点
next = ngx_queue_next(q); //记录后一个节点
ngx_queue_remove(q); //1。先把当前节点从队列中取出
do { //2。向前查找，找到插入的位置(即比当前节点小的节点)
if (cmp(prev, q) <= 0) break;
prev = ngx_queue_prev(prev);
} while (prev != ngx_queue_sentinel(queue));
ngx_queue_insert_after(prev, q);//3。插入当前节点。。
}
}
例如
有一个int 队列：
2 3 5 8 4 6 9
进行到第5个元素4时，首先将4从中取出，
2 3 5 8 6 9
然后向前查，8－5－3，发现3比4小，则在3后面插入4
2 3 4 5 8 6 9
接着处理下一个节点6
