Pythonでスタックを作る方法｜リストとdequeを使った実装ガイド

はじめに

スタックは、幅広い用途で活用されている重要なデータ構造です。

プログラミングにおいて、スタックはデータを「後入れ先出し（LIFO：Last-In, First-Out）」の順序で格納します。つまり、最後に追加された要素が最初に処理される仕組みです。

では、Pythonでスタックはどのように作成すればよいのでしょうか？本ガイドではこの疑問にお答えします。読み終える頃には、Pythonでスタックを作成・操作するスキルをしっかり身につけられているでしょう。

Pythonにおけるスタックとは

スタックは、データを後入れ先出し（LIFO）の順序で管理するデータ構造です。

この仕組みをイメージしやすくするために、皿の山を思い浮かべてください。洗い物の皿が積まれているとき、最初に手に取るのは一番上の皿ですよね。皿を片付けていくにつれて、下に積まれた皿へと順番にアクセスできるようになります。

スタックは、キューとは正反対の動作をする点にも注目です。キューは最も古く追加された要素から取り出す「先入れ先出し（FIFO）」構造である一方、スタックは最も新しく追加された要素から取り出す「後入れ先出し（LIFO）」構造を採用しています。

スタックがサポートする主な操作は「push」と「pop」の2つです。pushはスタックの先頭に要素を追加する操作、popはスタックの先頭から要素を取り除く操作を指します。

Pythonでスタックを作成する方法は主に2つあります。1つは組み込みのリストを使う方法、もう1つはcollections.deque()クラスを使う方法です。それぞれのやり方を詳しく見ていきましょう。

方法1：Pythonの組み込みリストを使う

Pythonの組み込みリスト型を使えば、手軽にスタックを実装できます。

Pythonのリストは配列として実装されているため、要素の追加や削除が簡単に行えます。また、値を挿入した順序が保持されるため、リストの末尾の要素を柔軟に操作できます。

ここで、クラスに提出された課題を管理するスタックを作成する例を考えてみましょう。先生は、提出された順番どおりに課題を採点したいと考えています。つまり、最初に提出された課題がスタックの一番下に、最後に提出された課題が一番上に積まれるイメージです。

スタックへの要素の追加

スタックに要素を追加するには、append()メソッドを使用します。以下のコードで課題のスタックを作成できます。

assignments = []

assignments.append("Hannah")
assignments.append("Benny")
assignments.append("Gordon")

print(assignments)

実行結果：

['Hannah', 'Benny', 'Gordon']

このコードでは、まずassignmentsという空のリストを宣言しています。続いて、append()メソッドを使って、提出済み課題のリストに3人の名前を追加しました。追加の順序はHannah、Benny、Gordonです。Gordonが最後に課題を提出したため、リストの末尾に配置されています。

スタックからの要素の削除

Gordonの課題の採点が終わり、次に採点すべき課題を確認したい場面を想定しましょう。これには、スタックの先頭にある要素を取り除く必要があります。

スタックから要素を削除するには、pop()メソッドを使用します。スタックの先頭の要素を削除するコードは以下のとおりです。

assignments = []

assignments.append("Hannah")
assignments.append("Benny")
assignments.append("Gordon")
assignments.pop()

print(assignments)

実行結果：

['Hannah', 'Benny']

pop()によってGordonの名前がスタックから取り除かれ、スタックにはHannahとBennyの2つの名前のみが残りました。

方法2：collections.dequeクラスを使う

collectionsライブラリのdequeクラスを使うと、両端キュー（double-ended queue）を作成できます。

dequeオブジェクトは双方向連結リストとして実装されており、要素の挿入や削除において高速かつ安定したパフォーマンスを発揮します。さらに、collectionsライブラリはPython標準ライブラリの一部なので、外部ライブラリをインストールすることなく、import文だけで利用を開始できます。

collections.dequeクラスを使うには、まずimport文でコードに読み込む必要があります。

from collections import deque

それでは、先ほどの課題管理の例を使って、collections.dequeクラスの動作を確認してみましょう。

dequeスタックへの要素の追加

dequeスタックに要素を追加する場合も、append()メソッドを使用します。dequeクラスで課題のスタックを作成するコードは以下のとおりです。

from collections import deque

assignments = deque()

assignments.append("Hannah")
assignments.append("Benny")
assignments.append("Gordon")

print(assignments)

実行結果：

deque(['Hannah', 'Benny', 'Gordon'])

コードの流れを整理しましょう。まず、collectionsライブラリからdequeクラスをインポートします。次に、deque()でdequeオブジェクトを生成し、変数assignmentsに代入します。

その後、Hannah、Benny、Gordonの3つの名前を課題のdequeに追加し、最後に内容をコンソールに出力しています。

実行結果を見ると、データがリストではなくdequeとして格納されていることがわかります（出力がdeque()で囲まれている点に注目）。これはdeque構造を使用しているためですが、データの振る舞い自体はスタックと同じです。

dequeスタックからの要素の削除

dequeスタックから要素を削除する場合も、pop()メソッドを使用します。

GordonとBennyの課題の採点が完了したとしましょう。スタックからこれらを取り除くコードは以下のとおりです。

from collections import deque

assignments = deque()

assignments.append("Hannah")
assignments.append("Benny")
assignments.append("Gordon")
assignments.pop()
assignments.pop()

print(assignments)

実行結果：

deque(['Hannah'])

このコードでは、まず3つの値を持つdequeスタックを作成し、続いてpop()を2回実行しています。pop()が呼び出されるたびに、スタックの先頭の要素が削除されます。その結果、Gordon、Bennyの順にスタックから取り除かれ、最後にHannahだけが残ります。

Pythonのdequeクラスについてさらに詳しく学びたい方は、キューとdequeに関するチュートリアルもあわせて参考にしてください。

どちらの方法を選ぶべき？

小規模なデータやシンプルな用途であれば、組み込みリストで十分対応できます。一方、大量の要素を頻繁に追加・削除するようなケースでは、双方向連結リストベースのdequeの方が安定したパフォーマンスを発揮します。データ量や操作の頻度に応じて、適切な方法を使い分けるとよいでしょう。

まとめ

スタックは、データを後入れ先出し（LIFO）の順序で格納できる便利なデータ構造です。Pythonでスタックを実装する方法は複数ありますが、特に実用的なのは、組み込みのリスト構造を使う方法と、collections.deque()クラスを使う方法の2つです。

本チュートリアルでは、具体的なコード例とともに、リストとcollections.deque()を使ったPythonでのスタックの作成方法を解説しました。これであなたも、プロのPython開発者のように自信を持ってスタックを扱えるはずです！