課題2(4/28出題)

課題

ヒント

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

Exercise 2.1に関しては，ArrayStackを拡張したMyArrayStackの「効率の悪い」 実装例MyArrayStack.h, MyArrayStack.cppとそれを使うプログラムex2_1.cppを公開します． プログラミングの課題は， MyArrayStack.hのaddAllを置き換えることで，クリアできるはずです．

Exercise 2.2は，ArrayStack.h を使って， 
T ArrayStack::remove() {
  i = rand() % n;
  return remove(i);
}
とすれば良さそうですが，途中の要素のremoveはコピーのためのコストがかかります．RandomQueueでは，要素のインデックスを指定してアクセスすることがないので， 順番はaddした順番になっている必要がないことに注意すれば，コピーを最小限におさえることができます．
Exercise 2.3は，DualArrayDequeの考え方を拡張します．ArrayStackを2つで Dequeを効率的に実現できるわけですが，ArrayDequeを2つ使うとどうなるでしょうか?

提出方法

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

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

オプション課題

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