［Python入門］クラスを使ってスタックとキューを作成する：Python入門（1/2 ページ）
Pythonのクラス機構を利用して、スタックとキューという代表的なデータ構造を作成し、特殊メソッドを使ってスタックをさらに改良してみる。
* 本稿は2019年8月6日に公開された記事を、Python 3.12.0で動作確認したものです（確認日：2023年11月10日）。
前回までに、クラスの基本的な構成要素を見てきた。今回は、これらの知識を用いてスタックとキューと呼ばれるデータ構造を自分で作ってみよう。
スタックとキュー
コンピュータ上で動作するプログラムではよく「スタック」と「キュー」と呼ばれる形式でデータが使われる。これらはいずれも複数のデータを保管して、それを取り出すために使われるデータ構造だが、データの取り出し方に違いがある。
プログラミングの世界における「スタック」（stack）とは「データを積み重ねたもの」という意味を持っている。
スタックとは上の画像に示したように、スタックではデータは順番に積み重ねられていく。スタックにデータを積むことを、「プッシュ」という。これに対して、プッシュされたデータを取り出すことを「ポップ」と呼ぶ（「プル」と呼ぶこともある）。プッシュされたデータをポップする（取り出す）際には、直近にプッシュされたものが取り出される。スタックは「後に入れたデータが先に出てくる」データ構造といえる。これを「Last-in, First-out」「LIFO」「後入れ先出し」などと表すこともある。
スタック的なデータ管理を行っている例としては、身近なところではWebブラウザの閲覧ページの履歴が挙げられるだろう。WebページA→WebページB→WebページCという順序でページを閲覧して、ブラウザの戻るボタンなどから履歴をたどれば、閲覧の順とは逆順にページをたどることになるはずだ。
Webページの閲覧履歴は、閲覧した順序とは逆順に取り出されるスタックについてはInsider's Computer Dictionaryの「スタックとは」なども参考にしてほしい。
もう一つのデータ構造である「キュー」もまた幾つものデータを保管しておくためのデータ構造だ。プログラミングの世界では「キュー」（queue）は「待ち行列」のことだ。待ち行列とは、例えば、銀行のATMのような人が何かの処理を行うのを待って形成される行列のことだ（数学の用語でいうところの行列とは異なる）。
キュー今の例から分かるように、キューはスタックとは違って、最初にキューに置かれたものが、最初に出てくる（銀行でATMを待つ行列の先頭にいる人が最初にそれを使えるようになるのと同じだ）。なお、キューにデータを置くことを「エンキュー」「キューイン」などと、キューからデータを取り出すことを「デキュー」「キューアウト」などと呼ぶ。
キューについてはInsider's Computer Dictionaryの「キューとは」なども参考にしてほしい。
以下では、スタックとキューをPythonのクラスを使って定義してみよう。
スタックを定義する
まず定義するクラスの名前を、ここでは「MyStack」としよう。
そして、スタックをクラスとして表現するために必要な属性を考える。上では、「プッシュ」と「ポップ」という操作があると述べた。これらはメソッド（インスタンスメソッド）として定義する。それに加えて、プッシュするデータを保存する先が必要だ。これにはインスタンス変数としてリストを用意すればよいだろう。メソッド名とパラメーターリスト、インスタンス変数名などを以下にまとめる。
| 操作 | 属性名 | 説明 |
|---|---|---|
| プッシュ | push(self, item) | itemに受け取ったデータをインスタンス変数stackに追加する。戻り値はなし |
| ポップ | pop(self) | インスタンス変数stackの末尾のデータを取り出す。その後、対応する要素をリストから削除し、取り出したデータを戻り値として返送する |
| データの保存先（インスタンス変数） | stack | 最初は空のリストとして作成し、それに対してデータを追加したり、取り出したりする。コード内ではself.stackとして参照することを忘れないようにすること |
| MyStackクラスの属性 | ||
図にすると次のようになる。
Pythonで作成するMyStackクラスのインスタンス（__init__メソッドは省略）ここで注意する点としては、スタックは「データを積み重ねたもの」と述べたが、ここではそれをリストとして表現している点だ。リストでは最初の要素のインデックスが「0」で、その次の要素のインデックスが「1」で、……、のようになる。ここでは、スタックへの「プッシュ」を「リストへのデータの追加」として表現し、スタックからの「ポップ」をリスト末尾からのデータの取り出し（と、その後、リストからその要素を削除）と考えよう。すると、スタックとリストの関係は次のようになる*1。
*1 これとは逆に、「プッシュ」では「リストの先頭にデータを挿入」し、「ポップ」では「リストの先頭のデータを取り出す」という方法も考えられる。興味のある方は後述のコードを見た後に、この方法でスタックを自分で定義してみよう（実は、実行時の効率や速度の面で2つの方法には差があるが、本稿では取り上げない）。
次に実際にMyStackクラスを定義してみよう。
MyStackの定義
ここまでのことからクラスの概要は次のようになる。以下では、__init__メソッドでのインスタンス変数stackの初期化だけを実際のコードとして記述している。pushメソッドとpopメソッドの定義の本体にある「pass文」は第28回「クラスの基礎知識」でも触れたが、何もしない文だ。ここでは、後でこれらのメソッドについて見ていくので、取りあえずpass文を使ってメソッドを定義している。
class MyStack:
def __init__(self):
self.stack = [] # 空のリストをスタックに保存するデータの入れ物とする
def push(self, item):
pass # 取りあえず何もしない
def pop(self):
pass # 取りあえず何もしない
__init__メソッドでは、既に述べた通り、データを保存する先となるリストを用意して、それをインスタンス変数stackに代入しているだけだ。
pushメソッドの定義
では、pushメソッドの定義ではどのような処理を書けばよいだろう。リストに要素を追加するには、appendメソッドとextendメソッドが使える（これらのメソッドについては、第17回「リストの操作」の「リストへの要素の追加：appendメソッド／extendメソッド」を参照されたい）。
簡単にいえば、appendメソッドは、与えられたデータをリストの末尾に追加する。このときに、リストを渡すと、それはリストのまま追加される。extendメソッドは渡されたデータが反復可能オブジェクトであれば、それらを個別にリストの末尾に追加するところが異なる点だ。ここではシンプルにappendメソッドを使って、受け取ったデータをリストに追加することにしよう。
実際のコードは次のようになる。
class MyStack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
pass # 取りあえず何もしない
実際にコードが正しく動くか試してみよう。
mystack = MyStack()
mystack.push(0) # スタックに「0」をプッシュ（リストの末尾に「0」を追加）
mystack.push(1) # スタックに「1」をプッシュ（リストの末尾に「1」を追加）
mystack.push(2) # スタックに「2」をプッシュ（リストの末尾に「2」を追加）
print(mystack.stack) # MyStackクラスのインスタンスのインスタンス変数の値を表示
このコードを実行すると、次のようになる。
print関数呼び出しの結果を見ると、リストをスタックの入れ物として、正しく動作しているようだ。
popメソッドの定義
ここで作成しているスタックは、内部的にリストを使用して、プッシュではリストの末尾にデータを追加していた。このため、ポップで行う処理としては、リストの末尾のデータを一時的に変数に代入して、リストからその要素を削除して、最後に取り出しておいたデータを戻り値として返送すればよいだろう。
第16回「リストの基本」の「リストの要素」でも述べたが、リストの末尾はインデックスを「-1」としてアクセスできる。このことを利用すると、今述べた処理は次のようになる。
class MyStack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
result = self.stack[-1] # 末尾の要素を変数に取り出す
del self.stack[-1] # リストから要素を削除する
return result # リスト末尾から取り出したデータを返送する
では、先ほどと同様にこのコードをテストしてみよう。
mystack = MyStack()
mystack.push(0)
mystack.push(1)
print(mystack.pop())
print(mystack.pop())
実行すると、次のようになる。
実行結果「0」→「1」という順序でスタックにプッシュをして、ポップでは「1」→「0」という順序でデータが取り出されているので、どうやら正しく動作しているようだ。
なお、Pythonのリストには上で書いた処理を行ってくれるpopメソッドもある。このメソッドを引数なしで呼び出せば、まさに今自分で書いたコードと同じことをしてくれる。よって、上のコードは次のようにも書ける。
class MyStack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
return self.stack.pop()
ところで、上のテストを実行した時点では、スタック（が使用しているリスト）は空となっている。この状態で、スタックからポップをするとどうなるだろう。
print(mystack.pop())
すると、以下に示すようにエラー（IndexError例外）が発生する。
空のスタックに対してpopメソッドが呼び出されたときに、どうすればよいかの判断は難しい。上記のまま、エラー（例外）を発生させるのも一つの手だ。そうではなく、自分で例外を発生させて、「スタックの利用者に、空のスタックからポップしようとした」ことを伝える方法もある。あるいは、「値がない」ことを意味するNone値を返すようにする方法もある（いずれにせよ、空のスタックからポップするのはあまりよろしくない事態に陥っていることを示唆しているので、スタックを利用する側でも何らかの対処が必要になる）。例外については、本連載ではまだ取り上げていないので、ここではNone値を返すようにしてみよう。
空のスタックに対してpopメソッドが呼び出されたかどうかは、リストの要素数を調べれば分かる。そのため、そのときにNone値を返すようにするには次のようなコードを書けばよいだろう。
class MyStack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if len(self.stack) == 0:
return None
return self.stack.pop()
実際に試してみよう。
mystack = MyStack()
mystack.push(0)
print(mystack.pop())
print(mystack.pop())
実行結果を以下に示す。
実行結果このようにすると、必要以上にpopメソッドが呼び出されると、None値が返されるようになる。エラー（例外）にしろ、None値にしろ、それらは異常な状態であることを意味するので、実際にはこれを呼び出した側で何らかの対策が必要になることは同じだ（そういう意味では、プログラムの動作を止めることなく、あえてNone値を返す必要はないかもしれない）。
これでスタックの定義は取りあえず完了だ。次にキューを定義してみよう。
キューを定義する
キューも、スタックと同様に、データを保存するのにリストを利用しよう。異なるのは、キューにデータを保存するメソッドの名前、キューからデータを取り出すメソッドの名前と動作くらいだ。これらを以下にまとめる。クラス名はMyQueueとしよう。
| 操作 | 属性名 | 説明 |
|---|---|---|
| エンキュー | enqueue(self, item) | itemに受け取ったデータをインスタンス変数queueに追加する。戻り値はなし |
| デキュー | dequeue(self) | インスタンス変数queueから先頭のデータを取り出す。その後、対応する要素をリストから削除し、取り出したデータを戻り値として返送する |
| データの保存先（インスタンス変数） | queue | 最初は空のリストとして作成し、それに対してデータを追加したり、取り出したりする。コード内ではself.queueとして参照することを忘れないようにすること |
| MyQueueクラスの属性 | ||
2つのメソッドの名前がスタックではpush／popだったのが、キューではenqueue／dequeueになることと、dequeueメソッドではリストの先頭の要素を取り出すようにすることがスタックとの違いとなる。
リストの先頭要素のインデックスは「0」なので、実際にはdequeueメソッドのコードもインデックスが変わる以外は、スタックのコードとそれほど変わらない。
実際のコードは次のようになる。
class MyQueue:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if len(self.queue) == 0:
return None
result = self.queue[0]
del self.queue[0]
return result
コード自体は、クラス名やメソッド名、インスタンス変数名などを除けば、データを取り出すときのインデックス指定が異なるだけとなるので、詳しい説明は省略してもよいだろう。
では、このクラスの動作を確認してみよう。
myq = MyQueue()
myq.enqueue(0)
myq.enqueue(1)
print(myq.dequeue())
print(myq.dequeue())
print(myq.dequeue())
実行結果を以下に示す。
実行結果スタックとは反対に、キューに入れた順番でデータが取り出されているのが分かるはずだ。
Copyright© Digital Advantage Corp. All Rights Reserved.
ITmediaはアイティメディア株式会社の登録商標です。