技術的なやつ

技術的なやつ

1.2 スタックとキュー

今回は、スタック(stack)とキュー(queue)について纏める。
なお、今回使用する画像は、http://www.akita-nct.ac.jp/yamamoto/lecture/2005/2E/test_4/html/node2.html から引用している。こちらのページに、スタックとキューについてより詳しい内容が載っている。

スタック・キューは、単にデータ構造を表しているに過ぎない。

f:id:ibako31:20130814011221p:plain
スタックとは、上のような画像で表されるデータ構造で、後に入れたデータから取り出されていく仕組みを持っている。ゲームの箱を上に積んでいき、上から順に消化していく、というのがスタックの分かりやすいたとえではないだろうか。スタックにデータを突っ込むことをpushと言い、データを取り出す(最近pushされたデータに限る)ことをpopという。

f:id:ibako31:20130814011658p:plain
キューとは、上のような画像で表されるデータ構造で、スタックとは対照的に、先に入れたデータから取り出されていく仕組みを持っている。キューにデータを突っ込むことをenqueueと言い、データを取り出すことをdequeueという。


というわけで、テンプレートを用いてまずはスタックを組んだ。

//スタック
#include <iostream>

#define MAX_STACK_SIZE 100

template <class d_type> class stack{
private:
	d_type data[MAX_STACK_SIZE];
	int data_num;
public:
	stack(); //コンストラクタ
	void clear(); //スタックの中身を空にする
	void push(d_type obj); //スタックにobjを追加する
	d_type pop(); //スタックからobjを取り出す
	void show(); //スタックの中身を見せる
	int get_data_num(){return data_num;}
};

template <class d_type> stack<d_type>::stack(){
	data_num = 0;
}

template <class d_type> void stack<d_type>::clear(){
	data_num = 0;
}

template <class d_type> void stack<d_type>::push(d_type obj){
	if(data_num+1 < MAX_STACK_SIZE){
		data[data_num] = obj;
		data_num++;
	}
	else{
		std::cout << "This stack is FULL! -- error in stack<d_type>::push" << std::endl;
	}
}

template <class d_type> d_type stack<d_type>::pop(){
	if(data_num>0){
		data_num--;
		return data[data_num];
	}
	else{
		std::cout << "This stack is EMPTY! -- error in stack<d_type>::pop" << std::endl;
	}
}

template <class d_type> void stack<d_type>::show(){
	for(int i=0; i<data_num; i++){
		std::cout << i << ":" << data[i] << std::endl;
	}
}

特に説明すべき点は無いと思う。
いずれ、dataは動的に宣言して可変長にするつもりだが、とりあえず今は静的に宣言しておく。
また、今回using namespaceを使っていないが、これは今回組んだコードを汎用探索パッケージに流用する予定がある為である。

単純なデータ構造であるスタックに対して、キューはやや複雑な構造をしている。格納されているデータ数と、キューの占有メモリは正比例の関係に無いのである。
そこで、以下のような構造が考えられる。
f:id:ibako31:20130814012341p:plain
今回は静的宣言の為、このような逃げ道を用意したが、動的宣言の場合はもっと話が単純になる。取り出したデータのメモリをその都度解放してやれば良いだけである。この点に関しては、動的宣言の場合スタックとほとんど仕組みが変わらない為、ある意味楽なのかもしれない。

//キュー
#include <iostream>

#define MAX_QUEUE_SIZE 100

template <class d_type> class queue{
private:
	d_type data[MAX_QUEUE_SIZE];
	int first_num; //最初のデータ格納番号
	int data_num;
public:
	queue(); //コンストラクタ
	void clear(); //キューの中身を空にする
	void enqueue(d_type obj); //キューにobjを追加する
	d_type dequeue(); //キューからobjを取り出す
	void show(); //キューの中身を見せる
	int get_data_num(){return data_num;}
	int get_first_num(){return get_first_num;}
};

template <class d_type> queue<d_type>::queue(){
	first_num = 0;
	data_num = 0;
}

template <class d_type> void queue<d_type>::clear(){
	first_num = 0;
	data_num = 0;
}

template <class d_type> void queue<d_type>::enqueue(d_type obj){
	if(data_num+1 < MAX_QUEUE_SIZE){
		data[(first_num+data_num)%MAX_QUEUE_SIZE] = obj;
		data_num++;
	}
	else{
		std::cout << "This queue is FULL! -- error in queue<d_type>::enqueue" << std::endl;
	}
}

template <class d_type> d_type queue<d_type>::dequeue(){
	if(data_num>0){
		data_num--;
		int value = first_num;
		first_num = (first_num + 1) % MAX_QUEUE_SIZE;
		return data[value];
	}
	else{
		std::cout << "This queue is EMPTY! -- error in queue<d_type>::pop" << std::endl;
	}
}

template <class d_type> void queue<d_type>::show(){
	for(int i=0; i<data_num; i++){
		std::cout << i << ":" << data[(first_num+i)%MAX_QUEUE_SIZE] << std::endl;
	}
}

さて、ここで「何故、スタックとキューの2種類のデータ構造を学ぶ必要があるか?」について、少しだけ書いておく。
実は、この2つのデータ構造は深さ優先探索幅優先探索に密接に関係する。前者がスタック、後者がキューに関係しているのである。この点に関しては、探索の話に入った時により詳しく纏める。
データ構造を簡潔に理解しておくことで、厄介な探索アルゴリズムが非常にスッキリ理解できる。

しかし、今回の私の最終到達目標はそこではない。スタックもキューも、実は最終的には使用する予定が無い。まぁ、教養として知っておくべきことだろうということで、とりあえずこれを使って基本探索アルゴリズムは組む予定だが。