目錄

?編輯

（一）隊列的定義,初始化及創建結點

?

?（二）入隊和出隊，以及取隊頭隊尾的數據

(三)銷毀隊列

---

隊列是指只允許在一端進行插入數據操作，在另?端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)的特點。本篇文章的隊列以鏈表為基礎進行創建

---

（一）隊列的定義,初始化及創建結點

//隊列的初始化
//我們先宏定義隊列存儲的數據類型#define QueueDataType int           //這里我們宏定義隊列存儲的數據類型為int//這里定義隊列的結點
typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QueueNode;//為了方便隊列的出隊和入隊我們要新定義一個結構體，里面裝著頭結點和尾結點的指針。
type struct Queue
{QueueNode* phead;QueueNode* ptail;
}Queue;

?

這里我們定義了隊列的結點和管理整個隊列的結構體。關于鏈表形式的數據結構我們往往要單獨寫封裝一個函數來創建結點。

//封裝一個函數，專門用來創建結點
//該函數的形參是一個數據類型，返回創建的結點的指針
QueueNode* BuyNewNode(QueueDataType val)
{//動態向內存申請空間QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//防止使用創建結點失敗返回的NULL指針if (newnode == NULL){perror("newnode malloc failed!");exit(1);}//給創建好的結點初始化newnode->data = val;newnode->next = NULL;//返回初始值return newnode;
}

我們還需要初始化管理整個結點的那個結構體，就叫它隊列吧

//初始化隊列
void InitQueue(Queue* pq)
{//檢查是否為空指針assert(pq);pq->phead = NULL;pq->ptail = NULL;
}

?

?

?（二）入隊和出隊，以及取隊頭隊尾的數據

入隊就是從隊伍的后面進去。根據這個原理我們直接寫

//隊列的入隊（要在初始化隊列之后）
//我們通過管理整個隊列的那個結構體來進行操作
//所以這里我們接受那個結構體的形參
void QueuePush(Queue* pq, QueueDataType val)
{//檢查是不是空指針assert(pq);//我們可以通過pq來找到隊伍的尾結點//進行入隊操作。如果隊列為空if (pq->phead == NULL){pq->phead = pq->ptail = BuyNewNode(val);}else                //如果隊列不為空，則尾插到隊尾{pq->ptail->next = BuyNewNode(val);pq->ptail = pq->ptail->next;}
}

在寫出隊之前我們先得寫一個函數來檢查隊列是否為空，防止隊列里沒有數據

//判斷隊列是否為空，我們采用bool值
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

進行出隊。

//隊列的出隊
void QueuePop(Queue* pq)
{    //檢查隊列是否為空assert(!QueueEmpty(pq));//如果隊列只有一個元素if (pq->phead == pq->ptail){pq->phead = pq->ptail = NULL;}else{    //定義一個新結點來保存出隊后的頭結點QueueNode* ptem = pq->phead->next;free(pq->phead); pq->phead = ptem;}
}    

取隊頭就很簡單了，也是直接寫

//取隊頭
QueueDataType QueueFront(Queue* pq)
{//檢查隊列是否為空assert(!QueueEmpty(pq));return pq->phead->data;
}

取隊尾更是無需多言

//取隊尾的數據    
void QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}

?

(三)銷毀隊列

最后的環節也必然是我們的銷毀隊列

//銷毀隊列    
void QueueDestroy(Queue* pq)
{assert(pq);//新定義一個結點用來遍歷隊列QueueNode* pcur = pq->phead;//開始遍歷鏈表銷毀while (pcur){    //再新定義一個結點來保存下一個節點QueueNode* ptem = pcur->next;free(pcur);pcur = ptem;}pq->phead = pq->ptail = NULL;
}