Python で作ったスタックに最小値(min) を返す機能を追加するが push/pop/min は基本 O(1) !!

皆様、こんばんは
私の記事も total 400 view と言うことで
嬉しい限りです、有難うございます m(_ _)m
分かりにくかったらコメント OK です(oﾟｪﾟo)ﾉYO--

私の夏休みを使ったチャレンジも意味があったと、
しみじみしています。今日で夏休みは終わりで
来週から仕事です。明日、明後日は育児、家事というなの修行です(笑)

出来れば時間を見つけて
この活動は続けたいので是非、応援宜しくお願い致します。

さて、O(1)!? ってことで、
そこから説明するのは私が分かっていないことを
バレてしまいますので省きます(笑)

有識者の方の記事を拝見すると、要は for 単品 or for のネスト or while + if を
やめれば O(1) になりそうな気がしました(勝手に URL 貼って良いのかな。まぁ、いっか)。
https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0

先日、以下の考え方でスタックを作りましたが、
https://qiita.com/AKpirion/items/f3d5b51ab2ee9080e9c6
取りあえず、記述としては push/pop は O(1) の理解で問題なさそうです。

さて、min の実装ですが、min 関数を走らした時点で、スタックしたデータから最小値を探し出すには for 文の使用は必須です。
なので、O(1) を満たす為には、Push の度に、最小値を格納する箱を更新できれば良いと思いました。
よって、初期値に str_min を追加しました。

stack_min.py

class top:
    def __init__(self, capacity: int = 5):
        self.str = [None] * capacity
        self.capa = capacity
        self.ptr = 0
        self.str_min = float("inf") #最小値を格納する箱

※@shiracamus さん、autopep8 やりました(笑)。初耳の方はググってみましょう

self.str_min を float("inf")、つまり無限大に設定しているのは、
最初に push した値を必ず str_min に格納できるからです。

stack_min.py

    def min_str(self, value):
        #self.str_min = min(self.str_min,value)
        if self.str_min > value: #入力値 value が str_min より小さければstr_min を更新
            self.str_min = value #self.str_min < value であれば何もしないで return
        return self.str_min

個人的には上図の def .. のすぐ下にあるコメントにあるように min() でやっても良いと思うんですけど、
本当に O(1)!? って言われると自信がないので、if 文で逃げました。
なんか確認方法あるんですか、これ!?
取りあえず時間がないので Push に行きます。

stack_min.py

    def push(self, value):
        if self.ptr >= self.capa:
            raise top.full
        self.str[self.ptr] = value  #str にデータを Push!
        top.min_str(self, value)    #Push したデータと str_min と比較し、最小値を更新
        self.ptr += 1

Push の記述は基本今まで通りなのですが、
top.min_str(self,value) を突っ込む事で Push する度に最小値を更新できるようにしました。
よかった、探す手間が簡略化できそうです( *´艸｀)

あとは最後に min を呼び出すときに
少し工夫が必要でした。
取りあえず、以下のコードを眺めてみてください。

stack_min.py

while True:
    num = int(input("select 1.push , 2.pop : , 3.min "))

    if num == 1:
        s = int(input("enter data: "))
        try:
            test.push(s)
        except test.full:
            print("full!")
    elif num == 2:
        try:
            x = test.pop()
            print(x)
        except test.empty:
            print("empty!")
    elif num == 3:
        print(test.min_str(float("inf"))) #無限大と最小値を比較
    else:
        break

最初に 3 を入力すると min を呼び出せるのですが、
def min_str(self,value) っとなっているので、
何かを value の個所にぶち込まないとエラーになります。
なので、私は無限大を突っ込んで、必ず最小値が必ず出せるようにしました。

今回は絵がイメージの絵が皆無でした、すいません。
あとは、こんな記事も書いてますので宜しければどうぞ

1つの配列に 2 つのスタックを Python で実装してみる
https://qiita.com/AKpirion/items/2e74eecd30063a01d2fc

それでは良い週末を・ω・´)尸

ところが、、2020/9/29　@neboccoさんのご指摘により、
前述の記述で不足分を指摘いただきました。
以下、コメントの抜粋です。

---

stackでは、pushは末尾に追加、popは末尾を削除、という操作になります。
https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF

よって先程示したような操作をすると、topに保持されたデータは以下のようになると思います。
push(3)
=> str = [3], str_min = 3
push(1)
=> str = [3, 1], str_min = 1
pop()
=> str = [3], str_min = 1
（strの中身がNoneになっている部分は描画を省いています。）

これだと1は既にpopされてstackには残っていないのに最小値には1が残ってしまう（正しい最小値は3）のではないでしょうか？

---

pop の際に最小値が抜けてしまったら、
min も更新しないとダメではないか!?
全くもって、死角でした、気付けなくて恥ずかしいです。
でも、教えてくれて有難うございます(´；ω；`)ｳｩｩ

では対策行ってみましょう。

例えば、
push(1)
push(2)
push(0)
push(2)
push(5)
push(2)
っと順に push したとします。
すると str 本体の中身は以下のようになります。

これとは別に最小値を管理する str_min を用意します。
ここに格納するのは、push の度に求めた最小値です。
下図をご覧ください、イメージを図にしました。

このようにしてあげれば、pop と同じように、str_min の上から順に値を拾えば、
どのタイミングで pop されたとしても簡単に最小値を拾える算段です。
ではでは、修正していきましょう。

stack_min_r2.py

class top:
    def __init__(self, capacity: int = 5):
        self.str = [None] * capacity
        self.capa = capacity
        self.ptr = 0
        
        self.min      = float("inf") #Pushデータが最小か否かを判断する基準
        self.str_min  = [None]*self.capa #最小値を管理するスタック

self.str_min と self.min の追加をしました。
self.min 用途については、以下の記述を見てもらったほうが早いかもしれません。

stack_min_r2.py

class top:

    def push(self, value):
        if self.ptr >= self.capa:
            raise top.full
        self.str[self.ptr] = value
        top.min_str(self, value)
        self.ptr += 1

    def min_str(self, value):
        #基準値 min と push value を比較
        #min の初期値は inf
        if self.min > value:
            #pushしたvalueの方が小さければstr_min格納
            self.str_min[self.ptr] = value 
            #基準値 min も最小値の value へ更新し、次の比較に使用する
            self.min = value
        else:
            #基準値 min が最小値を維持しているのであれば min を str_min に push
            self.str_min[self.ptr] = self.min

        return self.str_min[self.ptr-1]

最後の return self.str_min[self.ptr-1] のですが、
pop と同じ要領です。

このような勉強の機会をくださった @nebocco さんに感謝です。
本当に有難うございましたm(_ _)m

っというわけでコード全貌です。

stack_min_r2.py

class top:
    class full(Exception):
        pass

    class empty(Exception):
        pass

    def __init__(self, capacity: int = 5):
        self.str = [None] * capacity
        self.capa = capacity
        self.ptr = 0
        
        self.min      = float("inf")    
        self.str_min  = [None]*self.capa

    def push(self, value):
        if self.ptr >= self.capa:
            raise top.full
        self.str[self.ptr] = value
        top.min_str(self, value)
        self.ptr += 1

    def min_str(self, value):
        if self.min > value:
            self.str_min[self.ptr] = value
            self.min = value
        else:
            self.str_min[self.ptr] = self.min
        return self.str_min[self.ptr-1]

    def pop(self):
        if self.ptr <= 0:
            raise top.empty
        self.ptr -= 1
        return self.str[self.ptr]


test = top()

while True:
    num = int(input("select 1.push , 2.pop : , 3.min "))

    if num == 1:
        s = int(input("enter data: "))
        try:
            test.push(s)
        except test.full:
            print("full!")
    elif num == 2:
        try:
            x = test.pop()
            print(x)
        except test.empty:
            print("empty!")
    elif num == 3:
        print(test.min_str(float("inf")))
    else:
        break