こんにちは、
初投稿から1晩経ちました。
196view 有難うございます。
特に嬉しかったのはコメント頂いたことです。
@shiracamus さん有難うございます。
嬉しかったです。サンプルのコードまで頂いて。
また改めて頂いたヒントで考える機会を設けたいと思います。
表題の件ですがどっかで、
聞いたことのある質問ですよね？
はい、チャレンジしちゃいました(笑)。
色々な指摘を頂きそうですが、
一旦は、先日の記述スタイルでやってみます。
いやいや、スタックって何 !? って人は
https://qiita.com/AKpirion/items/f3d5b51ab2ee9080e9c6
か、他の有識者の記事を参考願います。
いきなり全貌を書いちゃいます。
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 つ作ります。
あとは、0 <= ptr <= 3 の領域と 4 <= ptr <= 7 の領域で分けて
スタックにしてあげます。
見えます、見えます、皆さんの？マーク。
やり方は色々あると思いますが、
私は単に ptr を 2 つ用意(ptr0,ptr1)して、
0 <= ptr0 <= 3, 4 <= ptr1 <= 7 となるように
書き換えればいいのでは？っと解釈しました。
じゃあ、おっさん、何したん!?
ってなると思いますので、順を追って見ていきましょう。
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 とします。
それが以下の記述です、前述の記述から抜き取ってみました。
def sel_ptr(self,sel):
if sel == 0:
self.ptr = self.ptr0
else:
self.ptr = self.ptr1
return self.ptr
大丈夫そうですね。次は実際に Push をする本体です。
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 文でチェックする必要があります。
抜き出してみます。
#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) っとありますが、やっていることは
以下の処理です。
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 です。
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