C++コンテナ-キュー

キューの紹介

キューは、FIFOコンテキスト(先進先出)で動作するためのコンテナアダプタで、コンテナの一端から要素を挿入し、他端から要素を抽出します.

キューはコンテナアダプタとして実装され、コンテナアダプタは特定のコンテナクラスをその下位コンテナクラスとしてカプセル化し、queueはその要素にアクセスするための特定のメンバー関数のセットを提供する.要素はキューの最後からキューに入り、キューの先頭からキューから出ます.

底部容器は、標準容器クラステンプレートの1つであってもよいし、他の専門的に設計された容器クラスであってもよい.この下位コンテナは、少なくとも以下の操作をサポートする必要があります:empty:キューが空sizeであるかどうかを検出します:キュー内の有効な要素の個数frontを返します:キューヘッダ要素の参照backを返します:キューテール要素の参照push_を返しますback:キューの末尾にキューpop_を挿入front:キューヘッダにキュー

を出る

標準コンテナクラスdequeおよびlistは、これらの要件を満たしている.デフォルトでは、queueインスタンス化にコンテナクラスが指定されていない場合は、標準コンテナdequeが使用されます.

キューの共通インタフェース関数宣言インタフェース説明queue()-空のキューを構築empty()-キューが空であるかどうかを検出し、trueを返します.そうでなければfalse size()を返します.キュー内の有効な要素の数front()を返します.キューヘッダ要素の参照back()を返します.キューヘッダ要素の参照push()を返します.キューヘッダ要素をキューpop()にキューヘッダ要素をキューから出します.

#include
#include
using namespace std;
void test()
{
	queue<int> q1;//  int      q1
	queue<vector<int>> q2;//    vector      
	q1.push(1);//  1  
	q1.push(2);//  2  
	vector<int> vec;
	q2.push(vec);//vec  
	int front = q1.front();//  q1     
	int end = q1,back();//  q1     
	size_t size = q1,size();//  q1     
	q1,empty();//  q1      
	q1.pop();//      
}
int main()
{
	test();
}

Queueのシミュレーション実装
queueのインタフェースにはヘッダ削除とテールプラグが存在するためvectorを用いたパッケージング効率が低すぎるためlistを用いてqueueの実装をシミュレートすることができる.

#include  
namespace Queue 
{    
	template<class T>    
	class queue    
	{   
	 public:        
	 	queue() 
	 	{}        
	 	void push(const T& x) {_c.push_back(x);}  
	 	      	
	 	void pop() {_c.pop_front();}      
	 	  
	 	T& back() {return _c.back();}     
	 	   
	 	const T& back()const {return _c.back();}   
	 	     
	 	T& front() {return _c.front();}        
	 	
	 	const T& front()const {return _c.front();}  
	 	      
	 	size_t size()const {return _c.size();}     
	 	   
	 	bool empty()const {return _c.empty();}  
	 	  	
	 private:        
	 	std::list<T> _c;    
	 }; 
}