システム開発

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

お茶ん太
お茶ん太

この記事では、キュー・スタックと逆ポーランド表記法について、初心者にも分かりやすく図解付きで丁寧に解説しています!

キューとスタック

  • キューとは入力されたデータを入力された順番で処理する方式のデータ構造
  • スタックとは最後に入力されたデータから順番に処理する方式のデータ構造

逆ポーランド表記法

  • 逆ポーランド表記法とは項の後ろに演算記号を書く表記法
  • 普段の式を逆ポーランド表記法に変換するには、計算する順番で「項の後ろに演算記号を置く」というルールに従って変形する
  • 逆ポーランド表記法を普段の式に変換するには、前から順に①項の場合はプッシュ、②演算記号の場合は2つポップして演算結果をプッシュする

キューとスタック

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

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

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

一方で、スタックは、Excelやブラウザの戻るボタンで使う履歴管理に使います。ブラウザで戻るボタンを押して表示されるページは、一番最後に見ていたページですよね。他にスタックを使っているものの例に逆ポーランド表記法があります。

逆ポーランド表記法

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

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

逆に、逆ポーランド表記法から中置記法に変換するときにスタックを使います。逆ポーランド表記法で書かれた式を前から次の通りに処理していきます。

  1. 項の場合はプッシュします。
  2. 演算記号の場合は2つポップして、演算した結果をプッシュします。

先程の「AB-CD+E÷×」を中置記法に変換してみましょう。

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

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

令和6年度秋期問3

応用情報技術者
午前試験 
令和6年度秋期問3

式A+B×Cの逆ポーランド表記法による表現として,適切なものはどれか。

ア +×CBA   イ ×+ABC   ウ ABC×+   エ CBA+×

正解と解説

正解は”ウ”

まず計算するのは、B×Cなので、BC×に変換します。→ A+BC×
BC×は項と見なすので、ABC×+に変換出来ます。
よって、答えはウです。

令和5年度秋期問3

応用情報技術者
午前試験 
令和5年度秋期問3

逆ポーランド表記法(後置記法)で表現されている式ABCD-×+において,A=16,B=8,C=4,D=2のときの演算結果はどれか。逆ポーランド表記法による式AB+は,中置記法による式A+Bと同一である。

ア 32     イ 46     ウ 48     エ 94

正解と解説

正解は”ア”

ABCD-×+:Aは項なのでプッシュします。
【A】

BCD-×+:Bは項なのでプッシュします。
【A,B】

CD-×+:Cは項なのでプッシュします。
【A,B,C】

D-×+:Dは項なのでプッシュします。
【A,B,C,D】

×+:-は演算記号なので2つポップして演算結果をプッシュします。
【A,B,(C-D)】

×+:×は演算記号なので2つポップして演算結果をプッシュします。
【A,(B×(C-D))】

+:+は演算記号なので2つポップして演算結果をプッシュします。
【A+(B×(C-D))】

よって、16+(8×(4-2))=32となります。