課題2(5/10出題)

課題

教科書の2.7 Discussion and ExercisesのExcercise 2.1, 2.2, 2.3のうち， 1題以上を解きなさい(C++言語で動くプログラムを作成しなさい)
C++言語で回答する時は，回答に利用した環境も書くように．
教育用計算機システムのMac環境で回答する場合は， g++-5 を用いると良いでしょう．
一から実装するのではなく，配布プログラム ods-cpp.tgz に手を加えて回答することが前提になっています．

ヒント

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 が展開されているディレクトリに置くことを想定しています)．プログラミングの課題は， MyArrayStack.hのaddAllを置き換えることで，クリアできるはずです．

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つ使うとどうなるでしょうか?

提出方法

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

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

オプション課題

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

第2章の他の練習問題(Exercise 2.4 - 12)に取り組む