10.2 stack データの抽象化

データの抽象化として、stack は、伝統的に、表 15 で定義されている演算を実装する任意のオブジェクトとして定義されています。

表 15 -- stack 演算

先頭の要素へのアクセスと削除は、それぞれ別の演算であることに注意してください。

stack データの抽象化を使用するプログラムには、stack ファイルをインクルードする必要があります。

# include <stack>

stack の宣言は、配下の要素型を指定する必要があります。また、要素を保持するコンテナを指定することもできます。stack のデフォルトコンテナは deque ですが、list や vector を使用することもできます。vector では一般的により小さく、deque ではわずかに速くなる場合があります。

以下に、stack の宣言例を示します。

stack<int> stackOne;                       //  deque を使用する stack
stack< double, deque<double> > stackTwo;
stack< Part *, list<Part * > > stackThree;
stack< Customer, list<Customer> > stackFour;

最後の例では、Customer という名前のユーザー定義の型から stack が作成されます。

---

注: 例に示すように、ほとんどのコンパイラでの stack の宣言で、2 つの右山括弧 (>) の間に空白文字を入れておくことが重要です。入れない場合は、右シフト演算子としてコンパイラに解釈されます。

---

stack の古典的な適用例は、この計算機の実装です。

---

注: このプログラムは calc.cpp ファイルにあります。

---

計算機への入力は、逆ポーランド表記法 (RPN) で書かれた式を表現するテキスト文字列で構成されます。整数定数と呼ばれるオペランド は、値の stack の上にプッシュされます。演算子が検出されると、適切な数のオペランドがスタックから引き出されて演算が実行され、結果がスタックに戻されます。

stack シミュレーションの開発は、計算機エンジンと計算機プログラムの 2 つの部分に分割することができます。計算機エンジンはシミュレーションに含まれる実際の作業に関係する部分で、入力や出力の演算は実行しません。この名前は、自動車のエンジンやコンピュータのプロセッサとの類似を示唆することを意図しています。このメカニズムが実際の作業を実行しますが、通常、ユーザーとメカニズムが直接対話することはありません。この周りを覆っているのが計算機プログラムで、ユーザーと対話し、適切な指示を計算機エンジンに渡します。

計算機エンジンには、次のクラス定義を使用することができます。計算機が受け入れることのできる各演算子を表わす値が列挙された list をクラス宣言内に定義します。単純にするために、すべてのオペランドは整数値であることと、2 項演算子だけが処理されることの 2 点を前提とします。

class calculatorEngine {
public:
   enum binaryOperator {plus, minus, times, divide};
   
   int currentMemory ()           // 現在の stack の一番上に返す
      { return data.top(); }
      
   void pushOperand (int value)   // stack にオペランド値をプッシュする
      { data.push (value); }
      
   void doOperator (binaryOperator);   // stack を引き出し、演算子を
                                       // 実行する
   
protected:
   stack< int > data;
};

メンバー関数 doOperator() が実際の作業を実行します。スタック² から値を引き出して演算を実行し、結果をスタックに戻します。

void calculatorEngine::doOperator (binaryOperator theOp)
{
   int right = data.top();   // 一番上の要素を読み取る
   data.pop();   // stack から引き出す
   int left = data.top();   // 次の要素を読み取る
   data.pop();   // stack から引き出す
   switch (theOp) {
      case plus: data.push(left + right); break;
      case minus: data.push(left - right); break;
      case times: data.push(left * right); break;
      case divide: data.push(left / right); break;
      }
}

メインプログラムが逆ポーランド表記法の値を読み取り、計算機エンジンを呼び出して実際の作業を行います。

void main() {
   int intval;
   calculatorEngine calc;
   char c;
   
   while (cin >> c)
      switch (c) {
         case '0': case '1': case '2': case '3': case '4':
         case '5': case '6': case '7': case '8': case '9':
            cin.putback(c);
            cin >> intval;
            calc.pushOperand(intval);
            break;
         
         case '+':  calc.doOperator(calculatorEngine::plus);
            break;
   
         case '-':  calc.doOperator(calculatorEngine::minus);
            break;
   
         case '*':  calc.doOperator(calculatorEngine::times);
            break;
   
         case '/':  calc.doOperator(calculatorEngine::divide);
            break;

         case 'p':  cout << calc.currentMemory() << endl;
            break;
   
         case 'q':  return; // プログラムを終了する
      }
}