スタックと線形リストの操作

スタックは、後から入れたデータほど先に取り出す後入れ先出し（LIFO）の構造であり、線形リストは要素を一列に並べ、各要素が次の要素を指す構造である。両者はデータの一時的な保持や処理順序の管理に用いられ、配列とポインタのどちらで実現するかによって操作の性質が変わる。ここでは、スタックの出力順序、逆ポーランド表記法による式の評価、リストの実現方式と末尾操作の順に整理する。

スタックの基本操作と出力順序

スタックでは挿入（push）と取出し（pop）が同じ端で行われるため、入力順と出力順は一致するとは限らない。A、B、Cの順に入力されるデータについて、挿入と取出しを1回ずつ組み合わせて得られる出力順序は5通りである。 入力順を保ったまま全順列を数えると6通りになるが、スタックを経由すると実現できない順序が生じるため、6通りとはならない。

この種の問題では、挿入と取出しの操作列を書き出し、どの出力順序が実現可能かを一つずつ確認するのが基本である。たとえばCを先に出し、その後にAを出すような順序は、Bを先に取り出さなければAに到達できないため実現できない。

逆ポーランド表記法の評価

逆ポーランド表記法（後置記法）は、演算子を被演算子の後ろに置く表記法であり、括弧を使わずに演算の順序を一意に表せる。式A＋B×Cを後置記法で表すと、ABC×＋となり、BとCを掛けた結果にAを加えるという元の式の演算順序と一致する。 演算子を先頭に置く表記や被演算子の順序を入れ替えた表記は、元の式と演算順序が一致しないことがある。また、演算子に対して必要な被演算子が揃っていない表記は評価できないため、表記の形式を確認する必要がある。

後置記法の評価では、被演算子を順にスタックへ積み、演算子が現れたらスタックの上から二つを取り出して計算し、その結果を再びスタックに積む。数値を代入した式ABCD－×＋を左から評価すると、結果は32となる。 この手順はコンパイラが式を機械的に処理する際の基本となる。