隊列的概念及結(jié)構(gòu)

隊列是只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO(First In First Out) 的原則。

• 入隊列：進行插入操作的一端稱為隊尾。
• 出隊列：進行刪除操作的一端稱為隊頭。

隊列結(jié)構(gòu)聯(lián)想起來也非常簡單，如其名，隊列就相當于銀行辦理業(yè)務(wù)的柜臺前一條長長的隊伍，排在隊伍前面的人（隊頭）可以先辦理，而在隊伍最后面的人（隊尾）只能最后辦理，如果繼續(xù)有人來辦理業(yè)務(wù)就只能排在隊尾，這樣的模式就是隊列且遵循隊頭出隊列，隊尾入隊列的原則。結(jié)構(gòu)大致如下：

隊列的實現(xiàn)

隊列的實現(xiàn)同樣有兩種方式–數(shù)組隊列，鏈式隊列：

1. 數(shù)組隊列：
   如果用數(shù)組實現(xiàn)隊列：這樣隊頭就只能指向下標為0的位置，那么隊尾就指向隊列最后一個元素的后一個的下標，基于此結(jié)構(gòu)，想要出隊操作，時間復(fù)雜度就會升高為O(N)且十分不方便。因為每當要將下標為0的元素出隊，后面的所有元素就要前移并改變隊尾指向。大致如下：

還有一點就是，如果使用數(shù)組隊列，在前期有大量數(shù)據(jù)入隊列，動態(tài)開辟了很大的空間，到后期可能很多數(shù)據(jù)都出了隊列但動態(tài)開辟的空間并不能釋放，那就造成了嚴重的空間浪費。

2. 鏈式隊列：
   如果使用雙向鏈表： 這與棧為什么不用雙向鏈表實現(xiàn)一個道理，雖然可以實現(xiàn)，且入隊/出隊的時間復(fù)雜度都為O(1)但結(jié)構(gòu)較為復(fù)雜，實現(xiàn)起來并不是很實用；
   那么我們這時會選擇結(jié)構(gòu)更優(yōu)得單鏈表，雖說單鏈表尾插得時間復(fù)雜度是O(N)，但我們可以定義一個變量（QNode* ptail）來記錄單鏈表的尾節(jié)點，這樣每次入隊時便不用再遍歷單鏈表找尾節(jié)點，時間復(fù)雜度也降為O(1)。結(jié)構(gòu)如下：

這樣按需開辟空間，出隊列就釋放節(jié)點，進隊列新建節(jié)點，也大大減少了空間的浪費。我們便可如下定義隊列的每個節(jié)點：

typedef int QDataType;
//隊列節(jié)點
typedef struct QueueNode
{
    QDataType val;
    struct QueueNode* next;//鏈接下一個節(jié)點的指針
}QNode;

因為我們要記錄隊列的頭（QNode* phead）和尾（QNode* ptail）（下文稱這兩個指針為頭指針和尾指針），且基本每個函數(shù)都要用到這兩個變量，甚至一些函數(shù)還要修改這兩個變量對應(yīng)的值，那就不得不傳二級指針了，這也就大大增加了代碼的難度！為了解決這個問題，我們可以定義一個結(jié)構(gòu)體，并將這兩個變量放到結(jié)構(gòu)體中，每次函數(shù)調(diào)用時，只需傳這個結(jié)構(gòu)體地址即可；
為了方便統(tǒng)計隊列里面的節(jié)點數(shù)，我們通常還會定義一個整型變量size，有元素出隊列時size--，入隊列時size++。
此結(jié)構(gòu)體定義方式如下：

typedef struct Queue
{
    QNode* phead;
    QNode* ptail;
    int size;
}Queue;

初始化

初始時隊列中無節(jié)點，所以pq->size = 0，頭指針（pq->phead = NULL）尾指針（pq->ptail = NULL）都指向空。

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->size = 0;
	pq->phead = pq->ptail = NULL;
}

入隊

入隊操作首先要新建一個節(jié)點（類型為QNode），然后通過尾指針指向的節(jié)點鏈接此節(jié)點（pq->ptail->next = newnode），并更新尾指針的指向（pq->ptail = newnode），將記錄節(jié)點數(shù)的值加1（pq->size++）。
在鏈接時還要考慮到隊列為空的情況，此情況下直接將頭/尾指針指向新建的節(jié)點（pq->ptail = pq->phead = newnode）。

//入隊列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//新建節(jié)點
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush()::malloc");
		return;
	}
	//新建的節(jié)點初始化
	newnode->next = NULL;
	newnode->val = x;
	//判斷，鏈接
	if (pq->ptail == NULL)
	{
	    //1.原隊列無節(jié)點
		pq->ptail = pq->phead = newnode;
	}
	else
	{
	    //2.原隊列已有節(jié)點
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

出隊

出隊列操作首先要確保隊列有節(jié)點才能出隊，那么斷言一下就可（assert(pq->phead);）。需要注意的是出隊是頭刪，可以先定義變量記錄頭節(jié)點（QNode* del = pq->phead;），然后再將頭指針指向下一個節(jié)點（phead = phead->next;），最后將原頭節(jié)點釋放（free(del);），并將記錄節(jié)點數(shù)的值減1（pq->size--）。
當隊列只有一個節(jié)點時，刪除后隊尾和隊頭指針都應(yīng)該指向空，但上述操作并不能達到此效果，所以要單獨判斷一下，將尾指針指向空。

//出隊列
void QueuePop(Queue* pq)
{
	assert(pq);
	//隊列不為空
	assert(pq->phead);
	QNode* del = pq->phead;//記錄頭節(jié)點
	pq->phead = pq->phead->next;//頭指針重定向
	free(del);//釋放原頭節(jié)點
	del = NULL;
	//隊列是否被刪空判斷
	if (pq->phead == NULL)
		pq->ptail = NULL;
	pq->size--;
}

其他一些隊列函數(shù)

1. 隊列有效數(shù)據(jù)個數(shù)：
   上面也講過pq->size記錄的就是隊列的有效數(shù)據(jù)個數(shù)

//數(shù)據(jù)個數(shù)
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

2. 隊列是否為空：
   兩種判斷方法：1.當頭指針指向NULL，2.pq->size的值為0。

//隊列是否為空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
	//return pq->size == 0;
}

3. 返回隊頭數(shù)據(jù)：
   首先要判斷隊列不為空，然后返回頭指針指向的節(jié)點的val即可。

//返回隊頭數(shù)據(jù)
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

4. 返回隊尾數(shù)據(jù)：
   同上，首先要判斷隊列不為空，然后返回尾指針指向的節(jié)點的val即可。

//返回隊尾數(shù)據(jù)
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->ptail->val;
}

5. 釋放隊列空間：
   遍歷隊列直到頭指針指向空，每遍歷一次釋放一個節(jié)點，最后將頭/尾指針指空，pq->size置0。

//釋放
void QueueDetroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	//遍歷，釋放
	while (cur)
	{
	    //記錄下一個節(jié)點地址
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

小結(jié)

• 隊列是一種先進先出的結(jié)構(gòu)，與棧相反；
• 隊列是頭部刪除尾部插入，一般使用鏈表實現(xiàn)，且與棧結(jié)構(gòu)一樣不支持隨機訪問；
• 在實現(xiàn)隊列時一般定義兩個結(jié)構(gòu)體，一個結(jié)構(gòu)體用來記錄每個節(jié)點中所需要的值，另一個用來記錄隊列的隊頭，隊尾和節(jié)點數(shù)。第二個結(jié)構(gòu)體的使用避免了二級指針，且在函數(shù)調(diào)用時一般傳第二個結(jié)構(gòu)體的地址。

隊列相關(guān)題目

8. 下面關(guān)于棧和隊列的說法中錯誤的是（ A B ）
   A.隊列和棧通常都使用鏈表實現(xiàn)
   B.隊列和棧都只能從兩端插入、刪除數(shù)據(jù)
   C.隊列和棧都不支持隨機訪問和隨機插入
   D.隊列是“先入先出”，棧是“先入后出”

這題主要考察對隊列和棧的性質(zhì)的區(qū)分，思路如下：

• A錯誤：棧是尾部插入和刪除，一般使用順序表實現(xiàn)，隊列是頭部刪除尾部插入，一般使用鏈表實現(xiàn)

• B錯誤：棧是后進先出，尾部插入和刪除；隊列是先進先出，尾部插入頭部刪除

• C正確：棧只能訪問棧頂元素，不支持隨機訪問，隊列也不支持

• D正確：棧和隊列的特性

關(guān)于隊列還有一個知識點就是循環(huán)隊列，因其結(jié)構(gòu)復(fù)雜就單獨拿出來講。文章來源地址http://www.zghlxwxcb.cn/news/detail-753800.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)和算法】--隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！