今回はPythonチュートリアルを１～９章までオンラインで読んでみてStackとQueueならなんとなくできそうだったのでコードを書いてみました。
Stack:
Stackの他の呼び名でLIFO(Last In First Out)というのがありますが、その名のとおり最後に入ったエレメント(要素)を出す時には最初に出すデータストラクチャーです。Stackをインプリメントするにあたり必要になるファンクション(関数)は2つあり、エレメントをStackの末尾に入れる関数でpush()とエレメントをStackの末尾から出すpop()です。イメージとしては本を積み上げて取る時は積まれた本の一番上から取っていくと思って頂ければいいと思います。モジュールはこんな感じで説明は後で書いています。
class Stack:
def __init__(self, stack = None):
if type(stack) is type([]):
self.stack = stack
elif stack is None:
self.stack = []
else:
print '\nError Message:\n\tYour input is not type of list!\n\tPlease enter list type!\n'
def push(self, e):
self.stack.append(e)
return self.stack
def pop(self):
try:
sEl = self.stack.pop()
return (sEl, self.stack)
except IndexError:
print '\nError Message:\n\tThere is no element in the stack!\n'
まずはStackのクラスを作り、コンストラクタではStackはパラメーター(引数)にリストを取るようにしました。Pythonでは何故かコンストラクタの最初のパラメーターにselfを入れるみたいですが、次の行を見てみるとself.stackと記述されています。たぶんこれはJavaでいうthisの事だと思います。Javaのthisはアクセスしたい変数がローカルかグローバルのどちらで定義されているのか見分ける時に使ったような気がします。(たぶん、絶対、忘れてもたｗ)という事でPythonの場合はパラメーターの変数名のstackなのか、このクラスで新たに定義する変数のstackなのかを見分けてるのかなと思います。
push():
最初のファンクションのpushではエレメントを末尾に挿入するだけなのでリストのビルトイン関数のappendにパラメーターで取ったエレメントのeを与えて呼ぶだけです。念のためにどのようにStackが変わっているかprintできるように戻り値としてstackを返しています。これは、このファンクションを呼んだ時にprintで確認できるはずです。
pop():
ここでも単純にビルトイン関数のpop()を使う事によって頭のエレメントを取り出して削除することができます。それを新しい変数sEl(stackElementの略のつもり)に代入して戻り値で返します。戻り値ではスタックの構成が変わっているのか確認するためにstack自身も返したかったのでタプルで囲って二つの値を同時に返しています。もしスタックがエレメントを１つも持っていない状態でこの関数を呼ぶとIndexErrorが発生するのでtryを使ってエラーが出た場合はprint後のメッセージを警告として出すようにしました。tryは中にあるコードを実行して何か問題があれば次のブロックで捕らえてメッセージを出したりする時に使います。これはJavaでもtry&catchで使うのでJavaをこれから勉強されたい方は是非覚えておいてください。
Queue
Queueでもエレメントを入れるする際はStackと同じ処理をしますが、エレメント出す際は残っているエレメントの最初に入れられたものから出していきます。これをFIFO(First In First Out)と呼びます。Stackと同様に二つの関数を作成していきます。まずは入れる関数をenqueue()と名付け、出す関数をdequeue()としました。このデータストラクチャーのイメージとしてはビリヤードの玉を一列に並べて最後部から一気に押し出して先頭から穴に落としていくと思えば解りやすいかもしれません。
class Queue:
def __init__(self, queue = None):
if type(queue) is type([]):
self.queue = queue
elif queue is None:
self.queue = []
else:
print '\nError Message:\n\tYour input is not type of list!\n\tPlease enter list type!\n'
def enqueue(self, e):
self.queue.append(e)
return self.queue
def dequeue(self):
try:
qEl = self.queue[0]
del self.queue[0]
return (qEl, self.queue)
except IndexError:
print '\nError Message:\n\tThere is no element in the queue!\n'
dequeue():
enqueu()ではStackのpush()と同じ手順を取りましたが、dequeue()では最初に入れたエレメントを最初に取り出したいのでインデックッス０内のエレメントを新しい変数に代入した後に削除しています。delで削除する事によりリスト内のインデックス１が保有しているエレメントが自動的にインデックス０に移動するので繰り返し行う時もリスト内の一番古いエレメントが選択されます。ここでもpop()同様、リストがエレメントを１つも保有していないときのエラーを示すためにtry文を使いエラーの際にはメッセージを表示しています。
この投稿ではPythonほぼ初心者という事で簡単なデータストラクチャーをインプリメントしました。もう少しPythonの参考書を読み進めて自然言語処理等に適したアルゴリズムをコーディングしていきたいと思っていますが、まだまだどうしていいかわからない事もいっぱいあると思うので、もしかしたら他のデータストラクチャーを作成して投稿するかもしれないです。あとは参考書を読み進めてPythonの面白いなと思う機能などがあれば、それもまとめて投稿しようと思っています。ではでは！
注：この投稿で書いてあるコードはいたって単純なテストしかしていない為上手く動作しないかもしれません。もし自分で使っていて何か問題があれば修正、編集していきます。このコードを使用する方、もしくは読んでいただいた方で何か足りない部分、効率的にできる方法等々ありましたらコメントかメールでご指摘してください。