課題2(5/7出題)

課題

ヒント

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

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

g++-8 -o ex2_1 ex2_1.cpp
で試すことができます(array.h, utils.h が展開されているディレクトリに置くことを想定しています)． 
as[0]=0
as[1]=1
...
as[8]=8
as[9]=9
as[10]=1000
as[11]=999
...
as[88]=922
as[89]=921
as[90]=10
as[91]=11
...
as[98]=18
as[99]=19
のような結果が得られるはずです．

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

サイズ1のxsをaddAllする操作を繰り返しても，addを繰り返した場合と比較してそれほど遅くならない(たかだか定数倍しか遅くならない)ということも，「efficient implementation」のためには必要な条件になります．「必ずresizeする」という実装の場合は，この点で問題となります．
Exercise 2.2は，ArrayStack.h を使った「効率の悪い」実装例SlowRandomQueue.h，効率が良いがランダムではないMyRandomQueue.h，およびそれを使うプログラムex2_2.cppを公開します． 
g++-8 -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/7出題)」(5/7の講義時間中に公開される予定)に提出してください．

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

オプション課題

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