佇列
筆記+原始碼自取：
🍭筆記：佇列筆記
🍭原始碼：佇列原始碼
文章目錄
- 佇列
- 一、為什么要學習佇列
- 二、佇列的介面
- 1. 佇列初始化
- 2. 進隊
- 3. 出隊
- 4. 銷毀佇列
- 5. 列印佇列中元素個數
- 6. 找到隊頭或隊尾資料
一、為什么要學習佇列
在排隊系統中，顧客去拿自己號碼順序，先拿到的一定先被叫號，
這種先進先出FIFO(First In First Out)的模式被稱為佇列
佇列顧名思義，排隊，按順序進入，按順序出去
🍎只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表
進行插入操作的一端稱為隊尾，進行洗掉操作的一端稱為隊頭
二、佇列的介面
在這種線性表的型別，可以是定義陣列來實作，也可以定義鏈表來實作，
二者如何抉擇？
因為涉及到元素移動，顯然陣列會很麻煩，而鏈表就很簡單，只需要指標移動就行
所以下面介面以鏈表實作佇列
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
這樣佇列的定義還不能結束，代表一個佇列，我們可能需要一頭一尾，一個控制隊頭一個控制隊尾
但每次定義一個佇列的時候都要先定義兩個變數很麻煩
所以我們定義一個結構體變數，一個指標記錄隊頭，一個指標記錄隊尾
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
1. 佇列初始化
頭和尾都置空
//佇列初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
2. 進隊
🍬head為空鏈表：
🍬head不為空鏈表：
//進隊
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
🍇進隊測驗：
void testqueue1()
{
Queue q;
//初始化佇列
QueueInit(&q);
//進隊
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
}
🍬測驗結果可以看出，tail指標指在最后一個資料
3. 出隊
佇列的出隊一定是頭部先出隊
🍬出隊前先判斷佇列是否為空
//判斷佇列是否為空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return (pq->head == NULL);
}
//出隊
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next;
if (next == NULL)
{
pq->tail = NULL;
}
free(pq->head);
pq->head = next;
}
🍦測驗用例：
void testqueue1()
{
Queue q;
//初始化佇列
QueueInit(&q);
//進隊
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePop(&q);
}
🍦測驗結果：可以看出1先消失的
4. 銷毀佇列
一個標準的頭刪操作
但要注意刪到最后的時候的操作
🍞這個時候要把tail置空不然就是個 野指標🍞
//銷毀佇列
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while(cur != NULL)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->tail = NULL;
pq->head = NULL;
}
🍙測驗用例：
void testqueue1()
{
Queue q;
//初始化佇列
QueueInit(&q);
//進隊
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePop(&q);
QueueDestroy(&q);
}
🍙測驗結果：head和tail都為空了
5. 列印佇列中元素個數
//佇列中資料個數
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}
這個比較簡單，有手就行，
6. 找到隊頭或隊尾資料
二者相似，也是有手就行，
//取到隊頭的資料
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//取到隊尾的資料
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
🍙連帶著列印佇列中元素一起測驗：
void testqueue1()
{
Queue q;
//初始化佇列
QueueInit(&q);
//進隊
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePop(&q);
//QueueDestroy(&q);
printf("%d\n", QueueSize(&q));
printf("%d\n", QueueFront(&q));
printf("%d\n", QueueBack(&q));
}
🍙測驗結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/344243.html
標籤：其他