前言：本章介紹的主要內容是資料結構中佇列的概念，并通過代碼實作鏈式結構的佇列，
文章目錄
- 1.佇列的基本概念
- 1.1 佇列的定義
- 1.2 佇列的特點
- 2.佇列的代碼實作
- 2.1 佇列存盤的說明
- 2.2 佇列的定義
- 2.3 佇列的初始化
- 2.4 佇列的判空操作
- 2.5 佇列的入隊操作
- 2.6 佇列的出隊操作
- 2.7 佇列的獲取隊首元素操作
- 2.8 佇列的獲取隊尾元素操作
- 2.9 佇列的計算佇列元素數量操作
- 2.10 佇列的銷毀操作
- 3.原始碼鏈接
1.佇列的基本概念
1.1 佇列的定義
只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出的特性
1.2 佇列的特點
- 佇列是一種操作受限的線性表
- 隊頭(首)：允許洗掉的一端
- 隊尾：允許插入的一端
- 空佇列：沒有元素的佇列
- 洗掉操作叫做
出隊,插入操作叫做入隊
2.佇列的代碼實作
| 程式名 | 功能 |
|---|---|
Queue.h | 函式宣告 |
Queue.c | 功能函式的定義 |
test.c | 測驗 |
2.1 佇列存盤的說明
front指標:指向隊頭元素
rear指標:指向隊尾元素的下一個位置
空隊時：rear == front
佇列初始化：rear = front = 0
入隊：隊未滿時，先送值到隊尾，再隊尾指標加一
出隊：隊為空時，先取隊頭元素，再隊頭指標加一
2.2 佇列的定義
這里選擇實作鏈表鏈式結構的佇列
- 鏈隊本質上是一個同時帶有隊頭指標、隊尾指標的單鏈表
- 頭指標指向隊頭結點
- 尾指標指向隊尾結點
- 鏈式佇列適合于資料元素變化較大的情形，不存在上溢
- 當使用多個佇列時，最好使用鏈式佇列，可以避免存盤分配不合理下的溢位問題，
typedef int QDataType;
typedef struct QueueNode //定義佇列結點
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue //定義佇列
{
QueueNode* head; //隊頭
QueueNode* tail; //隊尾
}Queue;
2.3 佇列的初始化
直接初始化為NULL.
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
2.4 佇列的判空操作
只要頭指標沒有指向任何空間就說明佇列為空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
2.5 佇列的入隊操作
因為咱們是鏈式結構，無需檢查佇列是否滿了，直接開辟一個新空間存盤資料，向新結點的資料域賦值，然后**
tail->next指向新結點**，
void QueuePush(Queue* pq, QDataType elem)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if(newnode == NULL)
{
perror("空間申請:");
exit(-1);
}
newnode->data = elem;
newnode->next = NULL;
//檢查佇列是否為空
pq->head == NULL ? (pq->tail = newnode ):(pq->tail->next = newnode,pq->tail = pq->tail->next);
}
2.6 佇列的出隊操作
1.先判斷是否是空隊,保存下一個結點
2.free釋放頭結點
3.指向所保存的下一個結點
（上述程序要小心出現佇列內元素全部清完，pq->tail變成野指標的情況）
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* next = NULL;
pq->head->next == NULL?
(free(pq->head),pq->head = pq->tail = NULL):
(next = pq->head->next, free(pq->head),pq->head = next);//避免野指標
}
2.7 佇列的獲取隊首元素操作
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq)); //不能為空
return pa->head->data;
}
2.8 佇列的獲取隊尾元素操作
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq)); //不能為空
return pa->tail->data;
}
2.9 佇列的計算佇列元素數量操作
直接遍歷計數
int QueueSize(Queue* pq)
{
assert(pq);
int num = 0;
QueueNode* cur = pq->head;
while(cur)
{
num++;
cur = cur->next;
}
return num;
}
2.10 佇列的銷毀操作
遍歷free，最后記得置空
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
3.原始碼鏈接
點擊跳轉原始碼倉庫
資料結構的佇列內容到此設計結束了，感謝您的閱讀！！！如果內容對你有幫助的話，記得給我點個贊——做個手有余香的人，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296581.html
標籤：其他
上一篇：C語言之遞回的應用