こんばんは
皆様に色々とアドバイスを頂き続けて
そろそろ 2 週間が経とうとしています。
本当に有難うございます。m(_ _)m
まずは、スタックを用意し、それを改造してキューに持っていく
アプローチを取ろうと思います。
class Stack:
class full(Exception):
pass
def __init__(self,size):
#スタック本体
self.str = []
#スタック出来るデータ数を指定
self.size = size
def push(self,value):
#スタック本体 > 指定したデータ数の場合、例外処理
if len(self.str) >= self.size:
raise Stack.full
#特に問題なければ push
self.str.append(value)
def pop(self):
print(self.str.pop())
def view(self):
print(self.str)
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
いやはや、2周間前には思いつかなかった記述です(;´･ω･)
さて、ここからどうやって、キューに持っていきましょうか。
そもそも、スタックとキューの違いは何だったでしょうか。。
基本的には pop の動きが違います。
図にあるようにキューの場合は最初に保存したデータから取り出していきます。
push/pop をランダムに行うと、中身がゴチャゴチャニなるので、
何処からが最初のデータが分からなくなります。
この対策としてリングバッファの考え方があり、
何処が最初か管理することでキューを実現します。
。。せっかく python 使ってるので
簡単に出来ないでしょうか？？？
って事で、まずは、pop の性質を見直します。
num = [3,2,1]
for i in range(3):
print(f"num[{i}] = {num[i]}")
## 実行結果##
# num[0] = 3#
# num[1] = 2#
# num[2] = 1#
############
ではでは、pop 入れてみましょう。
キューをやりたいので、pop(0) とし、
First data を取り出してみます。
num = [3,2,1]
num.pop(0)
for i in range(2):
print(f"num[{i}] = {num[i]}")
## 実行結果##
# num[0] = 2#
# num[1] = 1#
############
[壁]*ﾟーﾟ)ん？
先頭の num[0] を pop 、つまり取り出して、
削除をした結果、残った要素が左詰めになった。
そうなんです、先頭を削除すると残った要素は、
また0から再配置されるのです。
なんだ、勝手にやってくれるならリングバッファ要らない!?
キューは基本的にスタックと同じでデータの取り出し、
書き込みの、いずれかを 1 アドレスに 1 回行うだけです。
なので、前述の stack で定義されている pop() 、末尾から必ず取り出す記述を
pop(0)、先頭から必ず取り出す記述に変えればキューになります。
class Stack:
class full(Exception):
pass
def __init__(self,size):
self.str = []
self.size = size
def push(self,value):
if len(self.str) >= self.size:
raise Stack.full
self.str.append(value)
def pop(self):
print(self.str.pop(0)) #ここだけ変更 !! 変更前) pop() 変更後) pop(0)
def view(self):
print(self.str)
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
以下、実行結果です。
push data is 4 #4 を push
[1, 2, 3, 4] #push 後のメモリの中身
1.push 2.pop: 2#2.pop を選択
1 #str[0]に格納されている 1 を pop
[2, 3, 4] #pop 後のメモリの中身
1.push 2.pop: 2#2.pop を選択
2 #str[0]に格納されている 1 を pop
[3, 4] #pop 後のメモリの中身
1.push 2.pop: 2
3
[4]
1.push 2.pop: 2
4
[]
1.push 2.pop: 2
Empty!
このような感じで、楽してキューが実現できました。
ん～、でもちゃんとリンクバッファを作って説明を
載せておいたほうが自分のためになる気がします。
よし、やろう！！いつの日か。。