Pythonでスタックを実装する3つの方法を具体例つきで解説

スタック（Stack）は、LIFO（Last In First Out：後入れ先出し）という仕組みで動作する線形データ構造です。最初にスタックへ格納された要素は、最後に取り出されるという特徴を持ちます。

身近な例で理解するスタック

スタックの仕組みは、「積み重ねた皿」をイメージすると分かりやすくなります。

皿は1枚ずつ上に重ねていきます。最初に置いた皿は山の一番下にあり、最後に置いた皿が一番上にきます。皿が必要になったとき、私たちは必ず一番上の皿、つまり最後に置かれた皿から取ります。逆に、最初に置かれた皿が一番下に残り、最後に取り出されることになります。これこそが「後入れ先出し（LIFO）」の仕組みです。

Pythonにおけるスタックの実装方法

Pythonでは、リストや標準ライブラリの組み込みモジュールなどを利用して、複数の方法でスタックを実装できます。ここでは代表的な3つの方法を紹介します。

方法1：リスト（list）を使った実装

Pythonのリストを使えば手軽にスタックを実装できます。ただし、リストによる実装はパフォーマンス面で効率が良くないため、大規模な処理には推奨されません。

主な操作

append() … スタックの末尾に要素を追加します。

pop() … スタックの末尾（一番上）の要素を取り除き、その値を返します。要素はLIFOの順序で取り出されます。

コード例

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print("初期のスタック:", stack)
print("スタックから取り出した要素")
print(stack.pop())
print(stack.pop())
print("要素を取り出した後のスタック:", stack)

実行結果

初期のスタック: [1, 2, 3]
スタックから取り出した要素
3
2
要素を取り出した後のスタック: [1]

なお、空のスタックに対してさらにpop()を呼び出すことはできません。その場合、例外が発生します。

stack.pop()
IndexError: pop from empty list

方法2：queue.LifoQueueを使った実装

これはPythonの組み込みモジュールを使った実装方法です。queueモジュールからLifoQueueをインポートして使用します。スタックの最大サイズを指定して初期化でき、サイズに0を指定した場合は無制限のスタックとして扱われます。

主な操作

maxsize … スタックに格納できる要素数の上限。

get() … スタックの末尾（一番上）の要素を取り除いて返します。スタックが空の場合は、要素が追加されるまで待機します。

get_nowait() … スタックの末尾の要素を取り除いて返します。スタックが空の場合は例外を発生させます。

put(item) … スタックの末尾に要素を追加します。スタックが満杯の場合は、空きスロットができるまで待機します。

put_nowait(item) … スタックの末尾に要素を追加します。スタックが満杯の場合は例外を発生させます。

full() … スタックが満杯ならTrue、そうでなければFalseを返します。

empty() … スタックが空ならTrue、そうでなければFalseを返します。

qsize() … スタック内の現在の要素数を返します。

コード例

from queue import LifoQueue

s = LifoQueue(maxsize=3)
s.put(1)
s.put(2)
s.put(3)
print("スタックは満杯か:", s.full())
print("スタックから取り出した要素")
print(s.get())
print(s.get())
print("スタック内の要素数:", s.qsize())
print("スタックは空か:", s.empty())

実行結果

スタックは満杯か: True
スタックから取り出した要素
3
2
スタック内の要素数: 1
スタックは空か: False

方法3：collections.dequeを使った実装

もうひとつの方法が、collectionsモジュールのdeque（デック）を使う実装です。dequeは両端キューとして設計されており、スタック用途にも高速に対応できます。

主な操作

append() … スタックの末尾に要素を追加します。

pop() … スタックの末尾の要素を取り除いて返します。計算量はO(1)と非常に高速です。

コード例

from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print("初期のスタック:", stack)
print("スタックから取り出した要素")
print(stack.pop())
print(stack.pop())
print("要素を取り出した後のスタック:", stack)

実行結果

初期のスタック: deque([1, 2, 3])
スタックから取り出した要素
3
2
要素を取り出した後のスタック: deque([1])

なお、空のdequeに対してpop()を呼び出すと、IndexErrorの例外が発生する点に注意してください。