練習問題５

次のルールを持つ Random Queue を考える。

• insertとremoveの２つの操作を持つ
• removeを呼ぶと、これまでにinsertした要素からランダムな１つを削除して、その要素を返す

1. 配列を用いて、insertとremoveがO(1)時間で完了する実装を示しなさい
2. リンクリストを用いて、insertとremoveをできる限り効率的に実装し、その計算量を分析しなさい