1.2 スタックとキュー
今回は、スタック(stack)とキュー(queue)について纏める。
なお、今回使用する画像は、http://www.akita-nct.ac.jp/yamamoto/lecture/2005/2E/test_4/html/node2.html から引用している。こちらのページに、スタックとキューについてより詳しい内容が載っている。
スタック・キューは、単にデータ構造を表しているに過ぎない。
スタックとは、上のような画像で表されるデータ構造で、後に入れたデータから取り出されていく仕組みを持っている。ゲームの箱を上に積んでいき、上から順に消化していく、というのがスタックの分かりやすいたとえではないだろうか。スタックにデータを突っ込むことをpushと言い、データを取り出す(最近pushされたデータに限る)ことをpopという。
キューとは、上のような画像で表されるデータ構造で、スタックとは対照的に、先に入れたデータから取り出されていく仕組みを持っている。キューにデータを突っ込むことを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を使っていないが、これは今回組んだコードを汎用探索パッケージに流用する予定がある為である。
単純なデータ構造であるスタックに対して、キューはやや複雑な構造をしている。格納されているデータ数と、キューの占有メモリは正比例の関係に無いのである。
そこで、以下のような構造が考えられる。
今回は静的宣言の為、このような逃げ道を用意したが、動的宣言の場合はもっと話が単純になる。取り出したデータのメモリをその都度解放してやれば良いだけである。この点に関しては、動的宣言の場合スタックとほとんど仕組みが変わらない為、ある意味楽なのかもしれない。
//キュー #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つのデータ構造は深さ優先探索と幅優先探索に密接に関係する。前者がスタック、後者がキューに関係しているのである。この点に関しては、探索の話に入った時により詳しく纏める。
データ構造を簡潔に理解しておくことで、厄介な探索アルゴリズムが非常にスッキリ理解できる。
しかし、今回の私の最終到達目標はそこではない。スタックもキューも、実は最終的には使用する予定が無い。まぁ、教養として知っておくべきことだろうということで、とりあえずこれを使って基本探索アルゴリズムは組む予定だが。