目錄

前言

1.什么是鏈隊

2.鏈隊的表示和實現

1.定義

2.初始化

3.銷毀

4.清空

5.空隊列

6.隊列長度

7.獲取隊頭

8.入隊

9.出隊

10.遍歷隊列

11.完整代碼

---

前言

? ? 本篇博客介紹鏈棧隊列的表示和實現。

1.什么是鏈隊

? ? 鏈隊是采用鏈式存儲結構實現的隊列。通常鏈隊使用單鏈表表示。

? ?

圖1.鏈隊的示意圖

? ? ?為了操作方便，我們給鏈隊列增加一個頭結點，令頭指針始終指向頭結點。

2.鏈隊的表示和實現

1.定義

typedef int QElemType;
typedef int Status;
typedef struct QNode{QElemType data;struct QNode * next;
}QNode,*QueuePtr;
typedef struct {QueuePtr front;//隊頭指針QueuePtr rear;//隊尾指針
}LinkQueue;

2.初始化

? ? ? ? ? ? 初始化的時候給鏈隊分配一個結點。

? ? ? ? 圖2.空隊列

//初始化
Status initLinkQueue(LinkQueue * linkQueue){linkQueue->front =  linkQueue->rear = (QueuePtr)malloc(sizeof(QNode));if (!linkQueue->front) {return 0;}return 1;
}

3.銷毀

????????當需要銷毀隊列時，我們需要釋放隊列中所有節點的內存，并將隊列結構體中的指針置空。

? ? ? ? ?我們需要遍歷所有的結點，釋放結點內存，最后置空頭結點。

// 銷毀隊列
void destroyLinkQueue(LinkQueue *linkQueue) {while (linkQueue->front) { // 循環釋放隊列中所有節點的內存QueuePtr temp = linkQueue->front;linkQueue->front = linkQueue->front->next;free(temp);}linkQueue->rear = NULL; // 將 rear 指針置空
}

4.清空

????????清空隊列的方法與銷毀隊列的方法類似，但不釋放隊列結構體本身的內存，只釋放隊列中節點的內存并將隊列恢復到初始狀態。

// 清空隊列
void clearLinkQueue(LinkQueue *linkQueue) {while (linkQueue->front) { // 循環釋放隊列中所有節點的內存QueuePtr temp = linkQueue->front;linkQueue->front = linkQueue->front->next;free(temp);}linkQueue->rear = NULL; // 將 rear 指針置空
}

5.空隊列

? ? ? ? 隊頭和隊尾相同的時候為空隊列。

// 判斷隊列是否為空
Status isLinkQueueEmpty(LinkQueue *linkQueue) {return linkQueue->front == NULL; // 如果隊頭指針為空，則隊列為空
}

6.隊列長度

// 計算隊列長度
int getLinkQueueLength(LinkQueue *linkQueue) {int length = 0;QueuePtr p = linkQueue->front->next; // 從隊頭指針開始while (p != NULL) { // 遍歷隊列length++;p = p->next;}return length;
}

7.獲取隊頭

? ? ? ? 獲取隊頭元素。

// 獲取隊列頭結點
Status getLinkQueueFront(LinkQueue *linkQueue, QElemType *element) {if (linkQueue->front == NULL) { // 隊列為空return 0;}*element = linkQueue->front->next->data; // 將隊頭節點的數據存儲到 element 中return 1;
}

8.入隊

? ? ? ? 入隊列的時候如下所示。

? ? ? ? 圖3.入隊列示意圖

// 入隊列
Status enLinkQueue(LinkQueue * linkQueue,QElemType element){QueuePtr newNode = (QNode *)malloc(sizeof(QNode));//生成一個新節點if (!newNode) {return 0;}newNode->data = element;newNode->next = NULL;linkQueue->rear->next = newNode;linkQueue->rear = newNode;return 1;
}

9.出隊

? ? ? ? 出隊列的時候如下如所示：

圖4.出隊列示意圖

// 出隊列
Status deLinkQueue(LinkQueue * linkQueue,QElemType *element){if (linkQueue->front == linkQueue->rear) {//空隊列return 0;}QueuePtr p = linkQueue->front->next;// 指向頭結點* element = p->data;linkQueue->front->next = p->next;//修改頭指針if (linkQueue->front == p) {//如果僅有一個節點linkQueue->rear = linkQueue->front;//修改尾指針}free(p);return 1;
}

10.遍歷隊列

// 遍歷隊列（忽略頭結點）
void traverseLinkQueueIgnoreHead(LinkQueue *linkQueue) {if (linkQueue->front == NULL || linkQueue->front->next == NULL) { // 隊列為空或只有頭結點printf("隊列為空\n");return;}QueuePtr current = linkQueue->front->next; // 從頭結點的下一個節點開始遍歷while (current != NULL) { // 遍歷直到隊尾printf("%d\t", current->data); // 打印當前節點的數據current = current->next; // 移動到下一個節點}printf("\n");
}

11.完整代碼

#include <stdlib.h>typedef int QElemType;
typedef int Status;
typedef struct QNode{QElemType data;struct QNode * next;
}QNode,*QueuePtr;
typedef struct {QueuePtr front;//隊頭指針QueuePtr rear;//隊尾指針
}LinkQueue;//初始化
Status initLinkQueue(LinkQueue * linkQueue){linkQueue->front =  linkQueue->rear = (QueuePtr)malloc(sizeof(QNode));if (!linkQueue->front) {return 0;}return 1;
}
// 銷毀隊列
void destroyLinkQueue(LinkQueue *linkQueue) {while (linkQueue->front) { // 循環釋放隊列中所有節點的內存QueuePtr temp = linkQueue->front;linkQueue->front = linkQueue->front->next;free(temp);}linkQueue->rear = NULL; // 將 rear 指針置空
}
// 清空隊列
void clearLinkQueue(LinkQueue *linkQueue) {while (linkQueue->front) { // 循環釋放隊列中所有節點的內存QueuePtr temp = linkQueue->front;linkQueue->front = linkQueue->front->next;free(temp);}linkQueue->rear = NULL; // 將 rear 指針置空
}
// 判斷隊列是否為空
Status isLinkQueueEmpty(LinkQueue *linkQueue) {return linkQueue->front == NULL; // 如果隊頭指針為空，則隊列為空
}
// 計算隊列長度
int getLinkQueueLength(LinkQueue *linkQueue) {int length = 0;QueuePtr p = linkQueue->front->next; // 從隊頭指針開始while (p != NULL) { // 遍歷隊列length++;p = p->next;}return length;
}
// 獲取隊列頭結點
Status getLinkQueueFront(LinkQueue *linkQueue, QElemType *element) {if (linkQueue->front == NULL) { // 隊列為空return 0;}*element = linkQueue->front->next->data; // 將隊頭節點的數據存儲到 element 中return 1;
}
// 遍歷隊列
// 遍歷隊列（忽略頭結點）
void traverseLinkQueueIgnoreHead(LinkQueue *linkQueue) {if (linkQueue->front == NULL || linkQueue->front->next == NULL) { // 隊列為空或只有頭結點printf("隊列為空\n");return;}QueuePtr current = linkQueue->front->next; // 從頭結點的下一個節點開始遍歷while (current != NULL) { // 遍歷直到隊尾printf("%d\t", current->data); // 打印當前節點的數據current = current->next; // 移動到下一個節點}printf("\n");
}// 入隊列
Status enLinkQueue(LinkQueue * linkQueue,QElemType element){QueuePtr newNode = (QNode *)malloc(sizeof(QNode));//生成一個新節點if (!newNode) {return 0;}newNode->data = element;newNode->next = NULL;linkQueue->rear->next = newNode;linkQueue->rear = newNode;return 1;
}
// 出隊列
Status deLinkQueue(LinkQueue * linkQueue,QElemType *element){if (linkQueue->front == linkQueue->rear) {//空隊列return 0;}QueuePtr p = linkQueue->front->next;// 指向頭結點* element = p->data;linkQueue->front->next = p->next;//修改頭指針if (linkQueue->front == p) {//如果僅有一個節點linkQueue->rear = linkQueue->front;//修改尾指針}free(p);return 1;
}void testLinkQueue(void){LinkQueue queue;if (initLinkQueue(&queue)) {printf("鏈隊列初始化成功！\n");}else {printf("鏈隊列初始化失敗！\n");}if (isLinkQueueEmpty(&queue)) {printf("隊列為空\n");}printf("隊列長度:%d\n",getLinkQueueLength(&queue));for (int i = 1; i <= 10 ; i++) {if (enLinkQueue(&queue, i)) {printf("數據元素%d入隊成功!\n",i);}else{printf("入隊失敗!\n");}}printf("遍歷鏈隊列初！\n");if (!isLinkQueueEmpty(&queue)) {printf("隊列不為空\n");}QElemType headFront;if (getLinkQueueFront(&queue, &headFront)) {printf("隊列頭結點獲取成功,隊頭元素為:%d\n",headFront);}traverseLinkQueueIgnoreHead(&queue);printf("隊列長度:%d\n",getLinkQueueLength(&queue));printf("隊列長度:%d\n",getLinkQueueLength(&queue));for (int i = 1; i <= 10 ; i++) {int element;if (deLinkQueue(&queue, &element)) {printf("出隊列成功,出隊列的數據元為素%d!\n",element);}else{printf("入隊失敗!\n");}}destroyLinkQueue(&queue);
}