這兩天有興趣學習使用了下系統頭文件sys/queue.h中的鏈表/隊列的實現，感覺實現的很是優美，關鍵是以后再也不需要自己實現這些基本的數據結構了，哈哈！
我的系統環境是
正好需要使用隊列，那么本篇就以其中的尾隊列（tail queue）為例，結合實際的測試程序和示意圖（億圖軟件）來說明。
測試程序tailq.c如下：
#include <stdio.h> ?
#include <stdlib.h> ?
#include <sys/queue.h> ?
?
struct _Data { ?
?? ?int???????????????? value; ?
?? ?TAILQ_ENTRY(_Data)? tailq_entry; ?
}; ?
?
int main(int argc, const char *argv[]) ?
{ ?
?? ?/* 1. 初始化隊列 */ ?
#if 0 ?
?? ?TAILQ_HEAD(tailq_head, _Data)?? head = TAILQ_HEAD_INITIALIZER(head); ?
#else ?
?? ?TAILQ_HEAD(tailq_head, _Data)?? head; ?
?? ?TAILQ_INIT(&head); ?
#endif ?
?? ?int i; ?
?? ?struct _Data *pdata = NULL; ?
?
?? ?/* 2. 在隊列末尾插入data1 */ ?
?? ?struct _Data *data1 = (struct _Data *)calloc(1, sizeof(struct _Data)); ?
?? ?data1->value = 1; ?
?? ?TAILQ_INSERT_TAIL(&head, data1, tailq_entry); ?
?? ?/* 3. 在隊列末尾插入data2 */ ?
?? ?struct _Data *data2 = (struct _Data *)calloc(1, sizeof(struct _Data)); ?
?? ?data2->value = 2; ?
?? ?TAILQ_INSERT_TAIL(&head, data2, tailq_entry); ?
?? ?/* 4. 在data1之后插入data3 */ ?
?? ?struct _Data *data3 = (struct _Data *)calloc(1, sizeof(struct _Data)); ?
?? ?data3->value = 3; ?
?? ?TAILQ_INSERT_AFTER(&head, data1, data3, tailq_entry); ?
?? ?/* 5. 在data2之前插入data4 */ ?
?? ?struct _Data *data4 = (struct _Data *)calloc(1, sizeof(struct _Data)); ?
?? ?data4->value = 4; ?
?? ?TAILQ_INSERT_BEFORE(data2, data4, tailq_entry); ?
?? ?/* 6. 在隊列首部插入data5 */ ?
?? ?struct _Data *data5 = (struct _Data *)calloc(1, sizeof(struct _Data)); ?
?? ?data5->value = 5; ?
?? ?TAILQ_INSERT_HEAD(&head, data5, tailq_entry); ?
?? ?/* 遍歷隊列 */ ?
?? ?TAILQ_FOREACH(pdata, &head, tailq_entry) { ?
?? ??? ?printf("pdata->value1 = %d\n", pdata->value);????? ?
?? ?} ?
?? ?puts(""); ?
?? ?/* 7. 刪除data5 */ ?
?? ?TAILQ_REMOVE(&head, data5, tailq_entry); ?
?? ?free(data5);?? ?/* TAILQ_REMOVE宏只是從隊列中刪除該節點，因此還需手動free */
?
?? ?TAILQ_FOREACH(pdata, &head, tailq_entry) { ?
?? ??? ?printf("pdata->value1 = %d\n", pdata->value);????? ?
?? ?} ?
?? ?puts(""); ?
?
?? ?/* 正序遍歷尾隊列 */ ?
?? ?/* 方法一 */ ?
?? ?TAILQ_FOREACH(pdata, &head, tailq_entry) { ?
?? ??? ?printf("pdata->value1 = %d\n", pdata->value);????? ?
?? ?} ?
?? ?puts(""); ?
?? ?/* 方法二 */ ?
?? ?for (pdata = TAILQ_FIRST(&head); pdata;? ?
?? ??? ??? ??? ??? ?pdata = TAILQ_NEXT(pdata, tailq_entry)) { ?
?? ??? ?printf("pdata->value1 = %d\n", pdata->value);????? ?
?? ?} ?
?
?? ?puts(""); ?
?
?? ?/* 逆序遍歷尾隊列 */ ?
?? ?/* 方法一 */ ?
?? ?TAILQ_FOREACH_REVERSE(pdata, &head, tailq_head, tailq_entry) { ?
?? ??? ?printf("pdata->value1 = %d\n", pdata->value);????? ?
?? ?} ?
?? ?puts(""); ?
?? ?/* 方法二 */ ?
?? ?for (pdata = TAILQ_LAST(&head, tailq_head); pdata;? ?
?? ??? ??? ?pdata = TAILQ_PREV(pdata, tailq_head, tailq_entry)) { ?
?? ??? ?printf("pdata->value1 = %d\n", pdata->value);????? ?
?? ??? ?TAILQ_REMOVE(&head, pdata, tailq_entry); ?
?? ??? ?free(pdata); ?
?? ?} ?
?
?? ?if (TAILQ_EMPTY(&head)) { ?
?? ??? ?printf("the tail queue is empty now.\n");??? ?
?? ?} ?
?
?? ?exit(EXIT_SUCCESS); ?
}?
代碼github地址：https://github.com/astrotycoon/sys-queue.h
我們首先來看一下這個尾隊列的定義：
注意，其中的tqe_prev指向的不是前一個元素，而是前一個元素中的tqe_next，這樣定義的一個好處就是*tqe_prev就是自身的地址，**tqe_prev就是自身。
好，現在就順著我的測試程序來一步步看如何使用這個尾隊列吧！
第一步是初始化步驟。關于初始化我們有兩種方法：使用宏TAILQ_HEAD_INITIALIZER或者使用宏TAILQ_INIT，這兩者都是可以的，唯一的區別是傳遞給宏TAILQ_INIT的是地址，而傳遞給宏TAILQ_HEAD_INITIALIZER的不是，這點需要引起我們的注意。
初始化后的數據結構怎樣的呢？ 我們看下示意圖：
接下來的兩個步驟（步奏2和步奏3）都是在這個隊列的尾部追加元素（data1和data2），使用的是宏TAILQ_INSERT_TAIL：
那么隊列的變化過程是這樣的，請看示意圖：
接下來的操作是在data1之前插入data3，使用的是宏TAILQ_INSERT_AFTER：
形象的示意圖如下：
整理后的示意圖如下：
緊接著的操作是在data2之前插入data4，使用的是宏TAILQ_INSERT_BEFORE：
形象的示意圖如下：
整理后的示意圖如下：
現在在隊列首部插入data5，使用的是宏TAILQ_INSERT_HEAD：
形象的示意圖如下：
整理后的示意圖如下：
刪除數據data5使用是宏TAILQ_REMOVE：
現在的隊列布局如下：
好了，基本的操作就這么多，接下來我們看看提供的幾個數據元素訪問方法：
前三個很簡單，一看就懂，我們重點分析下TAILQ_LAST和TAILQ_PREV。
TAILQ_LAST的目的是獲取隊列中的最后一個元素的地址，注意是地址哦！(head)->tqh_last代表的是最后一個元素中tqe_next的地址，通過強轉之后，((struct headname *)((head)->tqh_last))->tqh_last實際上就是最后一個元素中的tqe_prev，而文章一開始介紹定義的時候就說過，*tqe_prev代表的是自身元素的地址，所以TAILQ_LAST最后獲取的就是最后一個元素的地址，宏TAILQ_PREV的道理是一樣的。
OK，測試程序接下來就是遍歷整個隊列，并打印出數據，可以使用提供的宏TAILQ_FOREACH，也可以使用上述的幾個訪問方法來遍歷。
好了，其實本文沒啥內容，對我個人而言就主要是想熟悉下億圖這個軟件，哈哈
?
?
?
?
?
?
?
