隊列

隊列的管理使用單向鏈表結構。個人認為使用雙向鏈表更易于維護。

注意：

每個以列隊為基礎管理的結構都必須將第一個元素設定為列隊元件的指針。

進行列隊操作時都需要關閉任務調度，防止多線程操作的信息同步問題。

隊列的管理結構

//隊列的管理結構 typedef struct {void????? *pHead;?????? //指向隊列的頭部節點void????? *pTail;???????//指向隊列的尾部節點 } wsfQueue_t;/* 隊列的元件 */ typedef struct wsfQueueElem_tag {struct wsfQueueElem_tag *pNext;????????? //保存一個指向下一位置的指針 } wsfQueueElem_t;

隊列的初始化

? ? ? ? 隊列的初始化比較簡單，僅僅是將頭部節點和尾部節點指向NULL

#define WSF_QUEUE_INIT(pQueue) {(pQueue)->pHead = NULL; (pQueue)->pTail = NULL;}

隊列尾部增加節點

? ? ? ? 判斷下隊列是否為空，為空增加為頭部，不為空增加到尾部。僅更改尾部節點。

//向列隊的尾部添加一個節點 void WsfQueueEnq(wsfQueue_t *pQueue, void *pElem) {WSF_CS_INIT(cs);WSF_ASSERT(pQueue != NULL);WSF_ASSERT(pElem != NULL);/* 節點的下一個節點指向空 */WSF_QUEUE_NEXT(pElem) = NULL;/* enter critical section */WSF_CS_ENTER(cs);/* 列隊為空，設置列隊的的頭尾都是剛添加的節點 */if (pQueue->pHead == NULL){pQueue->pHead = pElem;pQueue->pTail = pElem;}/* 添加到列隊的尾部。 */else{WSF_QUEUE_NEXT(pQueue->pTail) = pElem;pQueue->pTail = pElem;}/* exit critical section */WSF_CS_EXIT(cs); }

隊列頭部取出節點

? ? ? ? 取出頭部節點并返回。并判斷是否將列隊取空了，若空了重新設置尾部節點。

//從列隊的頭部取出一個節點 void *WsfQueueDeq(wsfQueue_t *pQueue) {wsfQueueElem_t *pElem;WSF_CS_INIT(cs);WSF_ASSERT(pQueue != NULL);/* enter critical section */WSF_CS_ENTER(cs);pElem = pQueue->pHead;/* 列隊不為空時進行操作 */if (pElem != NULL){/* 將頭部節點指向下一個 */pQueue->pHead = WSF_QUEUE_NEXT(pElem);/* 判斷是都將列隊取空了 */if (pQueue->pHead == NULL){pQueue->pTail = NULL;}}/* exit critical section */WSF_CS_EXIT(cs);return pElem; }

隊列頭部插入節點

? ? ? ? ?操作類似，不一一贅述，都為單向鏈表。

void WsfQueuePush(wsfQueue_t *pQueue, void *pElem) {WSF_CS_INIT(cs);WSF_ASSERT(pQueue != NULL);WSF_ASSERT(pElem != NULL);/* enter critical section */WSF_CS_ENTER(cs);/* 設置節點的下一個節點為頭部 */WSF_QUEUE_NEXT(pElem) = pQueue->pHead;/* 列隊為空的話同時設置尾部指針 */if (pQueue->pHead == NULL){pQueue->pTail = pElem;}/* 重新設置頭部節點 */pQueue->pHead = pElem;/* exit critical section */WSF_CS_EXIT(cs); }

?

隊列中間插入節點

? ? ? ?由于是單向鏈表，因此必須提供前一個節點的指針。

//列隊中間插入一個元素。必須提供上一個節點的指針。 void WsfQueueInsert(wsfQueue_t *pQueue, void *pElem, void *pPrev) {WSF_CS_INIT(cs);WSF_ASSERT(pQueue != NULL);WSF_ASSERT(pElem != NULL);/* enter critical section */WSF_CS_ENTER(cs);/* 列隊為空或者上一節點為尾部節點時，直接添加到尾部 */if (pQueue->pHead == NULL || pPrev == pQueue->pTail){/* 常規添加到列隊的尾部 */WsfQueueEnq(pQueue, pElem);}/* 判斷上一節點是不是頭部 */else if (pPrev == NULL){/* 添加到列隊的頭部 */WsfQueuePush(pQueue, pElem);}else{/* 插入到兩個節點中間 */WSF_QUEUE_NEXT(pElem) = WSF_QUEUE_NEXT(pPrev);WSF_QUEUE_NEXT(pPrev) = pElem;}/* exit critical section */WSF_CS_EXIT(cs); }

?

隊列中間刪除節點

由于是單向鏈表，因此必須提供前一個節點的指針。

void WsfQueueRemove(wsfQueue_t *pQueue, void *pElem, void *pPrev) {WSF_CS_INIT(cs);WSF_ASSERT(pQueue != NULL);WSF_ASSERT(pQueue->pHead != NULL);WSF_ASSERT(pElem != NULL);/* enter critical section */WSF_CS_ENTER(cs);/* 頭部節點 */if (pElem == pQueue->pHead){/* 將頭部節點指向當前節點的下一個 */pQueue->pHead = WSF_QUEUE_NEXT(pElem);}else if (pPrev){/* 下一個節點的next指向當前節點的next */WSF_QUEUE_NEXT(pPrev) = WSF_QUEUE_NEXT(pElem);}/* 如果是尾部節點 */if (pElem == pQueue->pTail){/* 尾部節點更新為上一個節點 */pQueue->pTail = pPrev;}/* exit critical section */WSF_CS_EXIT(cs); }

?

?

總結

以上是生活随笔為你收集整理的WSF操作系统抽象层学习笔记（二）---列队（单向链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。