這兩天有興趣學(xué)習(xí)使用了下系統(tǒng)頭文件sys/queue.h中的鏈表/隊(duì)列的實(shí)現(xiàn)，感覺實(shí)現(xiàn)的很是優(yōu)美，關(guān)鍵是以后再也不需要自己實(shí)現(xiàn)這些基本的數(shù)據(jù)結(jié)構(gòu)了，哈哈！

我的系統(tǒng)環(huán)境是

正好需要使用隊(duì)列，那么本篇就以其中的尾隊(duì)列（tail queue）為例，結(jié)合實(shí)際的測(cè)試程序和示意圖（億圖軟件）來說明。

測(cè)試程序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. 初始化隊(duì)列 */ ?
#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. 在隊(duì)列末尾插入data1 */ ?
?? ?struct _Data *data1 = (struct _Data *)calloc(1, sizeof(struct _Data)); ?
?? ?data1->value = 1; ?
?? ?TAILQ_INSERT_TAIL(&head, data1, tailq_entry); ?
?? ?/* 3. 在隊(duì)列末尾插入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. 在隊(duì)列首部插入data5 */ ?
?? ?struct _Data *data5 = (struct _Data *)calloc(1, sizeof(struct _Data)); ?
?? ?data5->value = 5; ?
?? ?TAILQ_INSERT_HEAD(&head, data5, tailq_entry); ?
?? ?/* 遍歷隊(duì)列 */ ?
?? ?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宏只是從隊(duì)列中刪除該節(jié)點(diǎn)，因此還需手動(dòng)free */
?
?? ?TAILQ_FOREACH(pdata, &head, tailq_entry) { ?
?? ??? ?printf("pdata->value1 = %d\n", pdata->value);????? ?
?? ?} ?
?? ?puts(""); ?
?
?? ?/* 正序遍歷尾隊(duì)列 */ ?
?? ?/* 方法一 */ ?
?? ?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(""); ?
?
?? ?/* 逆序遍歷尾隊(duì)列 */ ?
?? ?/* 方法一 */ ?
?? ?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

我們首先來看一下這個(gè)尾隊(duì)列的定義：

注意，其中的tqe_prev指向的不是前一個(gè)元素，而是前一個(gè)元素中的tqe_next，這樣定義的一個(gè)好處就是*tqe_prev就是自身的地址，**tqe_prev就是自身。

好，現(xiàn)在就順著我的測(cè)試程序來一步步看如何使用這個(gè)尾隊(duì)列吧！

第一步是初始化步驟。關(guān)于初始化我們有兩種方法：使用宏TAILQ_HEAD_INITIALIZER或者使用宏TAILQ_INIT，這兩者都是可以的，唯一的區(qū)別是傳遞給宏TAILQ_INIT的是地址，而傳遞給宏TAILQ_HEAD_INITIALIZER的不是，這點(diǎn)需要引起我們的注意。

初始化后的數(shù)據(jù)結(jié)構(gòu)怎樣的呢？ 我們看下示意圖：

接下來的兩個(gè)步驟（步奏2和步奏3）都是在這個(gè)隊(duì)列的尾部追加元素（data1和data2），使用的是宏TAILQ_INSERT_TAIL：

那么隊(duì)列的變化過程是這樣的，請(qǐng)看示意圖：

接下來的操作是在data1之前插入data3，使用的是宏TAILQ_INSERT_AFTER：

形象的示意圖如下：

整理后的示意圖如下：

緊接著的操作是在data2之前插入data4，使用的是宏TAILQ_INSERT_BEFORE：

形象的示意圖如下：

整理后的示意圖如下：

現(xiàn)在在隊(duì)列首部插入data5，使用的是宏TAILQ_INSERT_HEAD：

形象的示意圖如下：

整理后的示意圖如下：

刪除數(shù)據(jù)data5使用是宏TAILQ_REMOVE：

現(xiàn)在的隊(duì)列布局如下：

好了，基本的操作就這么多，接下來我們看看提供的幾個(gè)數(shù)據(jù)元素訪問方法：

前三個(gè)很簡(jiǎn)單，一看就懂，我們重點(diǎn)分析下TAILQ_LAST和TAILQ_PREV。

TAILQ_LAST的目的是獲取隊(duì)列中的最后一個(gè)元素的地址，注意是地址哦！(head)->tqh_last代表的是最后一個(gè)元素中tqe_next的地址，通過強(qiáng)轉(zhuǎn)之后，((struct headname *)((head)->tqh_last))->tqh_last實(shí)際上就是最后一個(gè)元素中的tqe_prev，而文章一開始介紹定義的時(shí)候就說過，*tqe_prev代表的是自身元素的地址，所以TAILQ_LAST最后獲取的就是最后一個(gè)元素的地址，宏TAILQ_PREV的道理是一樣的。

OK，測(cè)試程序接下來就是遍歷整個(gè)隊(duì)列，并打印出數(shù)據(jù)，可以使用提供的宏TAILQ_FOREACH，也可以使用上述的幾個(gè)訪問方法來遍歷。

好了，其實(shí)本文沒啥內(nèi)容，對(duì)我個(gè)人而言就主要是想熟悉下億圖這個(gè)軟件，哈哈

?

?

?

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的sys/queue.h分析(图片复制不过来，查看原文)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。