Pythonアルゴリズム

Pythonのスタック(stack)

このレッスンでは、Pythonのリストを使って、要素を積む(push)、取り出す(pop)、一番上を見る(peek)というスタックの基本操作を実装します。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

元に戻すボタン、ブラウザーの戻るボタン、かっこの対応のチェックはすべて、要素を覚えておき、最も新しいものから取り出す必要があります。スタックはまさにそのために作られたデータ構造です。

身近なたとえ

スタックは食堂の皿の山のようなものです。新しい皿は上に置き、皿は上から取ります。最後に置いた皿が最初に使われ、真ん中の皿は抜き取れません。

皿の山からコードへ
stack.append("third")🍽️ 皿を上に置く
stack.pop()⬆️ いちばん上の皿を取る
stack[-1]👀 取らずにいちばん上の皿を見る
stack📚 山に残っている皿
後入れ先出し:触れられるのはいちばん上だけです。
ひと言でいうと

スタックは後入れ先出し(LIFO)のコレクションで、要素の追加と取り出しは上(トップ)でだけ行います。

重要なポイント

  1. stack.append(...) は要素を上、つまりリストの最後に積みます。
  2. stack.pop() は上の要素を取り出して返し、ここでは "third" です。
  3. stack[-1] は取り出さずに上の要素を読みます。
  4. 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. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

空のスタックから取り出す

空のリストに 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 のレビューも受けられます。

すべてのチャレンジ