【Python】スタック【アルゴリズム】

2023年1月11日

Pythonでアルゴリズムのスタックの解説をします。

スタック

スタック(stack)はデータを一時的に蓄えるためのデータ構造のひとつです。

スタックのデータの出し入れは後入れ先出し(LIFO/Last In First Out)です。

つまり最後に入れたデータが最初に取り出されます。

プッシュとポップ

スタックにデータを入れる操作をプッシュ(push)、データを取り出す操作をポップ(pop)といいます。

スタックにおいてプッシュやポップが行われる上側を頂上(top)といい、その反対側を底(bottom)といいます。

下の図はプッシュとポップの操作を表したもので、データを入れるのも取り出すのも頂上で行われています。

なおプッシュすることを積むとも言われています。

プッシュされたデータは頂上に積まれて、ポップすることで最後にプッシュされた頂上のデータが取り出されます。

スタックを実現するプログラムの解説

スタックを実現するプログラムを考えます。

なお、今回は基礎を学習するためにスタックの容量(積める最大データ数)を固定します。

スタック本体の配列stack

プッシュされたデータを格納するスタック本体用のlist型の配列です。

下の図のように添え字0の要素をスタックの底とすることで、最初にプッシュされるデータの格納先をstack[0]で表せます。

スタックの容量capacity

スタックの容量(スタックに積める最大データ数)を表すint型の整数値です。

capacityは配列stackの要素数なのでlen(stack)と一致します。

スタックポインタpointer

スタックに積まれているデータ数を表します。

この値はスタックポインタと呼ぶことにします。

pointerの値はスタックが空なら0、満杯ならcapacityと一致します。

pointerの値がデータのある次の要素になっているのは添え字が要素数-1であるためです。

下の図は容量8のスタックに4個のデータが積まれている状態を表したものです。

最初にプッシュされた値は底のstack[0]である15で、最後にプッシュされた値は頂上のstack[pointer – 1]である42です。

黒丸で囲んだ添え字がpointerの値です。

pointerの値はプッシュするとインクリメントされ、ポップするとデクリメントされます。

例外クラスEmptyとFull

# 固定長スタッククラス

from typing import Any

class FixedStack:
    """固定長スタッククラス"""

    class Empty(Exception):
        """空のFixedStackに対してpopやprint_topが呼び出された時に送出する例外"""
        pass

    class Full(Exception):
        """満杯のFixedStackに対してpushが呼び出された時に送出する例外"""
        pass

Emptyは空のスタックに対してpopメソッドやprint_topメソッドが呼び出された時に送出する例外です。

Fullは満杯のスタックに対してpushメソッドが呼び出された時に送出する例外です。

初期化__init__

def __init__(self, capacity: int = 256) -> None:
        """初期化"""
        self.stack = [None] * capacity  # スタック本体
        self.capacity = capacity        # スタックの容量
        self.pointer = 0                # スタックポインタ

__init__メソッドではスタック本体用の配列を生成するための準備をします。

仮引数capacityをスタックの容量を表すフィールドcapacityにコピーします。

スタック本体stackは、要素数がcapacityで全要素がNoneのlist型の配列として初期化します。

生成時はスタックは空なのでスタックポインタpointerの値は0になります。

積まれたデータ数__len__

def __len__(self) -> int:
        """スタックに積まれているデータ数を返却"""
        return self.pointer

__len__メソッドではスタックに積まれているデータ数を返却するメソッドです。

スタックポインタpointerの値をそのまま返します。

このメソッドにより、スタックsの要素数をs.__len__()だけでなくlen(s)でも調べられます。

空であるか判定するis_empty

def is_empty(self) -> bool:
        """スタックは空であるか"""
        return self.pointer <= 0

is_emptyメソッドではスタックが空である(データが1個も積まれていない)かを判定するメソッドです。

空であればTrue、空でなければFalseを返却します。

満杯であるか判定するis_full

def is_full(self) -> bool:
        """スタックは満杯であるか"""
        return self.pointer >= self.capacity

is_fullメソッドではスタックが満杯である(これ以上データがプッシュできない)かを判定するメソッドです。

満杯であればTrue、満杯でなければFalseを返却します。

なお空の判定はself.pointer == 0、満杯の判定はself.pointer == self.capacityでも行えます。

ただし何かしらの理由でpointerの値が0未満やcapacityより大きくなる可能性もあるためコードではそれらに対応させています。

プッシュpush

def push(self, value: Any) -> None:
        """スタックにvalueをプッシュ"""
        if self.is_full():   # スタックは満杯
            raise FixedStack.Full
        self.stack[self.pointer] = value
        self.pointer += 1

pushメソッドではスタックにデータvalueをプッシュするメソッドです。

ただしスタックが満杯の時は例外FixedStack.Fullを送出します。

満杯でない時、受け取ったデータvalueをプッシュ前の頂上の次の要素であるstack[pointer]に格納します。

そしてスタックポインタpointerをインクリメントします。

下の図では4個のデータが積まれているスタックに29をプッシュする様子を表したものです。

ポップpop

def pop(self) -> Any:
        """スタックからデータをポップ(頂上のデータを返却)"""
        if self.is_empty():  # スタックは空
            raise FixedStack.Empty
        self.pointer -= 1
        return self.stack[self.pointer]

popメソッドではスタックの頂上からデータをポップしてその値を返却するメソッドです。

ただしスタックが空の時は例外FixedStack.Emptyを送出します。

空でない時、スタックポインタpointerをデクリメントします。

そしてstack[pointer]に格納されている値を返却します。

上の図では5個のデータが積まれているスタックからポップして29を返却する様子を表したものです。

頂上のデータを表示print_top

def print_top(self) -> Any:
        """スタックの頂上のデータを表示"""
        if self.is_empty():  # スタックは空
            raise FixedStack.Empty
        return self.stack[self.pointer - 1]

print_topメソッドではスタックの頂上のデータ(次にポップされるデータ)を表示するメソッドです。

ただしスタックが空の時は例外FixedStack.Emptyを送出します。

空でない時、頂上の値であるstack[pointer – 1]の値を返却します。

値を返却するだけなのでスタックポインタの値は変化しません。

スタックを空にする(全データ削除)clear

def clear(self) -> None:
        """スタックを空にする(全データを削除)"""
        self.pointer = 0

clearメソッドではスタックに積まれているすべてのデータを削除するメソッドです。

全データを削除といっても、スタックポインタpointerの値を0にするだけです。

プッシュやポップなどのメソッドはスタックポインタを使って行うため、要素の値を変更する必要はありません。

値を探索するsearch

def search(self, value: Any) -> Any:
        """スタックからvalueを探索して添え字(見つからなければ-1)を返却"""
        for i in range(self.pointer - 1, -1, -1):  # 頂上側から線形探索
            if self.stack[i] == value:
                return i  # 探索成功
        return -1         # 探索失敗

searchメソッドではスタック本体の配列stackにvalueと同じ値が含まれるかを探索するメソッドです。

含まれている場合は見つけた要素の添え字を返却し、見つからなかった場合は-1を返却します。

下の図はsearchメソッドによる探索の仕方を表したものです。

探索は頂上側から底側に向かって線形探索します。

つまり配列の添え字の大きいほうから小さいほうに向かって探索します。

上の図は23を探索していますが、23は添え字2と4の2箇所にあります。

探索は頂上側から行われるので、より頂上側にある23の添え字4を返却します。

このような探索方法にしているのは、ポップされるのは頂上側から取り出されるという特徴を見越しているからです。

要素をカウントするcount

def count(self, value: Any) -> bool:
        """スタックに含まれるvalueの個数を返却"""
        counter = 0
        for i in range(self.pointer):  # 底側から線形探索
            if self.stack[i] == value:
                counter += 1           # 入っていた
        return counter

countメソッドではスタック本体の配列stackに含まれるvalueの個数を求めて返却するメソッドです。

上の図のスタックであれば23をカウントすると2が返却されます。

データが含まれるかを判定する__contains__

def __contains__(self, value: Any) -> bool:
        """スタックにvalueは含まれているか"""
        return self.count(value)

__contains__メソッドではスタック本体の配列stackにvalueが含まれているかを判定するメソッドです。

含まれていればTrue、含まれていなければFalseを返却します。

このメソッドにより、スタックsにxが含まれているかの判定がs.__contains__(x)だけでなく、

帰属性判定演算子のin演算子を使ってx in sでも調べられます。

全データの表示print

def print(self) -> None:
        """スタックの全データを底から頂上の順に表示"""
        if self.is_empty():  # スタックは空
            print('スタックは空です。')
        else:
            print(self.stack[:self.pointer])

printメソッドではスタックに積まれているすべてのデータを底から頂上の順に表示するメソッドです。

ただしスタックが空であれば「スタックは空です。」と表示します。

スタックを実現するプログラムは以下の通りです。

スタックを実現するプログラム

# 固定長スタッククラス

from typing import Any

class FixedStack:
    """固定長スタッククラス"""

    class Empty(Exception):
        """空のFixedStackに対してpopやprint_topが呼び出された時に送出する例外"""
        pass

    class Full(Exception):
        """満杯のFixedStackに対してpushが呼び出された時に送出する例外"""
        pass

    def __init__(self, capacity: int = 256) -> None:
        """初期化"""
        self.stack = [None] * capacity  # スタック本体
        self.capacity = capacity        # スタックの容量
        self.pointer = 0                # スタックポインタ

    def __len__(self) -> int:
        """スタックに積まれているデータ数を返却"""
        return self.pointer

    def is_empty(self) -> bool:
        """スタックは空であるか"""
        return self.pointer <= 0

    def is_full(self) -> bool:
        """スタックは満杯であるか"""
        return self.pointer >= self.capacity

    def push(self, value: Any) -> None:
        """スタックにvalueをプッシュ"""
        if self.is_full():   # スタックは満杯
            raise FixedStack.Full
        self.stack[self.pointer] = value
        self.pointer += 1

    def pop(self) -> Any:
        """スタックからデータをポップ(頂上のデータを返却)"""
        if self.is_empty():  # スタックは空
            raise FixedStack.Empty
        self.pointer -= 1
        return self.stack[self.pointer]

    def print_top(self) -> Any:
        """スタックの頂上のデータを表示"""
        if self.is_empty():  # スタックは空
            raise FixedStack.Empty
        return self.stack[self.pointer - 1]

    def clear(self) -> None:
        """スタックを空にする(全データを削除)"""
        self.pointer = 0

    def search(self, value: Any) -> Any:
        """スタックからvalueを探索して添え字(見つからなければ-1)を返却"""
        for i in range(self.pointer - 1, -1, -1):  # 頂上側から線形探索
            if self.stack[i] == value:
                return i  # 探索成功
        return -1         # 探索失敗

    def count(self, value: Any) -> bool:
        """スタックに含まれるvalueの個数を返却"""
        counter = 0
        for i in range(self.pointer):  # 底側から線形探索
            if self.stack[i] == value:
                counter += 1           # 入っていた
        return counter

    def __contains__(self, value: Any) -> bool:
        """スタックにvalueは含まれているか"""
        return self.count(value)

    def print(self) -> None:
        """スタックの全データを底から頂上の順に表示"""
        if self.is_empty():  # スタックは空
            print('スタックは空です。')
        else:
            print(self.stack[:self.pointer])

このプログラムは「fixed_stack.py」という名前で保存してください。

スタックを利用するプログラム

コード例

# 固定長スタッククラス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.プッシュ:      # プッシュ
        push_value = int(input('データ : '))
        try:
            s.push(push_value)
        except FixedStack.Full:
            print('スタックが満杯です。')

    elif menu == Menu.ポップ:      # ポップ
        try:
            pop_value = s.pop()
            print(f'ポップしたデータは{pop_value}です。')
        except FixedStack.Empty:
            print('スタックが空です。')

    elif menu == Menu.頂上を表示:  # 頂上を表示
        try:
            top_value = s.print_top()
            print(f'頂上のデータは{top_value}です。')
        except FixedStack.Empty:
            print('スタックが空です。')

    elif menu == Menu.探索:        # 探索
        search_value = int(input('値 : '))
        if search_value in s:
            print(f'{search_value}は{s.count(search_value)}個含まれていて、先頭の位置は{s.search(search_value)}です。')
        else:
            print('その値は含まれていません。')

    elif menu == Menu.全表示:      # 全表示
        s.print()

    else:                          # 終了
        break

実行結果

現在のデータ数 : 0 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 1
現在のデータ数 : 1 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 2
現在のデータ数 : 2 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 3
現在のデータ数 : 3 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 2
現在のデータ数 : 4 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 5
現在のデータ数 : 5 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 5
[1, 2, 3, 2, 5]
現在のデータ数 : 5 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 4
値 : 2
2は2個含まれていて、先頭の位置は3です。
現在のデータ数 : 5 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 3
頂上のデータは5です。
現在のデータ数 : 5 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 2
ポップしたデータは5です。
現在のデータ数 : 4 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 2
ポップしたデータは2です。
現在のデータ数 : 3 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 5
[1, 2, 3]
現在のデータ数 : 3 / 64
(1)プッシュ (2)ポップ (3)頂上を表示 (4)探索 (5)全表示 (6)終了 : 6

このプログラムは「fixed_stack_test.py」という名前で「fixed_stack.py」と同じフォルダに保存してください。

アルゴリズム

Posted by ほりえりお