スタック、キュー、逆ポーランド記法
──┐ push ──┐ ┌─→ pop
│ │ │
: │↓ │ │↓ ││
├────┤ ├────┤ ┌────┐
11│データ5│ 0│データ5│ 0│データ1│
├────┤ ├────┤ ├────┤
12│データ4│ 1│データ4│ 1│データ2│
├────┤ ├────┤ ├────┤
13│データ3│ 2│データ3│ 2│データ3│
├────┤ ├────┤ ├────┤
14│データ2│ 3│データ2│ 3│データ4│
├────┤ ├────┤ ├────┤
15│データ1│ 4│データ1│ 4│データ5│
├────┤ ├────┤ ├────┤
: │ ││ :│ │ :│↑ ││
│ │ │
└─→ push ──┘ └─→ pop
キュー スタック スタック
FIFO LIFO (Javascriptでのイメージ)
配列の特殊な構造に、キューとスタックがあります。
キューは、FIFO(First In First Out:先入れ先出し)方式で、待ち行列ともいいます。プリンタへのスプールによる出力処理やデータを入力された順番通りに処理するときなどに用いられます。
それに対して、スタックは、LIFO(Last In First Out:後入れ先出し)方式です。新しいデータを入れる(Push)と、それまでのデータが下に押し下げられ、取り出すとき(Pop)ときは、1番上のデータが取り出され、2番目以降のデータが上に押し上げられます。
Javascriptでは、データの入る配列名を「スタック」とすれば、push, popは、
スタック.push(データ); スタック.pop();
の形式で記述します。
しかし、Javascriptでは、配列の末尾にpushし、末尾要素をpopする仕様になっているので、後入れ先出しであることは同じですが、むしろ上右図のようなイメージになります。
適宜、push, popを行ってください(clearはスタックを空にする操作 stack = []; です)。
コンピュータでは、スタックが広い分野で用いられています。
逆ポーランド記法の数式を与えて数学記法に変換します。変数は英字1文字とします。
・数学記法で( )が煩雑についていますが、プログラムを単純にしたからです。
・下記のkと例題の番号が逆になっている理由は、上述「スタックの実験」を参照してください。