佇列
- 前言
- 1、佇列的概念
- 2、佇列的實作方式
- 3、佇列的基本操作
- 頭檔案
- 1. 初始化佇列
- 2. 隊尾入佇列
- 3. 隊頭出佇列
- 4. 獲取佇列頭部元素
- 5. 獲取佇列隊尾元素
- 6. 獲取佇列有效個數
- 7. 判斷佇列為空
- 8. 銷毀佇列
- 4、佇列面試題（結合堆疊）
- 5、佇列和堆疊的區別
| 目錄 | 目錄 |
|---|---|
| 順序表 | 單鏈表（不帶附加頭結點） |
| 雙鏈表（帶附加頭結點） | 堆疊（順序表實作） |
| 佇列（鏈式，不帶附加頭結點） |
前言
這一節我們來學習佇列，以及佇列和堆疊的區別，
1、佇列的概念
- 佇列是另一種限定存取位置的線性表，只允許在隊尾（rear）插入，隊頭(front)洗掉，（可以理解為排隊打飯）
2、佇列的實作方式
- 佇列可以用陣列和鏈表來實作，但相對于佇列鏈表更優，鏈表實作頭刪和尾插不需要移動元素，陣列是需要移動元素的，效率比較低，
3、佇列的基本操作
頭檔案
#pragma once // 防止頭檔案重復包含
#include<stdio.h>
#include<assert.h> // 斷言檢查
#include<stdlib.h> // 動態記憶體函式頭檔案
#include<stdbool.h> // bool頭檔案
typedef int QDataType; // 給int重命名為QDataType
// 鏈式結構：表示佇列
typedef struct QListNode
{
struct QListNode* next; // 指標域
QDataType data; // 資料域
}QNode;
// 佇列的結構
typedef struct Queue
{
QNode* front; // 結構體隊頭指標
QNode* rear; // 結構體隊尾指標
}Queue;
1. 初始化佇列
- front 和 rear都等于NULL，表示空佇列，即初始化佇列
void QueueInit(Queue* q)
{
assert(q);
q->front = q->rear = NULL;
}
2. 隊尾入佇列
分兩種情況判斷
- 佇列為空，新結點就插入在隊頭和隊尾上
- 佇列不為空，新結點直接插入在原隊尾成為新的隊尾
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));// 創建新結點
if (newnode == NULL) // 檢查是否開辟成功
{
perror("Push"); // 報錯資訊
exit(-1);
}
newnode->data = data; // 給新結點賦值
newnode->next = NULL; // 新結點變隊尾，其指標域置空
if (q->rear == NULL)// 佇列為空的時候
{
q->front = q->rear = newnode; // 隊頭和隊尾都等于新結點
}
else
{
q->rear->next = newnode; // 原隊尾指向新隊尾（新結點）
q->rear = newnode; // 新結點變為隊尾結點
}
}
3. 隊頭出佇列
分兩種情況判斷
- 佇列只有一個結點的時候，直接將隊頭洗掉，然后 front 和 rear 置空
- 佇列多個結點的時候，需要先重命名第二個結點，然后再去洗掉隊頭
void QueuePop(Queue* q)
{
assert(q); // 斷言檢查
assert(!QueueEmpty(q)); // 檢查是否非空，有元素才可以洗掉
if (q->front->next == NULL) // 只有一個結點時
{
free(q->front); // 釋放，防止記憶體泄漏
q->front = q->rear = NULL; // 隊頭隊尾置空
}
else
{
QNode* next = q->front->next; // 重命名第二個結點
free(q->front); // 釋放，防止記憶體泄漏
q->front = next; // 讓第二個結點成為隊頭
}
}
4. 獲取佇列頭部元素
- 先檢查是否非空，在獲取隊頭元素即可
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q)); // 檢查是否非空
return q->front->data; // 回傳隊頭元素
}
5. 獲取佇列隊尾元素
- 先檢查是否非空，在獲取隊尾元素即可
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q)); // 檢查是否非空
return q->rear->data; // 回傳隊尾元素
}
6. 獲取佇列有效個數
- 定義隊頭元素，迭代進行遍歷即可
int QueueSize(Queue* q)
{
assert(q); // 斷言檢查
int len = 0;
QNode* cur = q->front; // 隊頭元素重命名
while (cur)
{
len++;
cur = cur->next; // 迭代
}
return len; // 回傳個數
}
7. 判斷佇列為空
- 檢測佇列是否為空，如果為慷訓傳非零，非慷訓傳0
int QueueEmpty(Queue* q)
{
assert(q); // 斷言檢查
return q->front == NULL && q->rear == NULL;
// front和rear都為空，佇列才空
}
8. 銷毀佇列
- 隊頭元素重命名，迭代一層一層洗掉即可
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front; // 隊頭元素重命名
while (cur)
{
QNode* next = cur->next; // 下一個結點，進行迭代
free(cur); // 釋放記憶體，防止記憶體泄漏
cur = next; // 迭代
}
q->front = q->rear = NULL; // 釋放完隊頭和隊尾需要置空
}
4、佇列面試題（結合堆疊）
學了佇列，結合佇列和堆疊，可以做一下下面的面試題來加深自己的理解
- 設計回圈佇列
- 用佇列實作堆疊
- 用堆疊設計佇列
5、佇列和堆疊的區別
- 佇列先進先出，堆疊后進先出
- 佇列是在兩端隊尾插入，隊頭洗掉，而堆疊只能在一端（堆疊頂）插入和洗掉
原始碼地址：佇列原始碼
ps：制作不易，記得三連
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/293966.html
標籤：其他