課題2(5/2出題)

課題

ヒント

Exercise 2.1では，addAllの対象として「Collection c」と書いていますが， C++言語では扱いにくいので，たとえば，MyArrayStack<T>にaddAllするのは， 同じ　MyArrayStack<T> 型のものに限定することをお勧めします．

Exercise 2.1に関しては，ArrayStackを拡張したMyArrayStackの「効率の悪い」 実装例MyArrayStack.hとそれを使うプログラムex2_1.cppを公開します． 

g++-5 -o ex2_1 ex2_1.cpp
で試すことができます(array.h, utils.h が展開されているディレクトリに置くことを想定しています)． 
as[0]=0
as[1]=1
as[2]=2
as[3]=3
...
as[48]=48
as[49]=49
as[50]=1000
as[51]=999
...
as[148]=902
as[149]=901
as[150]=50
as[151]=51
..
as[198]=98
as[199]=99
のような結果が得られるはずです．

プログラミングの課題は， MyArrayStack.hのaddAllを置き換えることで，クリアできるはずです．領域が足りない場合に現在の resize をそのまま呼び出しても，元のMyArrayStackのサイズ n に対して n * 2 のサイズしか確保できないので注意が必要です．加えようとする MyArrayStack のサイズが m だとすると n + m の領域が必要ですが，n * 2 >= n + m という保証はありません．別のresize を用意するか，resize の呼び出しの前にn を変更するresize相当のことをaddAll中に書く必要があります(resizeの呼び出しの前にnを変更する方法ではうまくいかないようです)．

Exercise 2.2は，ArrayStack.h を使った「効率の悪い」実装例SlowRandomQueue.h，効率が良いがランダムではないMyRandomQueue.h，およびそれを使うプログラムex2_2.cppを公開します． 
g++-5 -Wall -O3 -o ex2_2 ex2_2.cpp
SlowRandomQueue.hでは，取り出し removeの際に，ArrayStackの途中の要素のremoveを呼び出しているため，コピーのためのコストがかかります．RandomQueueでは，要素のインデックスを指定してアクセスすることがないので， 順番はaddした順番になっている必要がないことに注意すれば，コピーを最小限におさえることができます．それを考えて，MyRandomQueue.h を書き換えると課題の条件を満たすプログラムを作成できます．

Exercise 2.3は，DualArrayDequeの考え方を拡張します．ArrayStackを2つで Dequeを効率的に実現できるわけですが，ArrayDequeを2つ使うとどうなるでしょうか? ArrayStackを2つ使う時は，1回balanceを呼び出すと，O(n)のコストがかかったのですが，ArrayDeque ではfrontとbackの差が2になった時にbalanceを呼び出すようにするとO(1)のコストで実現できます．

提出方法

作成したすべてのプログラムと，各プログラムに関する簡単な説明をまとめた プレインテキスト形式(テキストエディタで編集可能な形式)またはPDF形式の ファイルを1つ作成して，ITC-LMSの「課題2(5/2出題)」(5/2の講義時間中に公開される予定)に提出してください．

締切は，5/14(日) 23:59．締切を過ぎても2017年7月末までは6割を上限に採点する．

オプション課題

課題だけで物足りない人は，以下のオプション課題にも取り組んでください．