C++ 佇列！還是要從 STL 中的說起……

1. 前言

佇列和棧一樣，都是受限的資料結構。

佇列遵循先進先出的儲存原則，類似於一根水管，水從一端進入，再從另一端出去。進入的一端稱為隊尾，出去的一端稱為隊頭。

佇列有 2 個常規操作：

入隊：進入佇列，資料總是從隊尾進入佇列。
出隊：從佇列中取出資料，資料總是從隊頭出來。

本文將先從STL的佇列說起，然後講解如何自定義佇列。

2. STL 中的佇列

STL的佇列有：

queue(普通佇列)。
priority_queue(優先佇列)。
deque（雙端佇列）。

2.1 `queue（普通佇列）`

queue是一個介面卡物件，是對deque元件進行改造後的偽產品，可以在原始碼中看出端倪。

template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue{
    //……
}

構建queue時需要 2 個型別引數：

_Tp：儲存型別說明。
_Sequence：真正的底層儲存元件，預設是deque。使用時，開發者可以根據需要指定其它的儲存元件。

queue 類中提供了幾個常規操作方法：

方法名	功能說明
`back()`	返回最後一個元素
`empty()`	如果佇列空則返回真
`front()`	返回第一個元素
`pop()`	刪除第一個元素
`push()`	在末尾加入一個元素
`size()`	返回佇列中元素的個數

操作範例：

#include <iostream>
#include <queue>
using namespace std;
int main(int argc, char** argv) {
	//建立並初始化佇列
	queue<int> myQueue;
	//向佇列新增資料
	for(int i=0; i<5; i++) {
		myQueue.push(i);
	}
	cout<<"檢視隊尾的資料"<<myQueue.back()<<endl;
	cout<<"看佇列的第一個資料"<<myQueue.front()<<endl;
	//獲取到佇列的大小
	int size=myQueue.size();
	//所有資料出佇列
	for(int i=0; i<size; i++) {
		cout<<myQueue.front()<<endl;
		myQueue.pop();
	}
	cout<<"列是否為空:"<<myQueue.empty()<<endl;
	return 0;
}

輸出結果：

在上述建立queue時也可以指定list作為底層儲存元件。

queue<int,list<int> > myQueue;

改變底層依賴元件，對業務層面的實現不會產生任何影響，這也是介面卡設計模式的優點。

2.2 Priority Queues

從優先佇列中刪除資料時，並不一定是按先進先出的原則，而是遵循優先順序法則，優先順序高的資料先出佇列，與資料的儲存順序無關。類似於現實生活中的VIP客戶一樣。

優先佇列的常規方法：

方法	功能說明
`empty()`	如果優先佇列為空，則返回真
`pop()`	刪除第一個元素
`push()`	加入一個元素
`size()`	返回優先佇列中擁有的元素的個數
`top()`	返回優先佇列中有最高優先順序的元素

建立並初始化優先佇列：

使用之前，先查閱 priority_queue的原始碼。

template<typename _Tp, typename _Sequence = vector<_Tp>,typename _Compare  = less<typename _Sequence::value_type> >
class priority_queue
{
//……
}

從原始碼可知，優先佇列屬於容器介面卡元件，本身並不提供具體的儲存方案，使用時，需要指定一個容器物件用於底層儲存(預設是 vector容器)。除此之外，還需要一個能對資料進行優先順序判定的物件。

當儲存的資料是基本型別時，可以使用內建的函數物件進行比較。

//升序佇列
priority_queue <int,vector<int>,greater<int> > q;
//降序佇列
priority_queue <int,vector<int>,less<int> > q_;

greater和less是內建的兩個函數物件。

如果是對自定義型別進行比較，則需要提供自定義的比較演演算法，可以通過如下的 2 種方式提供：

lambda函數。

auto cmp = [](pair<int, int> left, pair<int, int> right) -> bool { return left.second > right.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)>  pri_que(cmp);

自定義函數物件。要求函數物件中重寫operator()函數，如此，物件便能如函數一樣使用。

struct com_{
	bool operator()(const pair<int, int>& left, const pair<int, int>& right) {
		return left.second > right.second;
}};
priority_queue<pair<int,int>,vector<pair<int, int>>,com_> pri_que2;

操作範例：

範例功能要求：使用優先佇列儲存運運算元，獲取運運算元時，按運運算元的優先順序出隊。

#include <iostream>
#include <queue>
using namespace std;
//運運算元物件
struct Opt {
	//運運算元名
	char name;
	//運運算元的優先順序
	int jb;
	void desc() {
		cout<<name<<":"<<jb<<endl;
	}
};
//函數物件，提供優先順序佇列的比較法則
struct com {
	bool operator()(const Opt& opt1, const Opt& opt2) {
		return opt1.jb<opt2.jb;
	}
};
int main(int argc, char** argv) {
	priority_queue<Opt ,vector<Opt>,com> opt_que;
	//新增運運算元
	Opt opt= {'+',1} ;
	opt_que.push(opt);
	opt= {'*',2} ;
	opt_que.push(opt);
	opt= {'(',3} ;
	opt_que.push(opt);
	opt= {')',0} ;
	opt_que.push(opt);
	//出佇列
	int size= opt_que.size();
	for(int i=0; i<size; i++) {
		Opt tmp=opt_que.top();
		opt_que.pop();
		tmp.desc();
	}
	cout<<"佇列是否為空:"<<opt_que.empty()<<endl;
	return 0;
}

輸出結果：

2.3 deque

前面的queue物件本質是在deque的基礎上進行重新適配之後的元件，除此之外，STL中的stack也是……

deque也稱為雙端佇列，在兩端都能進行資料的新增、刪除。可以認為deque是一個伸縮性很強大的基礎功能元件，對其進行某些功能的遮蔽或新增，便能產生新元件。

deque的相關方法如下：

push_back()：在隊尾新增資料。
pop_back()：資料從隊尾出佇列。
push_front()：在隊頭新增資料。
pop_front()：資料從隊頭出佇列。

如果只允許使用push_back()和pop_back()或push_front()和pop_front()方法，就可以模擬出棧的儲存效果。
類似的，如果禁用pop_back()和push_front()則可以模擬出普通佇列的儲存效果……

可能會問，為什麼選擇deque作為基礎元件，難道它有什麼先天性優勢嗎？

這個就需要從它的物理結構說起。

deque物理結構中的基本儲存單位稱為段，段是一個連續的可儲存 8 個資料的順序區域。一個deque物件由很多段組成，段與段在物理空間上並不相鄰，而是通過一箇中央控制段儲存其相應地址。

deque具有順序儲存的查詢效能優勢也具有鏈式儲存的插入、刪除方面的效能優勢。因為它在物理結構上完美地融合了順序儲存思想（區域性）和鏈式儲存思想（整體）。

在一個段上進行資料查詢是很快的，即使有插入和刪除操作也只會對本段的效能有影響，而不會拖累整體效能。

操作範例：

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main(int argc, char *argv[]) {
	int ary[5] = {1, 2, 3, 4, 5};
	//使用陣列初始化 vector
	vector<int> vec( &ary[0], &ary[4]+1 );
	//使用 vector 初始化雙端佇列
	deque<int> myDeque( vec.begin(), vec.end() );
	//隊頭插入資料
	myDeque.push_front( 0 );
	//隊尾插入資料
	myDeque.push_back( 6 );
	cout<<"檢視隊頭資料 : "<<myDeque.front()<<endl;
	cout<<"檢視隊尾資料: "<<myDeque.back()<<endl;
	//雙端佇列支援迭代器查詢
	deque<int>::iterator iter = myDeque.begin();
	while( iter != myDeque.end() ) {
		cout<<*(iter++)<<' ';
	}
	cout<<endl;
	//雙端佇列支援下標存取方式
	cout<<"a[3] = "<<myDeque[3] << endl;
	//支援迭代器刪除
	myDeque.erase( myDeque.begin() );
	//刪除頭部刪除
	myDeque.pop_front();
	// 刪除尾部元素
	myDeque.pop_back();
	cout<<"檢視隊頭資料: "<<myDeque.front()<<endl;
	cout<<"檢視隊尾資料: "<<myDeque.back()<<endl;
	return 0;
}

執行後輸出結果：

3. 自定義佇列

佇列有 2 種實現方案：

順序實現，基於陣列的實現方案。
連結串列實現，基於連結串列的實現方案。

3.1 順序實現

順序實現底層使用陣列作為具體儲存容器。實現之初，需要建立一個固定大小的陣列。

3.1.1 思路

陣列是開發式的儲存容器，為了模擬佇列，可以通過 2 個指標用來限制資料的存和取：

front：指向隊頭的指標，用來獲取隊頭資料。總是指向最先新增的資料。
rear：指向隊尾的指標，用來在隊尾新增資料。

初始，front和rear指標可以指向同一位置，可以是下標為0位置。如下圖所示：

可以根據front和rear所指向位置是否相同，而判斷佇列是否為空。

如果 front==rear: 
     表示當前佇列是空的

入隊操作：

將資料儲存在rear所指向位置，再把rear向右邊移動一個位置（rear總是指向下一個可用的位置）。

當rear超出陣列的邊界，即下標為陣列的長度時，表示佇列已經滿了。

如果 rear==陣列長度
    表示佇列已經滿了

出隊操作：

出隊操作可以有 2 個方案。

front固定在下標為 0的位置，從佇列刪除一個資料後，後續資料向前移動一位，並把rear指標向左移動一位。如下圖是刪除資料1後的演示圖：

這種方案的弊端是，每刪除一個資料，需要後續資料整體向左移動，時間複雜度為O(n)，效能偏低。

從front位置處提取資料後，front指標向右邊移動。

以front位置為隊頭，而不是以陣列的絕對位置0為隊頭。這種方案的優勢很時顯，時間複雜度為O(1)。

但會出現假溢位的現象，如上圖示，刪除資料1後，留下了一個可用的空位置，因rear指標是向右移動的，並不知前面有空的位置，從而也無法使用此空位置。

針對於這種情況，可以讓rear指標在超過下標界限後，重頭再開始定位，這樣的佇列稱為迴圈佇列。

前文說過，當front和rear指標相同時，認定佇列為空。在迴圈佇列，當入隊的速度快於出隊速度時，rear指標是可以追上front指標的。如下圖所示：

這時佇列為滿負荷狀態。也就是說，front等於rear時佇列有可能是空的也有可能是滿的。

可以使用 2 種方案解決這個問題：

計數器方案。使用計數器記錄佇列中的實際資料個數。當num==0時佇列為空狀態，當num==size時佇列為滿狀態。
留白方案：儲存資料時，從rear+1位置開始，而不是儲存在rear位置。或者說下標為 0的位置空出來。

這樣，當rear+1等於front時，可判定佇列為滿狀態。

注意，在獲取隊頭資料時，需要先把front向右移一位。

3.1.2 編碼實現

迴圈佇列類（留白方案）：

class MyQueue {
	private:
		//陣列
		int *queue;
		int front;
		int rear;
		int size;
	public:
		//建構函式
		MyQueue(int queueSize=10):size(queueSize),front(0),rear(0) {
			this->queue=new int[queueSize];
		}
		//解構函式
		~ MyQueue() {
			delete[] queue;
		}
		//佇列是否為空
		bool isEmpty() {
			return this->front==this->rear;
		}
		//資料入佇列
		bool push_back(int data) {
			//需要判斷佇列是否有空位置
			if  (((this->rear+1)%this->size)!=this->front) {
				//獲取當前可儲存位置
				this->rear=(this->rear+1) % this->size;
				//儲存資料
				this->queue[this->rear]=data;
				return true;
			}
			return false;
		}

		//資料出佇列
		bool pop_front(int& data) {
			//佇列不能為空
			if (this->rear!=this->front) {
				//頭指標向右移動
				this->front=(this->front+1) % this->size;
				data=this->queue[this->front];
				return true;
			}
			return false;

		}
		//檢視隊頭資料
		bool get_front(int & data) {
			//佇列不能為空
			if (this->rear!=this->front) {
				//頭指標向右移動
				int idx=(this->front+1) % this->size;
				data=this->queue[idx];
				return true;
			}
			return false;
		}
};

測試佇列：

#include <iostream>
using namespace std;
int main(int argc, char *argv[]) {
	MyQueue myQueue(5);
	//向佇列中壓入 4 個資料,注意，有一個位置是空著的
	for(int i=0; i<5; i++) {
		myQueue.push_back(i);
	}
	int data;
	myQueue.get_front(data);
	cout<<"隊頭資料："<<data<<endl;
	//佇列已經滿，測試是否還能壓入資料
	int	data_=5;
	bool is= myQueue.push_back(data_);
	if(is)
		cout<<"壓入成功"<<endl;
	else
		cout<<"壓入失敗"<<endl;
	//把佇列中的所有資料刪除
	int tmp;
	for(int i=0; i<4; i++) {
		is= myQueue.pop_front(tmp);
		if(is)
			cout<<tmp<<endl;
	}
}

輸出結果：

3.2 鏈式實現

鏈式實現佇列時，資料可以從頭部插入然後從尾部刪除，或從尾部插入再從頭部刪除。本文使用尾部插入，頭部刪除方案。

連結串列實現時，需要頭指標也需要尾指標。初始，都為NULL。

鏈式實現的過程簡單清晰，就是在單連結串列上的資料新增和刪除操作，具體細節這裡就不再廢話，直接上程式碼：

鏈式實現的流程簡單清晰，這裡就不再廢話，直接上程式碼：

#include <iostream>
using namespace std;
//連結串列的結點型別
struct QueueNode {
	int data;
	QueueNode* next;
	QueueNode() {
		this->next=NULL;
	};
};
class MyQueue_ {
	private:
		//陣列
		QueueNode* front;
		QueueNode* rear;
	public:
		//建構函式
		MyQueue_() {
			this->front=NULL;
			this->rear=NULL;
		}
		//解構函式
		~ MyQueue_() {
			QueueNode* p, *q;
			p=front;
			while(p) {
				q=p;
				p=p->next;
				delete q;
			}
			front=NULL;
			rear=NULL;
		}
		//佇列是否為空
		bool isEmpty() {
			return this->front==NULL && this->rear==NULL;
		}
		//資料入佇列
		bool push_back(int data) {
			//新結點
			QueueNode* p=new QueueNode();
			if(p) {
				//申請結點成功
				p->data=data;
				if(rear) {
					rear->next=p;
					rear=p;
				} else
					front=rear=p;
				return true;
			} else
				return false;
		}
		//資料出佇列
		bool pop_front(int& data) {
			QueueNode* p;
			if(!isEmpty()) {   
                 //判斷佇列是否為空
				p=front;
				data=p->data;
				front=front->next;
				if(!front)
					rear=NULL;
				delete p;
				return true;
			}
			return false;
		}
		//檢視隊頭資料
		bool get_front(int & data) {
			if(!isEmpty()) {
				data=front->data;
				return true;
			} else
				return false;
		}
};

int main(int argc, char *argv[]) {
	MyQueue_ myQueue;
	//向佇列中壓入 4 個資料,注意，有一個位置是空著的
	for(int i=0; i<5; i++) {
		myQueue.push_back(i);
	}
	int data;
	myQueue.get_front(data);
	cout<<"隊頭資料："<<data<<endl;
	//佇列已經滿，測試是否還能壓入資料
	int	data_=5;
	bool is= myQueue.push_back(data_);
	if(is)
		cout<<"壓入成功"<<endl;
	else
		cout<<"壓入失敗"<<endl;
	//把佇列中的所有資料刪除
	int tmp;
	for(int i=0; i<4; i++) {
		is= myQueue.pop_front(tmp);
		if(is)
			cout<<tmp<<endl;
	}
}

輸出結果：

4. 總結

本文講解了STL中的佇列元件，以及如何通過順序表和連結串列模擬佇列。

本文同時被收錄到"程式設計驛站"公眾號。

C++ 佇列！還是要從 STL 中的說起……

1. 前言

2. STL 中的佇列

2.1 queue（普通佇列）

2.2 Priority Queues

2.3 deque

3. 自定義佇列

3.1 順序實現

3.1.1 思路

3.1.2 編碼實現

3.2 鏈式實現

4. 總結

2.1 `queue（普通佇列）`