キューとスタック

研

トラックバックより

毎回追加した値が先頭に来るまでローテーションする。意外と簡単。

キューでスタック - llaの日記

じつは、コンピュータのもっとも基本的な三種類の記憶モデル（キュー、スタック、テープ）の相互のシミュレーションとその計算量についての論文があるのね。

  1. ひとつのキューでスタックをシミュレートできる。
  2. ふたつのスタックでテープをシミュレートできる。
  3. ゆえに、ふたつのキューでテープをシミュレートできる。

という三段論法がFIFOLでbrainfuckインタプリタを書く重要なポイント。FIFOLでBrainfuckインタプリタ実装するとき、このアイディアにたどり着くのに当時3日間考えつづけた。その数週間後にこの論文を見つけて、計算量の裏付けができた。

ちなみに、キューひとつだけでもチューリング完全な機械を作ることが可能。