戻るボタンはどう動くのか
ブラウザで、ホーム、お店、カートの順にページを開きました。戻るボタンを押すと、カート、お店、ホームの順で戻ります。
一番新しいものが、一番先に取り出される。この決まりを持つ入れ物を、スタックと呼びます。
このレッスンのゴール
メモ
スタックとキューを使って、値を入れて取り出せる。
重要な言葉
| ことば | いみ |
|---|---|
| スタック | 最後に入れたものを、最初に取り出す入れ物 |
| キュー | 最初に入れたものを、最初に取り出す入れ物 |
| プッシュ | スタックの一番上に値を入れること |
| ポップ | スタックの一番上から値を取り出すこと |
| データ構造 | 値をしまっておく、決まった形の入れ物 |
学生が入力するセルは、このプレビューでは空白です。
スタックは後に入れたものから出る
食器を積み重ねると、洗うために取るのは、一番上の一枚です。スタックも同じで、入れるのも取るのも、上の端だけです。
この決まりを、後入れ先出し、英語の頭文字で LIFO と言います。Python のリストでは、append で入れ、pop() で取ります。
例：スタックの変化
| 操作 | スタックの中身（右が上） | 取り出した値 |
|---|---|---|
| 入れる 1 | 1 | なし |
| 入れる 2 | 1, 2 | なし |
| 入れる 3 | 1, 2, 3 | なし |
| 取り出す | 1, 2 | 3 |
| 取り出す | 1 | 2 |
学生が入力するセルは、このプレビューでは空白です。
スタックに三つ入れて、取り出す
docker exec jupyter python3 -c 'exec("stack = []\nstack.append(1)\nstack.append(2)\nstack.append(3)\nprint(stack.pop(), stack.pop(), stack.pop())")'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
キューは先に入れたものから出る
コンビニのレジの列を思い出してください。先に並んだ人が、先にレジへ進みます。キューも同じです。
この決まりを、先入れ先出し、FIFO と言います。入れるのは後ろの端、取り出すのは前の端です。印刷の順番待ちにも使います。
例：印刷待ちのキュー
| 操作 | キューの中身（左が前） | 取り出した値 |
|---|---|---|
| 入れる 1 | 1 | なし |
| 入れる 2 | 1, 2 | なし |
| 入れる 3 | 1, 2, 3 | なし |
| 取り出す | 2, 3 | 1 |
| 取り出す | 3 | 2 |
学生が入力するセルは、このプレビューでは空白です。
キューに三つ入れて、取り出す
docker exec jupyter python3 -c 'exec("queue = []\nqueue.append(1)\nqueue.append(2)\nqueue.append(3)\nprint(queue.pop(0), queue.pop(0), queue.pop(0))")'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
スタックとキューは、どちらも「順に取り出す入れ物」なので同じだと思いがちです。違いは取り出す順番です。スタックは一番新しい値、キューは一番古い値を取り出します。
括弧の対応をスタックで調べる
(a + [b]) のような式で、括弧がきちんと閉じているかを調べます。開き括弧に出会ったらスタックに入れます。
閉じ括弧に出会ったら、スタックの一番上を取り出し、対応する開き括弧か確かめます。最後にスタックが空なら、正しい式です。
例：([)] を調べる
| 読む文字 | 操作 | スタックの中身 |
|---|---|---|
| ( | 入れる | ( |
| [ | 入れる | (, [ |
| ) | 上は [ なので、合わない | 間違いと分かる |
学生が入力するセルは、このプレビューでは空白です。