①-2スタック

メモリの項で散々スタックの説明をしたがリストを使ったスタックの実装について説明する。
データ構造として最も重要なスタックだが、基本的な操作は２つだけで、プッシュとポップと言う概念からなる。プッシュはリストで言えば項目の挿入であり、ポップは項目の取出しである。
スタックを使った算術式を述べると
仮に
5*(((9+8)*(4*6)+7)と言う式
9+8をやってから4*6をやり続いて掛け算をしてから７を加え、最後に５を掛ける。
この手順をオペラントも含めて並べてみると

1. ５を入れる。
2. ９を入れる
3. ８を入れる
4. ９＋８の答えを入れる
5. ４を入れる
6. ６を入れる
7. ４＊６の答えを入れる
8. ９＋８の答えと４＊６の答えを掛けたものを入れる
9. ７を入れる
10. ９＋８の答えと４＊６の答えを掛けた答えに七を加える
11. ５を掛ける

この手順をpushとpopで表すと

1. push(5);
2. push(9);
3. push(8);
4. push(pop()+pop());
5. push(4);
6. push(6);
7. push(pop()*pop());
8. push(pop()*pop());
9. push(7);
10. push(pop()+pop());
11. push(pop()*pop());

こうなる。
pushとpopを除いて算術式で書くと

598+46**7+*

こうなることが分かる。
これをreverse Polish notation(逆ポーランド記法)もしくは後置記法と呼ぶ。
（これに対し通常の書き方をinfix(中置記法)という。）
逆ポーランドの利点は括弧が必要ではないことに尽きる。
これによりプッシュ、ポップの２つだけで簡単に算術式が書ける。
この一連の操作をリストを用いて実現する。