前言

本文章均基于C語言實作，如有不足，歡迎指正
以下是本篇文章正文內容，下面案例可供參考

一、佇列的概念及其結構

1.定義

佇列(Queue)：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有 先進先出 FIFO (First In First Out) 的特性

2.術語

入隊：向佇列中插入元素的操作為 入隊
隊尾(Rear)：進行插入操作的一端稱為 隊尾

出隊：向佇列中洗掉元素的操作為 出隊
隊頭(Front)：進行洗掉操作的一端稱為 隊頭

3.實際應用

實際中，表示公平排隊的地方均可以用到 佇列
比如，銀行的 抽號機 、鍵盤輸入回圈緩沖區問題

二、佇列的實作

佇列也可以陣列和鏈表的結構實作，使用 鏈表 的結構實作更優一些，因為如果使用陣列的結構，出佇列在陣列頭上出資料，效率會比較低

1.佇列的基本操作

佇列的基本操作有如下幾點：
初始化佇列
隊尾入佇列
隊頭出佇列
獲取佇列頭部元素
獲取佇列隊尾元素
獲取佇列中有效元素個數
檢測佇列是否為空
銷毀佇列

2.代碼實作

注：以下代碼均以鏈表結構實作

2.1 創建佇列

下列將 QDataType 進行宏定義，表示該佇列 元素型別 ，方便將來新佇列元素型別的替換
Qnode 用以存盤 資料 和 下一結點
front 表示 隊頭
rear 表示 隊尾

代碼如下：

//進行宏定義
typedef QDataType int
// 鏈式結構：表示佇列 
typedef struct QListNode 
{ 
	struct QListNode* next; 
	QDataType data; 
}QNode; 
 
// 佇列的結構 
typedef struct Queue 
{ 
	QNode* front; 	//表示隊頭
	QNode* rear; 	//表示隊尾
}Queue;

2.2 初始化佇列

assert 用以判斷所傳指標是否為 NULL ,多運用 assert 有利于幫助快速查錯
如圖

void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
}

2.3 隊尾入佇列

由于此處佇列使用 鏈表 結構，因此尾插新的元素，需使用 malloc() 函式開辟新的空間，值得注意的是， malloc() 函式可能開辟失敗，回傳 NULL ，需注意該點，避免 野指標 的使用，
另外，如果 隊頭 為 NULL ,則須將隊頭也賦值為該結點

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode)
	{
		if (q->rear)
			q->rear->next = newnode;
		q->rear = newnode;
		newnode->next = NULL;
		newnode->data = data;
	}
	else
	{
		printf("malloc failed\n");
		exit(-1);
	}
	if (q->front == NULL)
		q->front = newnode;
}

2.4 隊頭出佇列

1.倘若該佇列為 空佇列 ，則無法出佇列
2.值得注意的是，倘若該 佇列 僅有一個元素，則 隊尾 須置為 NULL
原因：當 隊頭 釋放此處空間后，該地址便還給計算機，但 隊尾 依舊存盤該地址，后續對該地址進行操作，即為 野指標的非法訪問
3.下列代碼中 if() 陳述句 用以判斷該佇列是否僅有一個元素，若 p 為 NULL，則該佇列僅有一個元素

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QNode* p = q->front->next;
	if (p == NULL)
	{
		free(q->front);
		q->front = NULL;
		q->rear = NULL;
	}
	else
	{
		free(q->front);
		q->front = p;
	}
}

2.5 獲取佇列頭部元素

只需判斷是否為 空佇列 即可

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}

2.6 獲取佇列隊尾元素

只需判斷是否為 空佇列 即可

QDataType QueueRear(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}

2.7 獲取佇列中有效元素個數

不考慮效率，若非頻繁呼叫，即可創建 n 用以記錄元素個數
若頻繁呼叫，可在 Queue 中創建 size

int QueueSize(Queue* q)
{
	assert(q);
	int n = 0;
	QNode* cur = q->front;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

2.8 檢測佇列是否為空

這里會用到 bool ,不清楚的小伙伴可以用 int 代替
如果為慷訓傳非零結果，如果非慷訓傳0

bool QueueEmpty(Queue* q)
{
	assert(q);
	if (q->rear == NULL)
		return true;
	return false;
}

2.9 銷毀佇列

需創建臨時變數 p 保存下一個結點

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* p = cur->next;
		free(cur);
		cur = p;
	}
}

附上運行圖

三、佇列的經典問題-設計回圈佇列

題目鏈接： 設計回圈佇列（點擊即可跳轉）

1. 題目描述：

2. 解題思路：

我們設計頭尾兩個指陣來實作
假設規定 頭尾指標相同 ，則 佇列為 滿
但是，這樣又出現一個問題，當 佇列為 空 時， 頭尾指標也相同 ，無法判斷佇列狀態，如圖
因此，我們需要設計新方法，區分佇列是否為為 空 或為 滿
最簡單的方法就是， 額外多出一個空間
倘若指標 相同 ，則為 空
若頭尾指標 間隔為1 ，則為 滿 ，如圖

3. 代碼實作：

思路有了，就是代碼和細節問題了
由于是回圈佇列，則空間大小一定，此處無需使用鏈表結構
假設佇列有效元素個數為 K ,則開辟 K+1 個元素大小的空間
另外，在寫時想出來一個偷懶的寫法，分享給你們
注：以下代碼僅供參考，非最優解

typedef struct {
    int* queue;
    int front;
    int rear;
    int k;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int* p = (int*)malloc((k+1) * sizeof(int));
    q-> queue = p;
    q-> front = 0;
    q-> rear = 0;
    q-> k = k;
    return q;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    if(obj -> front == obj -> rear)
        return true;
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    if((obj -> rear + 1) % (obj -> k +1)== obj -> front)
        return true;
    return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    if((obj->rear+1)%(obj->k+1) == obj->front)
    {
        return false;
    }
    obj->queue [ obj -> rear] = value;
    obj ->rear = (obj -> rear + 1) % (obj -> k + 1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    if(obj -> front == obj -> rear)
    return false;
    obj ->front = (obj -> front + 1) % (obj -> k + 1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    	return -1;
    return *(obj ->queue + obj -> front);
}

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    return -1;
    return obj ->queue [(obj -> rear + obj -> k) % (obj -> k + 1)];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->queue);
    free(obj);
}
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

附上運行圖:

以上就是本次所帶來的全部內容，如有幫助，可以點贊支持一波哦~