【応用情報】キューとスタックの違いと逆ポーランド表記法について解説

この記事ではキューとスタックと逆ポーランド表記法についてIT初心者にも分かりやすく解説します。

応用情報ではキューとスタックと逆ポーランド表記法に関する問題が出ます。是非最後までご覧ください。

キューとスタック

キューは入力されたデータを入力された順番で処理していく方式のデータ構造で、
スタックは最後に入力されたデータから順番に処理していく方式のデータ構造です。

スタックにデータを入れることをプッシュ、データを取り出すことをポップと呼びます。

キューは、入力したデータをその順番で処理して欲しい時に使います。
例えば、印刷をしたとき、待ち時間が発生することがありますが、印刷を依頼した順番に印刷を実行されないと困りますね。

一方で、スタックは、プログラムの処理の順番を管理する時などに使います。
例えば、メインルーチンからサブルーチン①を呼び出し、さらにサブルーチン①からサブルーチン②を呼び出す場合、サブルーチン②の処理が終わったらサブルーチン①に戻り、サブルーチン①の処理が終わったらメインルーチンに戻ります。このように、サブルーチンの処理が終わった後、どこに戻るべきなのか分かるのは、スタックでデータを管理しているからです。

他にスタックを使っているものの例に逆ポーランド表記法があります。

逆ポーランド表記法

逆ポーランド表記法とは、演算記号を項の後ろに置く表記法です。
演算記号とは+－×÷()などの記号で、項とは数字のことです。
ちなみに、私たちが普段使う式の表し方は中置記法と呼びます。

中置記法から逆ポーランド表記法に変換するには、中置記法のときに計算する順番で「項の後ろに演算記号を置く」というルールに従って変形します。
一度変換した箇所は項と見なして変形していきます。

逆に、逆ポーランド表記法から中置記法に変換するときにスタックを使います。
逆ポーランド表記法で書かれた式を前から次の通りに処理していきます。
①項の場合はプッシュします。
②演算記号の場合は2つポップして、演算した結果をプッシュします。

中置記法の場合、どこから計算するのかを考えないといけないため、処理効率が落ちてしまいます。しかし、逆ポーランド表記法を使うと、前から処理していくだけで計算出来てしまうので、コンピュータが処理しやすいのです。

応用情報技術者試験での出題例

令和6年度秋期問3

令和5年度秋期問3