Web教材一覧ハードウェアとソフトウェア

スタックと逆ポーランド記法

キーワード

スタック、キュー、逆ポーランド記法


キューとスタック

       ──┐         Push ──┐  ┌─→ Pop
         │             │  │
      : │↓   │      : │↓  ││
        ├────┤        ├────┤
      11│データ5│      11│データ5│
        ├────┤        ├────┤
      12│データ4│      12│データ4│
        ├────┤        ├────┤
      13│データ3│      13│データ3│
        ├────┤        ├────┤
      14│データ2│      14│データ2│
        ├────┤        ├────┤
      15│データ1│      15│データ1│
        ├────┤        ├────┤
      : │   ││      : │    │
            │
            └─→
         キュー           スタック
         FIFO          LIFO

配列の特殊な構造に、キュースタックがあります。
 キューは、FIFO(First In First Out:先入れ先出し)方式で、待ち行列ともいいます。プリンタへのスプールによる出力処理やデータを入力された順番通りに処理するときなどに用いられます。
 それに対して、スタックは、LIFO(Last In First Out:後入れ先出し)方式です。新しいデータを入れる(Push)と、それまでのデータが下に押し下げられ、取り出すとき(Pop)ときは、1番上のデータが取り出され、2番目以降のデータが上に押し上げられます。

スタックの利用

コンピュータでは、スタックが広い分野で用いられています。

逆ポーランド記法との関係

逆ポーランド記法
数学の一般的な記法での数式 A+B×C を計算するには、発生順序により「(A+B)×C」とするのは誤りです。日本語では「AにBにCを×したものを+する」ことになりますが、その順に「ABC×+」と記述する記法を逆ポーランド記法といいます。
 もう少し複雑な例にして、数式を逆ポーランド記法にする手順を説明します。
  数式 A+B×(C+D)+E は、演算の優先順位を( )で明示すれば、
   ((A+(B×(C+D)))+E)
になります。
 最も深い( )から、数式を逆ポーランド記法に置き換えていきます。
   ((A+(B×(C+D)))+E)
          └─①─┘
           CD+
       └───②───┘
          BCD+×
    └─────③─────┘
         ABCD+×+
   └─────④─────────┘
         ABCD+×+E+

となり、逆ポーランド記法の
   ABCD+×+E+
になります。
 なお、これを木構造(演算木)を用いて表現することもできます。
練習問題
  問題1: (A+B)×(C-D) → AB+CD-×
  問題2: A/(B-C)+D  → ABC-/D+
スタックによる計算方法
数学での記法を逆ポーランド記法に変換すれば、スタックを利用して簡単に計算することができます。
そのルールは、次の通りです。
   逆ポーランド記法で記述した数式を左から順番に処理する。スタックは空である。
   数値ならば、スタックに Push する
   演算子ならば、
     スタックの1番上の数値を Pop して、その数値をXとする。
     新しくスタックの1番上にきた数値をYとして、YにXを演算する。
     その結果をYに代入する。
   数式がなくなったとき、スタックには唯一の数値が残っており、それが数式の結果である。
 このように、逆ポーランド記法では、+×や( )などの優先順位を考慮する必要がなく、式の解釈が簡単になり、スタック操作だけで行えるので、初期の電卓では逆ポーランド記法の順に入力するものもありました。また、コンパイラで数式を解釈するときにも利用されています。
例題
「ABC/-」を例にして説明します。
  Step1:Aを Push する。
  Step2:Bを Push する。
  Step3:Cを Push する。
  Step4:/になった。Cが Pop され、スタックの最上段がBになる。
    最上段の値を B/C の計算結果に置き換える。
  Step5:-になった。B/C が Pop され、スタックの最上段がAになる。
    最上段の値を A-(B/C) の計算結果に置き換える。
    数式がなくなったので、計算結果は A-(B/C) となる。
スタックの状況は、次のようになります。
    Step1  Step2  Step3  Step4   Step5
     A   B   C   /    -
   ┌───┬───┬───┬───┬──────┐
 1 │ A │ B │ C │B/C│A-(B/C)│
   └───┼───┼───┼───┼───┬──┘
 2     │ A │ B │ A │   └ 計算結果
       └───┼───┼───┘
 3         │ A │
           └───┘