转载时请注明出处和作者联系方式
文章出处：http://www.limodev.cn/blog
作者联系方式：李先静 <xianjimli at hotmail dot com>
队列
队列是一种很常用的数据，操作系统用队列来管理运行的进程，驱动程序用队列来管理要传输的数据包，GUI框架用队列来管理各种GUI事件。队列是一 种先进先出(FIFO, First in First out)的数据结构，数据只能从队列头取，向队列尾追加。队列的名称很形象的表达了它的意义，就像排队上车一样，前面的先上，后来的站在后面排队。
队列主要的接口函数有：
o 创建队列：queue_create
o 取队列头的元素：queue_head
o 追加一个元素到队列尾：queue_push
o 删除队列头元素：queue_pop
o 取队列中元素个数(同时也可以判断队列是否为空)：queue_length
o 遍历队列中的元素：queue_foreach;
o 销毁队列 queue_destroy
队列看起来比链表和数组要高级一点，其实它只不过是链表和数组的一种特殊形式而已，下面我们重用链表来实现队列：
o 队列的数据结构
struct _Queue
{
DList* dlist;
};
这里队列只是对双向链表的一个包装。
o 创建队列
Queue* queue_create(DataDestroyFunc data_destroy, void* ctx)
{
Queue* thiz = (Queue*)malloc(sizeof(Queue));
if(thiz != NULL)
{
if((thiz->dlist = dlist_create(data_destroy, ctx)) == NULL)
{
free(thiz);
thiz = NULL;
}
}
return thiz;
}
创建队列时，除了分配自己的空间外，就是简单的创建一个双向链表。
o 取队列头的元素
Ret queue_head(Queue* thiz, void** data)
{
return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS);
return dlist_get_by_index(thiz->dlist, 0, data);
}
我们认为链表的第一个元素是队列头，取队列头的元素就是取链表的第一个元素。
o 追加一个元素到队列尾
Ret queue_push(Queue* thiz, void* data)
{
return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);
return dlist_append(thiz->dlist, data);
}
我们认为链表的最后一个元素是队列尾，追加一个元素到队列尾就是追加一个元素到链表尾。
o 删除队列头元素
Ret queue_pop(Queue* thiz)
{
return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);
return dlist_delete(thiz->dlist, 0);
}
删除队列头的元素就是删除链表的第一个元素。
o 取队列中元素个数
size_t queue_length(Queue* thiz)
{
return_val_if_fail(thiz != NULL, 0);
return dlist_length(thiz->dlist);
}
队列中元素的个数等同于链表元素的个数。
o 遍历队列中的元素
Ret queue_foreach(Queue* thiz, DataVisitFunc visit, void* ctx)
{
return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);
return dlist_foreach(thiz->dlist, visit, ctx);
}
遍历队列中的元素等同于遍历链表中的元素。
o 销毁队列
void queue_destroy(Queue* thiz)
{
if(thiz != NULL)
{
dlist_destroy(thiz->dlist);
thiz->dlist = NULL;
free(thiz);
}
return;
}
销毁链表然后释放自身的空间。
用组合的方式实现队列很简单吧，不用半小时就可以写出来。虽然链表已经通过了自动测试，队列的自动测试也不能省，在这里我们就不列出代码了。
上面我们实现的是通用队列，除了通用队列外，还有几种特殊队列应用也非常广泛：
o 优先级队列。它的不同之外在于，插入元素时，不必追加到队尾，而是根据元素的优先级插到队列的适当位置。这个就像排队上车时，后面来了个老人，大家让他先上一样的。内核的进程管理器通常采用估先级队列管理进程。
o 循环队列。循环队列的特点是最大元素个数是固定的。这个我们在前面学习同步时已经提过，它的优点是两个并发的实体(线程或进程)，按一个读一个写的方式访问，不需要加锁。设备驱动程序经常使用循环队列来管理数据包。