一、什么是佇列？

佇列的概念及結構：佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out)
入佇列：進行插入操作的一端稱為隊尾
出佇列：進行洗掉操作的一端稱為對頭

佇列在生活中的應用也非常廣泛，例如我們平時買東西付款，先排隊的就先付款，后排隊的就后付款（不允許插隊），又比如去醫院掛號，先去掛號的有個掛號單（比如21號），后面的人去掛號，掛號單就從22號開始，以此類推

二、佇列的實作

1.每個模塊的功能

在堆疊的實作當中我們采用了順序表的結構來實作如果還不知道什么是堆疊的朋友們，請點擊——》資料結構——堆疊的實作
了解了堆疊是用順序表實作后，我們先思考一個問題：佇列能用順序表實作嗎？答案當然是能了，不過太麻煩了，因為我們知道佇列有著先進先出的特點，當入了4個資料之后想要出佇列，隊頭該怎么辦，
假設我們將隊頭向前一個，前面就剩下一個空間用不到，如果想要利用前面的空間，就需要挪動資料，這樣一來每次出隊時都需要挪動資料，十分耗費時間，這么做是非常不明智的選擇，如下面的圖中所示：

為了解決上述所說的問題，我們將采用單鏈表的結構來實作佇列（雙向鏈表也可以），

先來看一下佇列的示意圖:

代碼如下（示例）：

//佇列中存盤的資料型別為進行重命名
//為什么要重命名？
//因為如果以后想將存盤資料的內容改為char或者double等其他型別的話，只需在這里該一次就可以，
//而不必代碼中的每一處都改，減少了不必要的麻煩，提高了代碼的可讀性
typedef int QDataType;
typedef struct QListNode//每個結點都由型別為QDataType（int）的變數和型別為struct QListNode*的指標（用于指向下一個結點）組成
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 佇列的結構 
typedef struct Queue//我們將用兩個指標來代表佇列的頭和尾，并將其封裝為另一個結構體
{
	QNode* front;//頭指標
	QNode* rear;//尾指標
}Queue;

// 初始化佇列 
void QueueInit(Queue* q);
// 隊尾入佇列 
void QueuePush(Queue* q, QDataType data);
// 隊頭出佇列 
void QueuePop(Queue* q);
// 獲取佇列頭部元素 
QDataType QueueFront(Queue* q);
// 獲取佇列隊尾元素 
QDataType QueueBack(Queue* q);
// 獲取佇列中有效元素個數 
int QueueSize(Queue* q);
// 檢測佇列是否為空，如果為慷訓傳非零結果，如果非慷訓傳0 
bool QueueEmpty(Queue* q);
// 銷毀佇列 
void QueueDestroy(Queue* q);

2.功能的實作

代碼如下（示例）：

// 初始化佇列 
void QueueInit(Queue* q)
	{
		assert(q);//以下的每個模塊都會使用這個斷言來判斷q是否為空，不為空才能進行下一步操作
		q->front = q->rear = NULL;
	}
// 隊尾入佇列 
	void QueuePush(Queue* q, QDataType data)
	{
		assert(q);
		QNode* newnode = (QNode*)malloc(sizeof(QNode));//每次入隊都需要開辟新的結點
		if (newnode == NULL)//如果開辟失敗，就給出提示資訊，并例外終止程式
		{
			printf("malloc fail\n");
			exit(-1);
		}
		newnode->data = data;//開辟成功，將此結點賦值
		newnode->next = NULL;//因為此時這個結點就是隊尾，所以next指標要指向NULL
		if (q->rear == NULL)//rear為NULL，front也必然為NULL,說明是入佇列的第一個元素
		{
			q->front = q->rear = newnode;//因為是第一元素，所以對頭和隊尾都是它
		}
		else
		{
			q->rear->next = newnode;
			q->rear = newnode;//newnode做新的隊尾
		}
	}
// 隊頭出佇列 
	void QueuePop(Queue* q)
	{
		assert(q);
		assert(!QueueEmpty(q));//斷言佇列是否為空，為空就直接報錯，下面獲取隊頭和隊尾的資料也這么操作
		QNode* next = q->front->next;//保存對頭的下一個結點的指標，防止將對頭釋放后，找不到下一個結點
		free(q->front);
		q->front = next;//下一個結點做新的隊頭
		if (q->front == NULL)//如果隊頭為NULL，則表示出佇列的資料是最后一個資料，此時隊頭和隊尾都要置為NULL
		{
			q->rear = NULL;
		}
	}
// 獲取佇列頭部元素 
	QDataType QueueFront(Queue* q)
	{
		assert(q);
		assert(!QueueEmpty(q));//
		return q->front->data;
	}
// 獲取佇列尾部元素 
	QDataType QueueBack(Queue* q)
	{
		assert(q);
		assert(!QueueEmpty(q));
		return q->rear->data;
	}
// 獲取佇列中有效元素個數 	
	int QueueSize(Queue* q)
	{
		assert(q);
		QNode* cur = q->front;
		int size = 0;
		while (cur != NULL)//遍歷整個佇列
		{
			size++;
			cur = cur->next;
		}
		return size;
	}
// 檢測佇列是否為空，如果為慷訓傳非零結果，如果非慷訓傳0 
	bool QueueEmpty(Queue* q)
	{
		assert(q);
		return q->front == NULL;
	}
// 銷毀佇列 
	void QueueDestroy(Queue* q)
	{
		assert(q);
		QNode* cur = q->front;
		while (cur != NULL)
		{
			QNode* next = cur->next;//在釋放當前結點時先保存下一個結點，否則將無法找到下一個結點
			free(cur);
			cur = next;
		}
		q->front = q->rear = NULL;//佇列釋放完后，將隊頭和隊尾都置為NULL，防止誤操作(對已經釋放空間進行解參考操作)
	}

3.測驗程式

代碼如下（示例）：

void test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	printf("%d\n", QueueFront(&q));
	printf("%d\n", QueueBack(&q));
	QueuePop(&q);
	printf("%d\n", QueueSize(&q));
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);
}
int main()
{
	test();

	return 0;
}

測驗：

畫圖分析：

總結

在佇列的實作當中，我們考慮到了用順序表實作佇列的不便利性，所以采用了單向鏈表的結構實作的佇列，在實作佇列的程序中，有入佇列，出佇列等8個模塊，在入佇列時，我們需要考慮是否是第一個資料這種情況，同樣的在出佇列時，我們也要考慮出的是否是最后一個元素，如果我們沒有正確的解決這些細節問題，可能就會導致程式的崩潰，如果在以后做大型專案里，這些細節導致的后果，往往是巨大的，