スタック 2個 でキューを実現

18131 ワード
Python Python テキストリンク

こんばんは。

いつも応援有難うございます。
自分の記事が皆様の役に少しでも役に立っているようで
とっても嬉しいです(≧▽≦)

自分の理解をまとめる事は自分自身の理解の整理にもなるので
一石二鳥ですね!( *´艸｀)

さて表題の件ですが、
面白い題材ですよね。
早速やっていきましょう。
皆さんはどんな解放をイメージしましたか？

私は Push、Pop 専用のスタックをそれぞれ用意することで実現できると思いました。
例えばですが、Push するときは Push 専用の領域に貯めます。
Pop の際は、Push 専用から Pop 専用にデータを移し替えます。
これでイケる!?????
取りあえず順を追ってイメージを作りましょう。

1.Push の場合
Push 専用機にデータをシコタマ貯めます。
データは A => B => C => D => E => F の順番に push しました。
問題ないですね。
Pop 専用機も覗いてみましょう。
念のためアドレスを 0 から 5 まで振ってありますが、一応、カラです。

2.Pop の場合
Push 専用機からスタックの要領でデータを取り出し、
Pop 専用機に Push していきます。
この状態だと Pop 専用機から見ると、F => E => D => C => B => A の順番で
Push することになるので、こんな感じにありませんか？

あとはスタックの要領で Pop 専用機から pop すれば、
動きはスタックですが、システムの出力結果はキューと同じになりませんか？

何となくイメージが出来たので書いていきましょう。
ベースは前回の記事を元にしています。
https://qiita.com/AKpirion/items/b1bad123aebe72f35a77

stack_x2_queue.py
    def __init__(self,size):
        self.INstr = []  #Push 専用機
        self.OUTstr = [] #Pop 専用機
        self.size = size

全く問題になりませんね、次です。
取りあえず、トリガーは置いておいて、
Push 専用機(or Pop 専用機)のデータを
根こそぎ Pop 専用機(or Push 専用機)へ転送する記述を使いたくなりました。

stack_x2_queue.py
    #Push専用機からPop専用機への移動
    def trans_IN2OUT(self):
        #既存で格納しているデータ長だけ根こそぎ移動
        for _ in range(len(self.INstr)):
            self.OUTstr.append(self.INstr.pop())
    #Pop専用機からPush専用機への移動
    def trans_OUT2IN(self):
        #既存で格納しているデータ長だけ根こそぎ移動
        for _ in range(len(self.OUTstr)):
            self.INstr.append(self.OUTstr.pop())

取りあえず、書きたいことを書いたはいいものの、
どうしましょうね(*´ω｀)
辻褄を合わせて行くしかないですね(笑)

まずは Push から行きましょう。
自分は、Push 専用機がどれだけデータが居ようと居なくても、
Pop 専用機のデータ長が 0 であれば、Push 専用機に push できるれば良いと考えました。
もし、Pop 専用機のデータ長が 0 じゃなければ、
def trans_OUT2IN(self) を使って、Pop 専用機から Push 専用機に
全てを移動します。
そのあとは再帰を使って push できるように組みました。

stack_x2_queue.py
    def push(self,value):
        # Push 専用機が Full か否かを確認
        if len(self.INstr) >= self.size:
        # Full なら例外処理
            raise Stack.full
        # Pop 専用機がカラかどうか判断
        if len(self.OUTstr) == 0:
        # カラなら Push 専用機に push!
            self.INstr.append(value)
        else:
        # カラじゃなければ Pop 専用機からデータを全て Push 専用機に移動
            Stack.trans_OUT2IN(self)
        # 再帰を使って、If len(self.OUTstr) == 0 にデータを代入して push 
            Stack.push(self,value)

追加したい機能を def で追加してって、
穴埋めを、それぞれの def 内の記述を調整して対応してく。。
こんなやり方で良いのでしょうか？( ﾟΩﾟ) ポカーン ( ﾟДﾟy)y !??
きっと、論理的な対処法があるんでしょうね、勉強したいなー

まぁ、次行きますか、pop です。

基本的には push の逆です。
Push 専用機に格納されているデータ長が 0 なら、
Pop 専用機から pop を行います。
上記以外の場合は、Push 専用機から全てのデータを
Pop 専用機へ移動させます。
以下のような感じになると思います。

stack_x2_queue.py
    def pop(self):
        # Push 専用機がカラであれば Pop 専用機から pop
        if len(self.INstr) == 0:
            print(f"pop data is {self.OUTstr.pop()}")
        else:
        # Push 専用機から全てのデータを Pop 専用機へ移動
            Stack.trans_IN2OUT(self)
        # 再帰を使って、if len(self.INstr) == 0 の条件を再度呼び出す
            Stack.pop(self)

全体はこのような感じです。

stack_x2_queue.py
class Stack:
    class full(Exception):
        pass
    def __init__(self,size):
        self.INstr = []
        self.OUTstr = []
        self.size = size
    def push(self,value):
        if len(self.INstr) >= self.size:
            raise Stack.full
        if len(self.OUTstr) == 0:
            self.INstr.append(value)
        else:
            Stack.trans_OUT2IN(self)
            Stack.push(self,value)
    def pop(self):
        if len(self.INstr) == 0:
            print(f"pop data is {self.OUTstr.pop()}")
        else:
            Stack.trans_IN2OUT(self)
            Stack.pop(self)
    def view(self):
        print(self.INstr)
        print(self.OUTstr)
    def trans_IN2OUT(self):
        for _ in range(len(self.INstr)):
            self.OUTstr.append(self.INstr.pop())
    def trans_OUT2IN(self):
        for _ in range(len(self.OUTstr)):
            self.INstr.append(self.OUTstr.pop())

x = int(input("stack size is "))
test = Stack(x)  

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

    if num == 1:
        x = int(input("push data is "))
        try:
            test.push(x)
            test.view()
        except:
            print("Full!")
    elif num == 2:
        try:
            test.pop()
            test.view()
        except:
            print("Empty!")
    else:
        break

実行結果も載せておきます。

stack size is 4

1.push 2.pop: 1

push data is 1 # 1 を Push
[1]            # Push 専用機
[]             # Pop 専用機

1.push 2.pop: 1

push data is 2 # 2 を Push
[1, 2]         # Push 専用機
[]             # Pop 専用機

1.push 2.pop: 1

push data is 3 # 3 を Push
[1, 2, 3]      # Push 専用機
[]             # Pop 専用機

1.push 2.pop: 1

push data is 4 # 4 を Push
[1, 2, 3, 4]   # Push 専用機
[]             # Pop 専用機

1.push 2.pop: 2
pop data is 1  # Pop 専用機から 1 を pop
[]             # Push 専用機
[4, 3, 2]      # Pop 専用機

1.push 2.pop: 2
pop data is 2  # Pop 専用機から 2 を pop
[]             # Push 専用機
[4, 3]         # Pop 専用機

1.push 2.pop: 1

push data is 2 # Push 専用機にデータを戻して 2 を push
[3, 4, 2]      # Push 専用機
[]             # Pop 専用機

1.push 2.pop: 1

push data is 1
[3, 4, 2, 1]
[]

1.push 2.pop: 2
pop data is 3
[]
[1, 2, 4]

1.push 2.pop: 2
pop data is 4
[]
[1, 2]

1.push 2.pop: 2
pop data is 2
[]
[1]

1.push 2.pop: 2
pop data is 1
[]
[]

途中で補足をやめてしまいましたが、
Push, Pop の度に各専用機へ全てのデータを寄せてから
Push,Pop のアクションに移らないと汎用性の維持は難しいようです ( =ω=)y─┛○o｡

あとPush 専用機、Pop 専用機で定義した動きにおいて Full,Empty で error になるようであれば例外処理に入るので特にコレといった変更は必要ないです。

お疲れ様でした ^^) _旦~~

Cによる雲のストリーミング
連続的統合のためのUbuntuサーバ上でのGitサーバの設定