Try implementing two stacks in one array in Python
Hello, It's been one night since the first post. 196view Thank you.
I was particularly pleased with the comments. Thank you @shiracamus. I was happy. Get the sample code. In addition, I would like to provide an opportunity to think with the hints I received again.
Regarding the title, somewhere, You've heard this question, right? Yes, I challenged myself (laughs).
I'm sure you'll get a lot of suggestions, I will try it with the description style of the other day. No, what is a stack !? https://qiita.com/AKpirion/items/f3d5b51ab2ee9080e9c6 Or, please refer to the articles of other experts. Suddenly I will write the whole picture.
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
I'm sorry, I forgot to tell you the prerequisites. str: Box to store data capa: The depth of str. So how many data can be packed? .. is ptr: Pointer. It means where to push the data in str and where to pop it from.
This time, I set capa = 8.
I will try it with the following image.
Hurry up as shown on the left side of the figure and make one box as before.
After that, divide it into the area of 0 <= ptr <= 3 and the area of 4 <= ptr <= 7.
I'll make it a stack.
You can see, you can see, everyone? mark.
I think there are many ways to do it, I just prepared two ptrs (ptr0, ptr1) and 0 <= ptr0 <= 3, 4 <= ptr1 <= 7 Should I rewrite it? I interpreted it.
Then what did you do, uncle !? I think it will be, so let's take a look at it step by step.
stack_x2.py
def __init__(self,capacity:int = 8):
self.str = [None] * capacity
self.capa = capacity/2 #Divide the box into two
self.ptr0 = 0 #1st pointer:0 <= ptr0 <=Since it operates at 3, the initial value is 0.
self.ptr1 = 4 #Second pointer:4 <= ptr1 <=Since it operates at 7, the initial value is 4
self.ptr = 0 #After selecting ptr0 or ptr1, assign it to ptr and go to stack processing.
Basically, when choosing Push / Pop, Make sure to choose which box to store. The way to do this is to substitute either ptr0 or ptr1 into self.ptr. It's still an image of pushing / poping with self.ptr. Let's push.
First, decide whether to assign ptr0 or ptr1 to ptr. Use sel to set ptr = ptr0 when sel == 0 and ptr = ptr1 when sel == 1. That is the following description, I extracted it from the above description.
stackx2.py
def sel_ptr(self,sel):
if sel == 0:
self.ptr = self.ptr0
else:
self.ptr = self.ptr1
return self.ptr
Sounds okay. Next is the main body that actually pushes.
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)
After substituting either ptr0 or ptr1 for ptr, Whether the selected 1st or 2nd box is Full You need to check with an if statement. I will pull it out.
stackx2.py
#sel ==When the first box is selected with 0#sel ==When the first box is selected with 0
if (self.ptr >= self.capa and sel==0) or (self.ptr >= self.capa*2 and sel==1):
If you can confirm whether it is Full or not, Push as usual. I think it's over here, but a little Time! Push has to increment ptr, so The information incremented to ptr0 or ptr1 after the Push process is finished. If you do not update it, it will not become a stack.
Therefore, you need to add the following at the end of the Push process. In the description, there is top.bak_ptr (self, sel), but what you are doing is The processing is as follows.
stackx2.py
def bak_ptr(self,sel):
if sel == 0:
self.ptr0 = self.ptr
else:
self.ptr1 = self.ptr
The last is Pop. It's not much different from Push. Select ptr => Check for Empty => Update ptr => 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]
How was that. I've omitted the explanation about the description of Pop, I wondered if I could do something if I knew Push (laughs)
As for the feel, the conditions for judging Full / Empty are ptr0 ver, ptr1 ver. If you can divide the conditions, you can use the description of the conventional stack. I wondered if I could survive.
The explanation is miscellaneous !, not enough !, difficult to understand! Besides, it's wrong, various !!
I am sorry. If you can comment, I will correct it and add it. m (_ _) m
Recommended Posts