【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
第4章スタックとキュー
本章では、データを一時的に蓄えるためのデータ構造である、スタックとキューを学習します。
(一時的に蓄えるためのデータというものがどういうものかピンときませんが…)
スタックとは
スタックはデータを一時的に蓄えるためのデータ構造の一つです。データの出し入れは後入れ先出しで行われます。(最後に入れたデータが最初に取り出される)
スタックに入れる操作はプッシュ取り出す操作はポップと呼ばれます。
プッシュ、ポップが行われる最も上側を頂上、反対側を底と呼びます。
スタックの実現
実現には、スタック本体用の配列(str)、スタックの容量(capacity)、スタックのポインタ(ptr)の三つを必要とします。
str：list型で、プッシュされたデータを格納する本体用の配列。
capacity：容量を表すint型の整数値で、len(stk)と一致する。
ptr：スタックに積まれているデータの個数を表す整数値。スタックが空であれば0に、満杯であれば、capacityと同じ値になる。
#固定長スタッククラス
from typing import Any
class FixedStack:
"""固定長スタッククラス"""
class Empty(Exception):
"""空のFixedStackに対して、popあるいはpeekが呼び出されたときに送出する例外"""
pass
class Full(Exception):
"""満杯のFixedStackに対してpushが呼びだされたときに送出する例外"""
pass
def __init__(self, capacity: int = 256) -> None:
"""初期化"""
self.stk = [None] * capacity #スタックの本体
self.capacity = capacity #スタックの容量
self.ptr = 0 #スタックポインタ
def __len__(self) -> int:
"""スタックに積まれているデータ数を返す"""
return self.ptr
def is_empty(self) -> bool:
"""スタックは空であるか"""
return self.ptr <= 0
def is_full(self) -> bool:
"""スタックは満杯か"""
return self.ptr >= self.capacity
def push(self, value: Any) -> None:
"""スタックにvalueをプッシュ"""
if self.is_full():
raise FixedStack.Full
self.stk[self.ptr] = value
self.ptr += 1
def pop(self) -> Any:
"""スタックからデータをポップ(頂上のデータを取り出す)"""
if self.is_empty():
raise FixedStack.Empty
self.ptr -= 1
return self.stk[self.ptr]
def peek(self) -> Any:
"""スタックからデータをピーク(頂上のデータをのぞき見)"""
if self.is_empty():
raise FixedStack.Empty
return self.stk[self.ptr - 1]
def clear(self) -> None:
"""スタックを空にする(全データの削除)"""
self.ptr = 0
def find(self, value: Any) -> Any:
"""スタックからvalueを探して添字(見つからなければ-1)を返す"""
for i in range(self.ptr - 1, -1, -1): #頂上側から線形探索
if self.stk[i] == value:
return i #探索成功
return -1 #探索失敗
def count(self, value: Any) -> bool:
"""スタックに含まれるvalueの個数を返す"""
c = 0
for i in range(self.ptr): #底側から線形探索
if self.stk[i] == value:
c += 1 #入っている
return c
def __contains__(self, value: Any) -> bool:
"""スタックにvalueは含まれているか"""
return self.count(value)
def dump(self) -> None:
"""ダンプ(スタック内の全データを表示)"""
if self.is_empty():
print('スタックは空です。')
else:
print(self.stk[:self.ptr])
(途中でインデントエラーが出たりしていたので、どこがどう悪いかわかる人がいればコメントください）
#固定長スタックFixedStackの利用例
from enum import Enum
#from fixed_stack import FixedStack
Menu = Enum('Menu', ['プッシュ', 'ポップ', 'ピーク', '探索', 'ダンプ', '終了'])
def select_menu() -> Menu:
"""メニュー選択"""
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep=' ', end='' )
n = int(input('：'))
if 1 <= n <= len(Menu):
return Menu(n)
s = FixedStack(64) #最大64個プッシュできるスタック
while True:
print(f'現在のデータ数：{len(s)} / {s.capacity}')
menu = select_menu() #メニュー選択
if menu == Menu.プッシュ: #プッシュ
x = int(input('データ：'))
try:
s.push(x)
except FixedStack.Full:
print('スタックが満杯です。')
elif menu == Menu.ポップ: #ポップ
try:
x = s.pop()
print(f'ポップしたデータは{x}です。')
except FixedStack.Empty:
print('スタックが空です。')
elif menu == Menu.ピーク: #ピーク
try:
x = s.peek()
print(f'ピークしたデータは{x}です。')
except FixedStack.Empty:
print('スタックが空です。')
elif menu == Menu.探索: #探索
x = int(input('値：'))
if x in s:
print(f'{s.count(x)}個含まれ先頭の位置は{s.find(x)}です。')
else:
print('その値は含まれません。')
elif menu == Menu.ダンプ:
s.dump()
else:
break
| コラム4-1 例外処理(その1) |
|---|
プログラムの実行中のエラーは、例外というメッセージとして送出されます。例外を捕捉して対処を行う例外処理を行うと、エラーからの回復によってプログラムの実行の中断を回避できます。
例外処理は、本来の処理のコードと、エラー発生時の対処のコードを分離できる点が優れてた特徴の一つで、try文を使います。
try：本来の処理
except：例外の捕捉と対処
else：捕捉しなかった
finally：後始末
| コラム4-2 例外処理(その2) |
|---|
例外はプログラムによって意図的に送出することが可能で、raise文を使います。
ValueErrorやZeroDivisionErrorクラスなどは標準組み込み例外と呼ばれます。プログラマが定義するユーザー定義例外は、Exceptionクラスあるいは、その派生クラスから派生するのが原則だそうです。
| コラム4-3 __len__メソッドと__contains__メソッド |
|---|
pythonでは、先頭と末尾が__となっているめそどでゃ特別な意味が与えられます。
__len__メソッド：クラスにこのメソッドを定義すると、そのクラス型のインスタンスをlen関数に渡せるようになります。
obj.__len__() は len(obj)と記述できます。
__contains__メソッド：このメソッドを定義すると、そのクラス型のインスタンスに対して帰属性判定演算子のin演算子を適用できます。
obj.__contains__(x)はx in objと記述ができます。
| コラム4-4 collections.dequeを用いたスタックの実現 |
|---|
pythonの組み込みコンテナは、collectionsモジュールで、様々なコンテナが提供されています。
(namedtuple,deque,ChainMap,Counter,OrderDict,defaultdict,UserDict,UserList,UserStringなど)
このうちdequeを活用するとスタックを簡潔に実現できます。
deque：両端における要素の追加・削除が容易に行えるデータ構造のデック(deque)を実現するコンテナで、主要な属性とメソッドの仕様は次の通りです。
maxlen：最大長を表す読出し専用の属性で、制限されていなければNone
append(x)：x末尾に追加するメソッド
appendleft(x)：xを先頭に追加するメソッド
clear()：全要素を削除して長さを0にするメソッド
copy()：浅いコピーを生成
count(x)：xと等しい要素をカウント
extend(iterable)：イテラブルな引数から得られる要素を末尾側に追加して拡張
extendleft(iterable)：イテラブルな引数から得られる要素を先頭側に追加して拡張
index(x[, start[, stop]]])：インデックスstartからstopの両端を含む範囲でxで最も先頭側の位置を返却。見つからなければValueErrorを送出
insert(i, x)：xをiの位置に挿入。長さに制限があるときにそれを超えた場合IndexErrorを送出
pop()：末尾から要素を1個削除して、その要素を返却。要素が1個も存在しない場合はIndexErrorを送出
popleft()：先頭から要素を1個削除して、その要素を返却。要素が1個も存在しない場合はIndexErrorを送出
remove(value)：最初に現れるvalueを削除。要素がない場合はValueErrorを送出
reverse()：要素をインプレースに反転してNoneを返却
rotate(n=1)：要素全体でnステップだけ右に回転。nが負であれば、左に回転。
以上に加えて、イテレーションや、pickle len(d)、reversed(d)、copy.copy(d)、copy.deep、copy(d)、in演算子による帰属性判定、d[-1]などの形式での添字による参照がサポートされます。
両端へのアクセスはO(1)ですが、中央部分へのアクセスはO(n)と遅くなるため、添字による任意の要素へのランダムアクセスには向きません。
次にdequeを利用した例として、プログラムを書きます。使用は本文で作成したクラスFixedStackと同じです。
標準ライブラリは高速な動作が期待できること、プログラムがシンプルであることなどの理由からクラスFixedStackよりも優れていますが、データ構造の学習にはクラスFixedStackの理解が必要です。
#固定長スタッククラス(collections.dequeを利用)
from typing import Any
from collections import deque
class Stack:
"""固定長スタッククラス(collections.dequeを利用)"""
def __init__(self, maxlen: int = 256) -> None:
"""初期化"""
self.capacity = maxlen
self.__stk = deque([], maxlen)
def __len__(self) -> int:
"""スタックに積まれているデータ数を返す"""
return len(self.__stk)
def is_empty(self) -> bool:
"""スタックは空であるか"""
return not self.__stk
def is_full(self) -> bool:
"""スタックは満杯か"""
return len(self.__stk) == self.__stk.maxlen
def push(self, value: Any) -> None:
"""スタックにvalueをプッシュ"""
self.__stk.append(value)
def pop(self) -> Any:
"""スタックからデータをポップ(頂上のデータを取り出す)"""
return self.__stk.clear()
def peek(self) -> Any:
"""スタックからデータをピーク(頂上のデータをのぞき見)"""
return self.__stk[-1]
def clear(self) -> None:
"""スタックを空にする(全データの削除)"""
def find(self, value: Any) -> Any:
"""スタックからvalueを探して添字(見つからなければ-1)を返す"""
try:
return self.__stk.index(value)
except ValueError:
return -1
def count(self, value: Any) -> int:
"""スタックに含まれるvalueの個数を返す"""
return self.__stk.count(value)
def __contains__(self, value: Any) -> bool:
"""スタックにvalueは含まれているか"""
return self.count(value)
def dump(self) -> int:
"""ダンプ(スタック内の全データを底→頂上の順に表示)"""
print(list(self.__stk))
実行例は次の通りです。
#固定長スタックStackの利用例
from enum import Enum
#from fixed_stack import FixedStack
Menu = Enum('Menu', ['プッシュ', 'ポップ', 'ピーク', '探索', 'ダンプ', '終了'])
def select_menu() -> Menu:
"""メニュー選択"""
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep=' ', end='' )
n = int(input('：'))
if 1 <= n <= len(Menu):
return Menu(n)
s = Stack(64) #最大64個プッシュできるスタック
while True:
print(f'現在のデータ数：{len(s)} / {s.capacity}')
menu = select_menu() #メニュー選択
if menu == Menu.プッシュ: #プッシュ
x = int(input('データ：'))
try:
s.push(x)
except FixedStack.Full:
print('スタックが満杯です。')
elif menu == Menu.ポップ: #ポップ
try:
x = s.pop()
print(f'ポップしたデータは{x}です。')
except FixedStack.Empty:
print('スタックが空です。')
elif menu == Menu.ピーク: #ピーク
try:
x = s.peek()
print(f'ピークしたデータは{x}です。')
except FixedStack.Empty:
print('スタックが空です。')
elif menu == Menu.探索: #探索
x = int(input('値：'))
if x in s:
print(f'{s.count(x)}個含まれ先頭の位置は{s.find(x)}です。')
else:
print('その値は含まれません。')
elif menu == Menu.ダンプ:
s.dump()
else:
break
本日は以上です。ありがとうございました。
スタックがどのような形で活用されるかはよくわかりませんが、4章が終わるころには理解していたいですね。