0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

1つの配列に 2 つのスタックを Python で実装してみる

Posted at

こんにちは、
初投稿から1晩経ちました。
196view 有難うございます。

特に嬉しかったのはコメント頂いたことです。
@shiracamus さん有難うございます。
嬉しかったです。サンプルのコードまで頂いて。
また改めて頂いたヒントで考える機会を設けたいと思います。

表題の件ですがどっかで、
聞いたことのある質問ですよね?
はい、チャレンジしちゃいました(笑)。

色々な指摘を頂きそうですが、
一旦は、先日の記述スタイルでやってみます。
いやいや、スタックって何 !? って人は
https://qiita.com/AKpirion/items/f3d5b51ab2ee9080e9c6
か、他の有識者の記事を参考願います。
いきなり全貌を書いちゃいます。

stack_x2.py
class top:
    class full(Exception):
        pass
    class empty(Exception):
        pass    
    
    def sel_ptr(self,sel):
        if sel == 0:
            self.ptr = self.ptr0
        else:
            self.ptr = self.ptr1
        return self.ptr
    
    def bak_ptr(self,sel):
        if sel == 0:
            self.ptr0 = self.ptr
        else:
            self.ptr1 = self.ptr

    def __init__(self,capacity:int = 8):
        self.str  = [None] * capacity
        self.capa = capacity/2
        self.ptr0 = 0
        self.ptr1 = 4
        self.ptr  = 0

    def push(self,value,sel):

        top.sel_ptr(self,sel)
        
        if (self.ptr >= self.capa and sel==0) or (self.ptr >= self.capa*2 and sel==1):
            raise top.full
        self.str[self.ptr] = value 
        print(self.str)
        self.ptr += 1
   
        top.bak_ptr(self,sel)     


    def pop(self,sel):
        if sel == 0:
            self.ptr = self.ptr0
        else:
            self.ptr = self.ptr1
            
        if self.ptr <= 4*sel:
            raise top.empty
        self.ptr -= 1
        if sel == 0:
            self.ptr0 = self.ptr
            print(f"ptr0 = {self.ptr0}")
        else:
            self.ptr1 = self.ptr
            print(f"ptr1 = {self.ptr1} ")
        return self.str[self.ptr]

test = top()

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

    if num == 1 :
        s = int(input("enter data: "))
        sel = int(input("select str: "))
        try:
            test.push(s,sel)
        except test.full:
            print("full!")
    elif num == 2:
        sel = int(input("select str: "))
        try:
            x = test.pop(sel)
            print(x)
        except test.empty:
            print("empty!")
    else:
        break

すいません、前提条件を伝えるのを忘れていました。
str: データを格納する箱
capa: str の深さ。なので、何個までデータを詰め込めるか。。です
ptr : ポインタです。str の何処にデータをPush し、どこから Pop するかを意味します。

今回は capa = 8 としました。
以下のイメージでやってみようと思います。
図1.PNG
図の左側にあるように取り急ぎ、従来通り箱を1 つ作ります。
あとは、0 <= ptr <= 3 の領域と 4 <= ptr <= 7 の領域で分けて
スタックにしてあげます。

見えます、見えます、皆さんの?マーク。

やり方は色々あると思いますが、
私は単に ptr を 2 つ用意(ptr0,ptr1)して、
0 <= ptr0 <= 3, 4 <= ptr1 <= 7 となるように
書き換えればいいのでは?っと解釈しました。

じゃあ、おっさん、何したん!?
ってなると思いますので、順を追って見ていきましょう。

stack_x2.py
    def __init__(self,capacity:int = 8):
        self.str  = [None] * capacity
        self.capa = capacity/2  # 箱を二分割
        self.ptr0 = 0 # ポインタ 1つ目:0 <= ptr0 <= 3 で動作だから初期値 0
        self.ptr1 = 4 # ポインタ 2つ目:4 <= ptr1 <= 7 で動作だから初期値 4
        self.ptr  = 0 # ptr0 or ptr1 を選択後、ptr に代入してスタック処理へ

基本的には、Push/Pop を選択するときに、
どっちの箱に格納するか選択するようにします。
やり方としては self.ptr に ptr0 or ptr1 いずれか選択したほうを代入し、
今まで通り、self.ptr で push/pop するイメージです。
では、Push 行ってみましょう。

まず ptr に ptr0,ptr1 のどちらを代入するか決めます。
sel を使って、sel == 0 の時、ptr = ptr0、sel == 1 の時、ptr = ptr1 とします。
それが以下の記述です、前述の記述から抜き取ってみました。

stackx2.py
    def sel_ptr(self,sel):
        if sel == 0:
            self.ptr = self.ptr0
        else:
            self.ptr = self.ptr1
        return self.ptr

大丈夫そうですね。次は実際に Push をする本体です。

stackx2.py
    def push(self,value,sel):

        top.sel_ptr(self,sel)
        
        if (self.ptr >= self.capa and sel==0) or (self.ptr >= self.capa*2 and sel==1):
            raise top.full
        self.str[self.ptr] = value 
        print(self.str)
        self.ptr += 1
   
        top.bak_ptr(self,sel) 

ptr を ptr0 or ptr1 の どちらかを代入した後は、
選択した 1つ目or2つ目の箱が、 Full か否かを
if 文でチェックする必要があります。
抜き出してみます。

stackx2.py
   #sel == 0 で一つ目の箱を選択した場合  #sel == 0 で一つ目の箱を選択した場合
if (self.ptr >= self.capa and sel==0) or (self.ptr >= self.capa*2 and sel==1):

Full か否かを確認出来たら、
従来通り、Push します。ここで終わりと思いきや、ちょっと Time!
Push は ptr をインクリメントしなくてはいけないので、
Push の処理が終わった後に ptr0 or ptr1 にインクリメントした情報を
アップデートしてあげないとスタックになりません。

そのため、Push 処理の最後には以下を追加してあげる必要があります。
記述では top.bak_ptr(self,sel) っとありますが、やっていることは
以下の処理です。

stackx2.py
    def bak_ptr(self,sel):
        if sel == 0:
            self.ptr0 = self.ptr
        else:
            self.ptr1 = self.ptr

最後は Pop です。
Push と、それほど変わりません。
ptr の選択 => Empty の有無を確認 => ptr の Update => return value です。

stackx2.py
    def pop(self,sel):
        if sel == 0:
            self.ptr = self.ptr0
        else:
            self.ptr = self.ptr1
            
        if self.ptr <= 4*sel:
            raise top.empty

        self.ptr -= 1

        if sel == 0:
            self.ptr0 = self.ptr
            print(f"ptr0 = {self.ptr0}")
        else:
            self.ptr1 = self.ptr
            print(f"ptr1 = {self.ptr1} ")
        return self.str[self.ptr]

いかがだったでしょうか。
Pop の記述に関する説明は省いてしまいましたが、
Push が分かれば何とかなるかと(笑)

感触としては、Full / Empty を判断する条件を ptr0 ver , ptr1 ver と
条件分けしてあげることが出来れば、従来のスタックの記述を流用することで
乗り切れるのかなっと思いました。

説明が雑!, 足りない!,分かりにくい!
しかも間違ってるよ、色々!!

大変申し訳ありません。
コメント頂ければ修正、追記します。m(_ _)m

0
1
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?