最後に入れたものを、最初に出す
スタックとは、最後に入れたものを、最初に取り出す入れ物です。キューは反対に、最初に入れたものを、最初に取り出します。この2つが解ける問題を見分けられるようになります。
エディタの「元に戻す」は、直前の操作から順に戻ります。コピー機の印刷待ちは、出した順に印刷されます。
このレッスンのゴール
メモ
スタックとキューを使って、問題を解くことができる。
重要な言葉
| ことば | いみ |
|---|---|
| スタック | 後に入れたものから先に出る入れ物。後入れ先出し（LIFO） |
| キュー | 先に入れたものから先に出る入れ物。先入れ先出し（FIFO） |
| プッシュ | スタックの一番上に、1つ積むこと |
| ポップ | スタックの一番上から、1つ取り出すこと |
| エンキューとデキュー | キューに入れることと、取り出すこと |
学生が入力するセルは、このプレビューでは空白です。
スタックは一番上だけを触る
スタックは、本を積み重ねた山と同じです。足すのも取るのも、一番上だけです。
プッシュで一番上に積み、ポップで一番上を取ります。取り出せるのは、最後に積んだものです。真ん中を直接取ることはできません。
例: 元に戻す操作の流れ
| 操作 | スタックの中（下から上） | 出るもの |
|---|---|---|
| プッシュ「料金」 | 料金 | |
| プッシュ「は」 | 料金、は | |
| プッシュ「300円」 | 料金、は、300円 | |
| ポップ | 料金、は | 300円 |
| ポップ | 料金 | は |
学生が入力するセルは、このプレビューでは空白です。
リストで作った、元に戻す機能
# エディタの「元に戻す」を、スタックで作ります。
history = []
text = ""
for word in ["料金", "は", "300円", "です"]:
history.append(text) # 変える前の文を積みます。
text = text + word
print("今の文:", text)
text = history.pop() # 元に戻すと、最後に積んだものが出ます。
print("1回戻す:", text)
text = history.pop()
print("2回戻す:", text)
# 3回目の history.pop() を足して、実行しましょう。
キューは前から出して、後ろに足す
キューは、駅の券売機の行列と同じです。新しい人は一番後ろに並び、一番前の人から買います。
エンキューで後ろに入れ、デキューで前から出します。出る順番は、入れた順番と同じです。印刷待ちや、順番に処理する仕事に向きます。
例: 印刷待ちの流れ
| 操作 | キューの中（前から後ろ） | 出るもの |
|---|---|---|
| エンキュー「成績表」 | 成績表 | |
| エンキュー「請求書」 | 成績表、請求書 | |
| エンキュー「地図」 | 成績表、請求書、地図 | |
| デキュー | 請求書、地図 | 成績表 |
| デキュー | 地図 | 請求書 |
学生が入力するセルは、このプレビューでは空白です。
スタック: 後に入れた2が先に出る
python3 -c "s = []; s.append(1); s.append(2); print(s.pop(), s.pop())"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
キュー: 先に入れた a が先に出る
python3 -c "from collections import deque; q = deque(); q.append('a'); q.append('b'); print(q.popleft(), q.popleft())"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
括弧の対応は、スタックで調べる
式の括弧が正しく閉じているかは、コンパイラが最初に確かめることの1つです。開き括弧が来たらプッシュします。閉じ括弧が来たらポップして、対になる種類か調べます。
最後にスタックが空なら、正しい式です。ラボの電卓も、同じ考え方で括弧を読みます。
括弧を調べる小さなコード
# 開き括弧を積み、閉じ括弧が来たら取り出して、対になるか調べます。
text = "(2 + [3 * 4])"
pairs = {")": "(", "]": "["}
stack = []
ok = True
for ch in text:
if ch == "(" or ch == "[":
stack.append(ch)
elif ch == ")" or ch == "]":
if len(stack) == 0 or stack.pop() != pairs[ch]:
ok = False
print(ok and len(stack) == 0)
# text を "(2 + [3 * 4)]" に変えて、もう一度実行しましょう。
コンパイラのフォルダに入る
cd ~/compilerここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
電卓を用意する
makeここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
括弧が合っている式
echo "(2 + 3) * 4" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
閉じ括弧が足りない式
echo "(2 + 3" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
括弧は、開きの数と閉じの数が同じなら正しい、と思いがちです。)( は数が同じでも誤りで、[(1 + 2]) も種類が交差しています。順番と種類を見るために、数えるのではなくスタックを使います。