アルゴリズムとデータ構造
演習第 3 回
スタックとキュー

この演習では、 スタック（アルゴリズムＣ 第１巻 p.29） の操作方法について学び、そのプログラムを作成します。 キュー（アルゴリズムＣ 第１巻 p.34） については触れませんが、スタックを作ることができれば、 キューを作るのもそれほど難しいことではありません。

(1) は 逆ポーランド記法（アルゴリズムＣ 第１巻 p.31） に変換する問題です。 逆ポーランド記法は他にも 「後置記法」 「RPN (Reverse Polish Notation)」 「IPN (Inverse Polish Notation)」 などと呼ばれます。逆ポーランド記法は日本語表記と似ています。 例えば、1 + 2 を逆ポーランド記法で表すと 1 2 + になります。これは日本語で 「1 と 2 を足す(+)」 と書いたときの語順と同じです。 逆ポーランド記法にすると括弧が不要になります。 人間様には読みにくいかもしれませんが、 コンピュータが処理をする場合にはとても都合が良い表記方法です。

(2) では、以下の図を参考にして書いてみてください。

実行例：
% ./a.out
Input data by Reverse Polish Notation: 12+34+*
1 
1 2 
3 
3 3 
3 3 4 
3 7 
21 
Answer: 21

スタックを配列で表現する場合、次の図のようになります。

処理の流れとしては、まず getchar() などの入力関数を使って 入力データを 1 文字読み込みます。そのデータが数字であれば、 整数型に変換してスタックにプッシュし、+-*/ などの 記号であれば、スタックから 2 回ポップして計算して、計算結果を またプッシュします。

スタックを作るには、以下のような関数が必要になります。

void push(int x);

スタックにデータ x をプッシュ（一番上に置く）する関数

int pop();

スタックからデータをポップ（一番上を取る）して、それを返す関数

int isempty();

スタックが空かどうかをチェックする関数。空なら 1、そうでないなら 0 を返す。

isempty() 関数は pop() 関数の中で使います。 ポップする前にスタックにデータが入っているかを調べる必要があるからです （空ならポップできない）。

まずはスタック操作のための関数を作成し、簡単なテストをしてみると良いでしょう。

int main(){
  push(1);
  push(2);
  printf("poped value is %d.\n", pop());
  printf("poped value is %d.\n", pop());
}

実行すると、このようになるのが正解です。

% ./a.out
poped value is 2.
poped value is 1.

また、次のような関数を作成すれば、プログラミングしやすくなるでしょう。

int dtoi(char c);

文字型としての数字を整数型に変換する関数 （例： '5' → 5）

void print_stack();

スタックの中身を表示する関数

実行例：
% ./a.out
Input data by Reverse Polish Notation: 12+34+*
1 
2 1 
3 
3 3 
4 3 3 
7 3 
21 
Answer: 21

問題２とは違い、リストを使ってスタックを表現します。

リストでのプッシュは、head の次にノードを挿入します。

リストでのポップは、head の次のノードを削除します。

また、リストを使うことによって、キューも同様に作ることができます。