Data Structureはいろいろありまして、それはどうやってPythonで実現できますかをシェアしていきます。
あまりにも多くて、これからどんどん更新していきたいと思っています。
今回はLinear Structureについて、(簡便のため今後LSと書きます。)
LSは簡単に言うと、電車や新幹線みたいな感じですね。また、LSには4種類に分けられて、
- Stack
- Queue
- Deque
- List
があります。今後一個一個で説明しますが、ざっくりって言うと、dataの増減方式が違います。どんなイメージというと、
例えば、あるデータがこのLSの頭からしか入れない、またはtailしか入れないなどがあります。
では、今回はStackというデータ構造、そしてpythonならどうやって実現するのかを説明します。
Stackとは？
簡単に説明すると、最初から入ったデータは最後でしか取り出せない。図のように4が一番早くStackに入り、そしてdog, True,8.4はどんどん上に重ねていきます。取り出し場合は、最後に入れた8.4は最初に取り出します。ようするにLast In First Out (LIFO)のこと。雑ですが、こういう感じですね。
じゃpythonならどうやってStackを実現できるでしょう。
pythonのlist objectでStackを実現します。
class Stack(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
StackはLS構造なので、新たな空なListを作って、一番右の要素はheadとし、一番左の要素はtailとします。
pushについて、Stackはheadしか入れないため、pythonのappendメソッドを採用します。
popもそのままpython自分のメソッドを利用します。
その他のメソッドについて、Stackを利用した応用問題のために追加しましたものです。
応用問題：左カッコと右カッコののマッチ問題
あるstr型{()[]}がありまして、左カッコと左カッコは一体マッチしているかどうかをチェックしてくれるプログラムを書きましょう。
答えは以下になります。[説明はまた後日で(多分
)]
def check_quotation(symbol):
obj = Stack()
pos = 0
result = True
while pos < len(symbol) and result:
if symbol[pos] in '([{':
obj.push(symbol[pos])
else:
if obj.isEmpty():
result = False
else:
top = obj.pop()
if not match(top, symbol[pos]):
result = False
pos += 1
if result and obj.isEmpty():
return True
else:
return False
def match(s1, s2):
a_1 ='([{'
a_2 =')]}'
return a_1.index(s1) == a_2.index(s2)
print(check_quotation('[][][][]{[]'))
次回はQueueについて更新していきたいと思っています。
では、最後まで見ていただき、ありがとうございました。