Good evening everyone By saying my article is also total 400 view As far as I am happy, thank you m (_ _) m If it's hard to understand, you can comment (o ゚ o) no YO--
The challenge of using my summer vacation was also meaningful I'm sick. Summer vacation is over today I will be working from next week. Tomorrow and the day after tomorrow will be training for childcare and housework (laughs)
Find time if you can I would like to continue this activity, so please support me.
By the way, O (1) !? I don't know what to explain from there I will omit it because it will be bald (laugh)
If you look at the article by an expert, the point is for single item or for nesting or while + if. I felt like it would be O (1) if I quit (I wonder if it's okay to put the URL on my own. https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0
The other day, I made a stack with the following idea, https://qiita.com/AKpirion/items/f3d5b51ab2ee9080e9c6 For the time being, push / pop seems to have no problem in understanding O (1) as a description.
Now, for the implementation of min, when you run the min function, it is essential to use the for statement to find the minimum value from the stacked data. So, in order to satisfy O (1), I thought it would be good if I could update the box that stores the minimum value every time I push. Therefore, I added str_min to the initial value.
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") #Box to store the minimum value
The reason why self.str_min is set to float ("inf"), that is, infinity, is This is because the first pushed value can always be stored in str_min.
stack_min.py
def min_str(self, value):
#self.str_min = min(self.str_min,value)
if self.str_min > value: #Input value value is str_If it is smaller than min, str_update min
self.str_min = value #self.str_min <If it is value, do nothing and return
return self.str_min
Personally, I think you can do it with min () as shown in the comment just below def .. in the above figure. I wasn't confident when I was told O (1) !?, so I ran away with an if statement. Is there any way to check this !? I don't have time for the time being, so I'll go to Push.
stack_min.py
def push(self, value):
if self.ptr >= self.capa:
raise top.full
self.str[self.ptr] = value #Push data to str!
top.min_str(self, value) #Pushed data and str_Compare with min and update minimum value
self.ptr += 1
The description of Push is basically the same as before, By inserting top.min_str (self, value), the minimum value can be updated every time Push is performed. It was good, it seems that the trouble of searching can be simplified (*'艸 ｀)
And the last time you call min I needed a little ingenuity. For now, take a look at the code below.
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"))) #Compare infinity and minimum
else:
break
I can call min by typing 3 first, Since it is def min_str (self, value) If you don't put something in the value part, you will get an error. So I pushed infinity to make sure I could get the minimum value.
This time, there were no pictures with images, I'm sorry. I also wrote an article like this, so please do not hesitate to contact me.
Try implementing two stacks in one array in Python https://qiita.com/AKpirion/items/2e74eecd30063a01d2fc
Have a nice weekend ・ ω ・ ´) 尸
Recommended Posts