目錄

1.隊列的概念及結構

2.隊列的實現

2.1隊列結構定義?

2.2隊列的初始化及銷毀

2.3數據入隊

2.4數據出隊

2.5訪問隊頭數據

2.6訪問隊尾數據

2.6判斷隊列是否為空

2.7求隊列的大小

2.7打印隊列?

---

1.隊列的概念及結構

隊列：只允許在一端進行插入數據操作，另一端進行刪除數據操作的特殊線性表

隊列中先進先出FIFO（First In First Out）

入隊列：進行插入操作的一端稱為隊尾

出隊列：進行刪除操作的一端稱為隊頭

2.隊列的實現

隊列結構可以使用數組和鏈表結構實現，但一般采用的是鏈表，因為對于數組結構，隊頭出數據的效率較低

2.1隊列結構定義?

使用鏈表實現隊列，隊列中的每個元素都是節點的形式，所以需要定義節點的結構

對于隊列，其具有隊尾入數據，隊頭出數據的特性，所以其結構定義需要兩個指針，分別指向隊頭和隊尾

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;

2.2隊列的初始化及銷毀

初始化即隊列為空隊列，隊頭指針和隊尾指針都指向空

銷毀隊列，即釋放隊列中所有節點的空間，隊頭指針和隊尾指針重新指向空

//隊列初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}
//隊列銷毀
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->head = pq->tail = NULL;
}

2.3數據入隊

隊列結構中，數據入隊從隊尾入，需要考慮空隊列和非空隊列兩種情況

1??空隊列：

2??非空隊列：

?空隊列和非空隊列不同的是空隊列插入數據時需要更新隊頭指針

//數據入隊
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;}//空隊列時插入if (pq->tail == NULL){pq->head = pq->tail = newnode;}//非空隊列時插入else{pq->tail->next = newnode;//鏈接新元素pq->tail = newnode;//更新隊尾}
}

2.4數據出隊

隊列結構中，數據出隊從隊頭出，對于空隊列，出隊操作非法

出隊操作后，需要更新隊頭指針，并釋放已出隊節點的空間

特殊情況：隊列中只有一個節點

//數據出隊
void QueuePop(Queue* pq)
{assert(pq);//空隊列不能進行出隊操作assert(!QueueEmpty(pq));//隊列中只有一個元素if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;}
}

2.5訪問隊頭數據

隊頭數據的訪問操作在隊列為空時非法，所以需要先斷言，非空鏈表才可以進行隊頭數據的訪問操作，通過隊頭指針訪問即可

//訪問隊頭數據
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}

2.6訪問隊尾數據

隊尾數據的訪問操作在隊列為空時非法，所以需要先斷言，非空鏈表才可以進行隊尾數據的訪問操作，通過隊尾指針訪問即可

//訪問隊尾數據
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

2.6判斷隊列是否為空

隊列為空則隊頭指針和隊尾指針都指向空，可以使用if-else語句進行返回

也可以參考以下代碼，直接返回pq->head == NULL && pq->tail == NULL，只有當pq->head和pq->tail同時為NULL是才返回真，即隊列為空

📖Note：

判空函數的返回類型為bool，但是C語言標準中沒有bool類型，所以需要我們自己定義

#define bool int

//判斷隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);/*if (pq->tail == pq->head == NULL){return true;}else{return false;}*/return pq->head == NULL && pq->tail == NULL;
}

2.7求隊列的大小

求隊列的大小，遍歷統計節點個數并返回即可

//求隊列的大小
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;
}

2.7打印隊列?

為了便于觀察入隊與出隊操作，可以編寫一個打印函數便于調試

//打印隊列
void QueuePrint(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}