C語言超詳細講解佇列的實現及程式碼

2022-04-11 13:02:17

前言

佇列的概念

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

佇列和前文所學的棧還是有一定區別的，佇列明確指出先進先出。假如說一個佇列的入隊順序為A B C D，那麼出隊順序一定為A B C D，因為無論你是在A進去再出來，然後B進去再出來接著CD進去再出來或者類似的，都不會影響它最終的出隊順序A B C D。這點和棧還是有區別的，畢竟棧是後進先出。

佇列的結構

佇列的應用場景

佇列：

公平排隊
廣度優先遍歷 ……

棧：

解決括號匹配
逆波蘭表示式求解
遞迴改非遞迴 ……

佇列的實現

在實現之前，首先得考慮用哪種結構好，是用陣列結構還是鏈式結構呢？上文的棧我們使用的是陣列結構，難道佇列也要用嗎？
其實不然。應該使用鏈式結構。前文棧刪除資料不需要挪動資料，使用陣列結構即可滿足需求，而佇列在刪除資料時需要把後面的資料挪到前面，使用鏈式結構非常容易實現，只需改變節點指向即可，而陣列結構想要實現挪動資料則非常麻煩。綜上，使用鏈式結構是最優的。此外，單連結串列即可滿足需求，不需要使用其餘較為複雜的鏈式結構。

建立佇列結構

思路：

這裡要定義兩個結構體，除了要定義1個鏈式結構來記錄各個節點外，還要定義一個結構來記錄隊頭和隊尾。以此方便後續的隊尾入資料，隊頭出資料。

Queue.h 檔案：

//建立佇列結構
typedef int QDataType; //方便後續更改儲存資料型別，本文以int為例
 //建立佇列節點
typedef struct QueueNode
{
	QDataType data; //儲存資料
	struct QueueNode* next; //記錄下一個節點
}QNode;
 //儲存隊頭和隊尾
typedef struct Queue
{
	QNode* head; //頭指標
	QNode* tail; //尾指標
}Queue;

佇列初始化

思路：

佇列可以為空，但是管理頭指標和尾指標的結構體不能為空，所以一開始就要斷言。其次，在插入資料前，佇列肯定是空的，所以直接把頭指標和尾指標置空即可。

Queue.h 檔案：

//初始化佇列
void QueueInit(Queue* pq);

Queue.c 檔案：

//初始化佇列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

佇列銷燬

思路：

銷燬佇列就是把佇列的每個資料都銷燬掉，那麼需要遍歷連結串列進行挨個銷燬free。首先定義一個cur指標為pq->head，用來儲存第一個資料，遍歷cur，如果不為空，就free。最後把tail和head置空即可。

Queue.h 檔案：

//銷燬佇列
void QueueDestory(Queue* pq);

Queue.c 檔案：

//銷燬佇列
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

入佇列

思路：

入佇列其實很簡單，只需要尾插即可，首先要新建立一個節點來儲存新插入的資料。但是在尾插之前要考慮如果一開始佇列沒有資料，為空，那麼只需要把head和tail節點指向新節點newnode節點即可。相反的，如果一開始就有資料，那麼只需正常尾插把tail的next指向新節點newnode，再把newnode賦給tail即可。

Queue.h 檔案：

//入佇列
void QueuePush(Queue* pq, QDataType x);

Queue.c 檔案：

//入佇列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//建立一個新節點儲存資料
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//暴力檢測newnode，因為malloc的都要檢測
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一開始沒有資料，為空的情況
	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

出佇列

思路：

特殊情況：

這裡在刪除資料時，首先要考慮特殊情況，當刪到只剩一個資料時，再刪一次，此時資料是沒了，不過head為空了，而tail變成野指標了，為了避免此現象的產生，單獨討論並置空head和tail即可。

一般情況：

此時只需要定義一個next指標儲存head的下一個節點，將head移動到next即可，並把舊的head置空。

Queue.h 檔案：

//出佇列
void QueuePop(Queue* pq);

Queue.c 檔案：

//出佇列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail); //tail和head均不能為空
	//特殊：當刪到head=tail的位置時
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情況
	else
	{
		//儲存head的下一個節點
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

佇列判空

思路：

如果head為空或者tail為空都是判空的條件，直接返回即可。

Queue.h 檔案：

//判空
bool QueueEmpty(Queue* pq);

Queue.c 檔案：

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

獲取佇列元素個數

思路：

求元素個數其實不難，只需要定義一個cur指標為第一個資料pq->head，定義變數size來記錄個數。依次遍歷cur，不為空，size就++。這種遍歷的思想不復雜，但時間複雜度達到O(N)，不是太好，想要O(1)的話可以直接在當初定義結構體時多定義一個size變數，專門用來記錄有效元素個數，每次入佇列size++，出佇列size--。這樣實現是比較好的，不過為了封裝成一個獨立模組，還是採用遍歷的方式。如下：

Queue.h 檔案：

//獲取有效元素個數
size_t QueueSize(Queue* pq);

Queue.c 檔案：

//獲取有效元素個數
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

獲取佇列頭部元素

思路：

首先要斷言頭部不能為空，如果頭部都為空了，那還怎麼能獲得頭部元素，其次直接返回頭部head的資料即可。

Queue.h 檔案：

//獲取隊頭元素
QDataType QueueFront(Queue* pq);

Queue.c 檔案：

//獲取隊頭元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head); //頭部不能為空
	return pq->head->data;
}

獲取佇列尾部元素

思路：

有了獲取隊頭元素的經驗，隊尾就更簡單了，把head換位tail即可，結構與上文一樣。

Queue.h 檔案：

//獲取隊尾元素
QDataType QueueBack(Queue* pq);

Queue.c 檔案：

//獲取隊尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail); //尾部不能為空
	return pq->tail->data;
}

總程式碼

Queue.h 檔案

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
//建立佇列結構
typedef int QDataType; //方便後續更改儲存資料型別，本文以int為例
 //建立佇列節點
typedef struct QueueNode
{
	QDataType data; //儲存資料
	struct QueueNode* next; //記錄下一個節點
}QNode;
 //儲存隊頭和隊尾
typedef struct Queue
{
	QNode* head; //頭指標
	QNode* tail; //尾指標
}Queue;
 
//初始化佇列
void QueueInit(Queue* pq);
 
//銷燬佇列
void QueueDestory(Queue* pq);
 
//入佇列
void QueuePush(Queue* pq, QDataType x);
 
//出佇列
void QueuePop(Queue* pq);
 
//判空
bool QueueEmpty(Queue* pq);
 
//獲取有效元素個數
size_t QueueSize(Queue* pq);
 
//獲取隊頭元素
QDataType QueueFront(Queue* pq);
 
//獲取隊尾元素
QDataType QueueBack(Queue* pq);

Queue.c 檔案

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
 
//初始化佇列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
 
//銷燬佇列
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
 
//入佇列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//建立一個新節點儲存資料
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//暴力檢測newnode，因為malloc的都要檢測
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一開始沒有資料，為空的情況
	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
 
//出佇列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail); //tail和head均不能為空
	//特殊：當刪到head=tail的位置時
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情況
	else
	{
		//儲存head的下一個節點
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
 
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
 
//獲取有效元素個數
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
 
//獲取隊頭元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head); //頭部不能為空
	return pq->head->data;
}
 
//獲取隊尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail); //尾部不能為空
	return pq->tail->data;
}

Test.c 檔案

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	//插入資料
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	//列印
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("n");
}
int main()
{
	TestQueue();
	return 0;
}

到此這篇關於C語言超詳細講解佇列的實現及程式碼的文章就介紹到這了,更多相關C語言佇列的實現內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！