1 歩ずつ動かす
命令の列 (左から順に実行する)
- push 3
- push 7
- push 5
- pop
- push 9
- pop
- pop
- pop
出た値
- いま入れた値
- 出た値
- 空いている枠
- エラー
- top はいちばん上の位置
1 歩目 / 全 9 歩実行した命令 0 個中の値 0 個
空のスタックに、8 個の命令を順に実行します。入るのは 5 個までです。
いま動いている疑似コードの行
- 1push(x)
- 2いっぱいなら エラー (あふれる)
- 3top を 1 つ上げ、そこに x を置く
- 4pop()
- 5空なら エラー (出す値が無い)
- 6top の値を返し、top を 1 つ下げる
見本を変える
予想してみる
いまは 1 歩目です。
次の pop で出るのは、どれでしょう。
今回わかること
- 最後に入れた値が、最初に出る流れ
- 空のときに取り出すと、エラーになる理由
前提
- 配列と添字 (0 から数える番号)
- 配列の最後に足す・最後を取り除く書き方
どんな入れ物か
スタックは、値を上へ積み重ね、取り出すときもいちばん上から取る入れ物です。最後に入れた値が最初に出るので、後入れ先出しと呼びます。
積むのを push、取り出すのを pop と呼びます。いちばん上の位置を top と呼び、push と pop のたびに 1 つずつ動きます。
手順と具体例
- 1push では、いっぱいでないかを確かめてから、top の 1 つ上に値を置く
- 2pop では、空でないかを確かめてから、top の値を返す
- 3返したあとは、top を 1 つ下へ動かす
- 4空のときの pop と、いっぱいのときの push はエラーにする
| 命令 | 出た値 | 中身 (下から) |
|---|---|---|
| push 3 | なし | [3] |
| push 7 | なし | [3, 7] |
| push 5 | なし | [3, 7, 5] |
| pop | 5 | [3, 7] |
| push 9 | なし | [3, 7, 9] |
| pop | 9 | [3, 7] |
| pop | 7 | [3] |
| pop | 3 | [] |
手間と計算量
| 操作 | 手間 | 計算量 |
|---|---|---|
| push (積む) | 1 回 (いちばん上に置くだけ) | O(1) |
| pop (取り出す) | 1 回 (いちばん上を取るだけ) | O(1) |
| 底の値を見る | n 回 (上から順に取り出す) | O(n) |
push と pop は、中に 5 個あっても 100 万個あっても、いちばん上だけを触るので手間は変わりません。
使いどころ
向いているとき
- 直前の操作を取り消すとき (元に戻すの履歴)
- かっこの対応を確かめるとき
- 関数の呼び出しを覚えておくとき (呼び出しのスタック)
向いていないとき
- 先に来た順に処理したいとき (キューを使う)
- 途中の値を何度も探すとき (配列や辞書を使う)
コード
疑似コード
- 1push(x)
- 2いっぱいなら エラー (あふれる)
- 3top を 1 つ上げ、そこに x を置く
- 4pop()
- 5空なら エラー (出す値が無い)
- 6top の値を返し、top を 1 つ下げる
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- Python のリストだけでスタックになりますか？
- なります。append で積み、pop() で最後を取り出せば、そのままスタックです。上限を決めたいときだけ、上のように数を確かめます。
- 空のスタックで pop すると、実際のプログラムではどうなりますか？
- Python のリストは IndexError、Java の ArrayDeque は例外を出します。先に空かどうかを確かめてから pop するのが安全です。
