Used)スタック(=要素をアクセスした時系列順に並べておくようなデータ構造)をいかに効率よく実現するかという問題について取り組んでいる。スタックを配列で実現し、アクセスが起こる毎にその要素を先頭に移動するような素朴なアルゴリズムだと、毎回の移動コストが非常に大きくなる。この点に注目したBarrigaとAyaniは、配列のインデックスに関して昇順または降順にアクセスされている間は要素の移動を行わず、その昇(降)順性がくずれたときにまとめて移動を行う方法を発表した。アクセスがインデックスに関して不規則にくるような場合には、この方法は全く役に立たない。そこで我々はアクセスが不規則であったとしてもある時点までは移動を行わず、リンク情報により時系列順を記録しておき、要素の探索コストがある限界を越えて大きくなったときに初めて再構築するような実現方法を考案した。この方法のもとで、残りn個のリクエストがあるときの期待コストによる動的計画問題として定式化した。その際要素に対するリクエストがすべてのインデックスに関して一様に分布していると仮定した場合(第3章)、およびスタックの先頭が最もアクセス確率が高いような準幾何分布に従っていると仮定した場合(第4章)について調べた。それぞれの場合で配列の最大アクセスインデックスrをパラメータとした期待コストの上下限を算出し、残りnステップで再構築したときと再構築しないとさの期待コストを比較して、再構築が最適となるrの値を求めた。これによれば特に一様分布の場合はスタックの全要素数の5/7を越えたときに再構築するのが最適であることが分かった。インデックスrあるいは残りステップ数nが増加したとき、一度最適な時点を越えると再び非最適とはならないような単調性が存在することが分かった。