在前面兩篇博客中,我分別使用了靜態數組和動態數組來模擬循環隊列。但是線性表中和隊列最神似的莫過於鏈表了。我在前面也使用了大量的篇幅來講述了鏈表的各種操作。今天我們使用一種比較特殊的鏈表——非循環雙向鏈表來實現隊列。首先這裡的說明的是構建的是普通的隊列,而不是循環隊列。當我們使用數組的時候創建循環隊列是為了節省存儲空間,而來到鏈表中時,每一個節點都是動態申請和釋放的,不會造成空間的浪費,所以就不需要采用循環隊列了。第二,大家在很多書上看到的是使用單鏈表實現隊列,我這裡將會使用帶頭結點尾結點的非循環雙鏈表實現,雖然多維護了兩個節點和指針域,但是在鏈表頭尾進行插入刪除的時候不需要遍歷鏈表了,隊列操作變得非常的方便。真正實現了只在頭尾操作。
核心代碼如下:
(1)初始化隊列
//初始化帶頭結點和尾結點的非循環雙向鏈表 void InitialQueue(Queue **pHead,Queue **pTail){ *pHead = (Queue *)malloc(sizeof(Queue)); *pTail = (Queue *)malloc(sizeof(Queue)); if (*pHead == NULL || *pTail == NULL) { printf("%s函數執行,內存分配失敗,初始化雙鏈表失敗\n",__FUNCTION__); }else{ //這個裡面是關鍵,也是判空的重要條件 (*pHead)->next = NULL; (*pTail)->prior = NULL; //鏈表為空的時候把頭結點和尾結點連起來 (*pHead)->prior = *pTail; (*pTail)->next = *pHead; printf("%s函數執行,帶頭結點和尾節點的雙向非循環鏈表初始化成功\n",__FUNCTION__); } }
//入隊,也就是在鏈表的尾部插入節點 void EnQueue(Queue *head,Queue *tail,int x){ Queue *pInsert; pInsert = (Queue *)malloc(sizeof(Queue)); memset(pInsert, 0, sizeof(Queue)); pInsert->next = NULL; pInsert->prior = NULL; pInsert->element = x; tail->next->prior = pInsert; pInsert->next = tail->next; tail->next = pInsert; pInsert->prior = tail; }
//出隊,在隊列頭部刪除元素 void DeQueue(Queue *head,Queue *tail){ if (IsEmpty(head,tail)) { printf("隊列為空,出隊列失敗\n"); }else{ Queue *pFreeNode; pFreeNode = head->prior; head->prior->prior->next = head; head->prior = head->prior->prior; free(pFreeNode); pFreeNode = NULL; } }(4)打印所有節點
//打印出從隊列頭部到尾部的所有元素 void PrintQueue(Queue *head,Queue *tail){ Queue *pMove; pMove = head->prior; printf("當前隊列中的元素為(從頭部開始):"); while (pMove != tail) { printf("%d ",pMove->element); pMove = pMove->prior; } printf("\n"); }
//判斷隊列是否為空,為空返回1,否則返回0 int IsEmpty(Queue *head,Queue *tail){ if (head->prior == tail) { return 1; } return 0; }
int main(int argc, const char * argv[]) { Queue *pHead;//頭結點 Queue *pTail;//尾結點 InitialQueue(&pHead, &pTail); EnQueue(pHead, pTail, 2);EnQueue(pHead, pTail, 1); EnQueue(pHead, pTail, 9);EnQueue(pHead, pTail, 3);EnQueue(pHead, pTail, 4); PrintQueue(pHead, pTail); DeQueue(pHead,pTail);DeQueue(pHead,pTail);DeQueue(pHead,pTail); PrintQueue(pHead, pTail); return 0; }