初めまして。プログラムの練習で整数の循環queueを実装してみました。
独習C++という本を買ったので、その中の練習問題2.1の1.(サイズ100の整数の循環queueを実装せよ)を解いてみた次第です。
今回はテスト投稿ですので、今後どういう投稿をするのかわかりませんが、とりあえずマークダウン方式に慣れるためにも投稿してみます。なにぶんプログラムを始めたばかりの初心者ですので、至らぬ点も多々あると思いますが、宜しくお願いします。
早速classを定義してみます。
class queue{
static const int queue_size = 100+1; //isFullの都合で+1しないといけない
int Q[queue_size];
int head,tail;
public:
queue();
void enqueue(int x);
int dequeue();
bool isEmpty();
bool isFull();
};
ここで、
static const int queue_size = 100+1;
int Q[queue_size];
の部分を
const int queue_size = 100+1;
int Q[queue_size];
にすると、
Invalid use of non-static data member 'queue_size'
というエラーが出ました。とりあえずstaticを付ければいいんだなと思って、付けたらエラーは出なくなりました。仕組みはよくわかってません。どなたか教えていただけるとありがたいです。またサイズが100の整数の循環queueにするのですが、後述のisFull関数の実装の都合上、+1をする必要が出ました。後述します。
メンバ関数の中身を書いていきたいと思います。
queue::queue(){
head = 0;
tail = 0;
cout << "queueを生成しました。\n";
}
void queue::enqueue(int x){
if (isFull()) {
cout << "enqueue要求がありましたが、Qがいっぱいです\n";
return;
}
Q[tail] = x;
tail++;
tail %= queue_size;
}
int queue::dequeue(){
if (isEmpty()) {
cout << "dequeue要求がありましたが、Qが空っぽです\n";
return 0; //ここで何を返せばいいのだろう?
}
int result = Q[head];
head++;
head %= queue_size;
return result;
}
問題はdequeue関数です。queueが空っぽの時、何もせず終了したいのですが、関数の返り値がintのため、何かint型の値を返さなくてはいけません。苦し紛れに0を返すことにしていますが、何か良い解決方法があれば教えてください。
関数の中身の続きです。
bool queue::isEmpty(){
return head==tail;
}
bool queue::isFull(){ //headの後ろにtailが来た時(重なるひとつ手前)
return (tail+1)%queue_size==head;
}
isEmptyは単純にheadとtailが重なっている時ということにしました。isFullはtailがぐるりと回って、headのひとつ後ろに来た時(重なるひとつ手前)で判断することにしました。このせいで、サイズnのqueueを作ろうとすると、領域としてはn+1確保しないといけなくなりました。(headのひとつ後ろのポジションへはenqueueできない)これも、もっと綺麗な方法があれば教えていただきたいです。
main関数内で以下のコードを実行したところ以下の結果を得ました。
queue Q;
for (int i = 0; i < 100; i++) {
Q.enqueue(i);
}
Q.enqueue(100); //Qは一杯のはずなのでエラー文が出るはず。
for (int j = 0; j < 100; j++) {
Q.dequeue();
}
Q.dequeue(); //Qは空っぽのはずなのでエラー文が出るはず。
queueを生成しました。
enqueue要求がありましたが、Qがいっぱいです
dequeue要求がありましたが、Qが空っぽです
うまく動いているようです。いろいろ分からない点はありますが、なんとか実装できたようです。
また、何か実装したら投稿することにします。お読みいただいてありがとうございました。