Pythonアルゴリズム
Pythonのスタック(stack)
このレッスンでは、Pythonのリストを使って、要素を積む(push)、取り出す(pop)、一番上を見る(peek)というスタックの基本操作を実装します。
はじめに
どんな問題を解決するか
元に戻すボタン、ブラウザーの戻るボタン、かっこの対応のチェックはすべて、要素を覚えておき、最も新しいものから取り出す必要があります。スタックはまさにそのために作られたデータ構造です。
身近なたとえ
スタックは食堂の皿の山のようなものです。新しい皿は上に置き、皿は上から取ります。最後に置いた皿が最初に使われ、真ん中の皿は抜き取れません。
皿の山からコードへ
stack.append("third")🍽️ 皿を上に置くstack.pop()⬆️ いちばん上の皿を取るstack[-1]👀 取らずにいちばん上の皿を見るstack📚 山に残っている皿ひと言でいうと
スタックは後入れ先出し(LIFO)のコレクションで、要素の追加と取り出しは上(トップ)でだけ行います。
重要なポイント
stack.append(...)は要素を上、つまりリストの最後に積みます。stack.pop()は上の要素を取り出して返し、ここでは"third"です。stack[-1]は取り出さずに上の要素を読みます。appendもpopもリストの最後で動くので速いです。
どんな場面で使う?
- 元に戻す・やり直しの履歴。
- かっこの対応のチェックや式の解析。
- 再帰を使わない深さ優先探索とバックトラッキング。
使わなくてよいとき
- 要素を届いた順に出す必要がある場合:それはキューです。
- 真ん中や位置で要素を取り出す必要がある場合:普通のリストや別の構造のほうが合います。
動きで理解する
pushとpopを試すと、最後に入れた要素が必ず最初に出ることがわかります。
サンプルコード
main.py
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
実行結果
popped: third
top: second
stack: ['first', 'second']
コードの解説
append()メソッドはスタックの一番上に要素を追加し、pop()は一番上の要素を取り出して削除するので、"third"が最初に出てきます。stack[-1]を使うと、削除せずに一番上の要素を確認できます。リスト末尾でのappend()とpop()は、どちらも平均O(1)で動きます。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
空のスタックから取り出す
空のリストに pop() すると IndexError になります。
問題
item = stack.pop()
修正
if stack:
item = stack.pop()
リストの先頭をトップとして使う
insert(0, x) と pop(0) はすべての要素を動かすので遅いです。
問題
stack.insert(0, item)
stack.pop(0)
修正
stack.append(item)
stack.pop()
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
進み具合はこのブラウザーに保存されています ログインすると、どのデバイスでも引き継げます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. 中級
- Mini Stack-Language Interpreter Evaluate a small stack language. 難しい