目錄
隊列的概念及其結構
隊列的實現
數組隊列
鏈式隊列
隊列的常見接口的實現
主函數Test.c
頭文件&函數聲明Queue.h
頭文件
函數聲明
函數實現Queue.c
初始化QueueInit
創建節點Createnode?
空間釋放QueueDestroy
入隊列QueuePush
出隊列QueuePop
隊頭元素QueueFront
隊尾元素QueueBack
判斷隊列是否為空QueueEmpty
隊列元素個數QueueSize
鏈式隊列總代碼
隊列的概念及其結構
隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表。
隊列具有 先進先出 /后進后出 FIFO(First In First Out)
入隊列：進行插入操作的一端稱為 隊尾。
出隊列：進行刪除操作的一端稱為 隊頭。
隊列的實現
隊列的實現也有兩種方式。隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低
數組隊列
雖然數組也可以實現【隊列】，但是挪動數據的效率真的很低！！?
鏈式隊列
無論是【棧】還是【隊列】雙向鏈表都是通吃的。但是我們為了節省資源就是要用【單鏈表】去實現隊列。我們用【單鏈表】去實現【隊列】需要注意：
- 入隊列 == 尾插
- 出隊列 == 頭刪
- 需要ptail指針維護隊列最后一個元素
- 需要phead指針維護隊列最后一個元素
- 二級指針&一級指針
- 帶不帶哨兵位的頭節點都可（哨兵位的頭節點最后要釋放空間）
應用場景：辦理業務排隊打號機。因為【隊列】是絕對公平的。
隊列的常見接口的實現
- 入隊列和出隊列的順序都只有一種！！
- 傳二級指針/傳一級指針的情況
- 怎么去計算隊列元素個數?
- 怎么用其他方式替代傳二級指針?空間換時間的方式
- 鏈表都需要考慮?鏈表沒有元素?鏈表只有一個元素//兩種情況即對應指針的判斷情況
- 二級指針 == 頭節點 == 返回值 == 結構體包含兩個一級指針?
主函數Test.c
#include"Queue.h"
int main()
{Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);QueuePush(&pq, 77);QueuePush(&pq, 7);while (!QueueEmpty(&pq)){printf("隊頭元素：%d\n", QueueFront(&pq));//printf("隊尾元素：%d\n", QueueBack(&pq));QueuePop(&pq);}QueueDestroy(&pq);return 0;
}頭文件&函數聲明Queue.h
頭文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>函數聲明
- 創建節點
typedef int QDataType;
//創建隊列節點
typedef struct QueueNode
{QDataType val;struct QueueNode* next;//易錯?QNode*next
}QNode;- 創建維護隊列的指針
//兩個指針維護鏈表隊列
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;- 初始化
void QueueInit(Queue* pq);- 銷毀釋放空間
void QueueDestroy(Queue* pq);- 入隊列
void QueuePush(Queue* pq, QDataType x);- 出隊列
void QueuePop(Queue* pq);- 隊頭元素
QDataType QueueFront(Queue* pq);- 隊尾元素
QDataType QueueBack(Queue* pq);- 判斷隊列是否為空
bool QueueEmpty(Queue* pq);- 隊列元素個數
int QueueSzie(Queue* pq);函數實現Queue.c
初始化QueueInit
#include"Queue.h"
//不需要頭節點，初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}創建節點Createnode?
Queue* Createnode(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("fail malloc");return;}newnode->val = x;newnode->next = NULL;return newnode;
}空間釋放QueueDestroy
//空間釋放
void QueueDestroy(Queue* pq)
{assert(pq);while (pq->phead){Queue* cur = pq->phead;pq->phead = pq->phead->next;free(cur);cur = NULL;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}入隊列QueuePush
//Push元素
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//創建節點Queue* newnode = Createnode(pq,x);if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}出隊列QueuePop
- 刪到空的情況（phead/ptail野指針的情況）
- 刪到只剩一個節點的情況（ptail野指針的情況）
//Pop元素
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size > 0);//為NULL的判斷Queue* cur = pq->phead;pq->phead = pq->phead->next;free(cur);cur = NULL;//為一個節點的判斷if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}隊頭元素QueueFront
//隊頭元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->size > 0);return pq->phead->val;
}隊尾元素QueueBack
//隊尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->size > 0);return pq->ptail->val;
}判斷隊列是否為空QueueEmpty
//判斷是否為NULL
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}隊列元素個數QueueSize
//隊員元素個數
int QueueSzie(Queue* pq)
{assert(pq);return pq->size;
}鏈式隊列總代碼
//Test.c
#include"Queue.h"
int main()
{Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);QueuePush(&pq, 77);QueuePush(&pq, 7);while (!QueueEmpty(&pq)){printf("隊頭元素：%d\n", QueueFront(&pq));//printf("隊尾元素：%d\n", QueueBack(&pq));QueuePop(&pq);}QueueDestroy(&pq);return 0;
}
//Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;
//創建隊列節點
typedef struct QueueNode
{QDataType val;struct QueueNode* next;//易錯?QNode*next
}QNode;
//兩個指針維護鏈表隊列
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//接口的實現
void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//空間釋放
void QueuePush(Queue* pq, QDataType x);//放元素到隊列尾
void QueuePop(Queue* pq);//出元素到隊頭
QDataType QueueFront(Queue* pq);//隊列頭的元素
QDataType QueueBack(Queue* pq);//隊列尾的元素
bool QueueEmpty(Queue* pq);//判斷隊列是否是否為NULL
int QueueSzie(Queue* pq);//隊列里面的元素個數
//Queue.c
#include"Queue.h"
//不需要頭節點，初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}Queue* Createnode(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("fail malloc");return;}newnode->val = x;newnode->next = NULL;return newnode;
}
//Push元素
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//創建節點Queue* newnode = Createnode(pq,x);if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//Pop元素
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size > 0);//為NULL的判斷Queue* cur = pq->phead;pq->phead = pq->phead->next;free(cur);cur = NULL;//為一個節點的判斷if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}//隊頭元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->size > 0);return pq->phead->val;
}//隊尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->size > 0);return pq->ptail->val;
}//判斷是否為NULL
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//隊員元素個數
int QueueSzie(Queue* pq)
{assert(pq);return pq->size;
}//空間釋放
void QueueDestroy(Queue* pq)
{assert(pq);while (pq->phead){Queue* cur = pq->phead;pq->phead = pq->phead->next;free(cur);cur = NULL;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
?????最后，感謝大家的閱讀，若有錯誤和不足，歡迎指正！下篇博文會分享一些【棧和隊列的OJ題目】&【循環隊列】各位小伙伴乖乖敲代碼哦。?
代碼---------→【唐棣棣 (TSQXG) - Gitee.com】
聯系---------→【郵箱：2784139418@qq.com】
