Realize a queue with two stacks
Good evening.
Thank you for your support. It seems that my article is useful for everyone I'm very happy (≧ ▽ ≦)
Summarizing one's understanding also helps to organize one's own understanding. Two birds with one stone! (* ´ 艸 ｀)
Now for the title, It's an interesting subject, isn't it? Let's do it right away. What kind of liberation did you imagine?
I thought it could be achieved by preparing a stack dedicated to Push and Pop respectively. For example, when pushing, store it in the area dedicated to Push. In the case of Pop, the data is transferred from Push-only to Pop-only. This is cool! ????? Let's create an image step by step for the time being.
** 1. For Push **
Data is stored in the Push dedicated machine.
The data was pushed in the order of A => B => C => D => E => F.
There is no problem.
Let's take a look at the Pop-only machine.
The address is assigned from 0 to 5 just in case, but it is empty for the time being.
** 2. For Pop **
Extract data from the Push dedicated machine in the manner of a stack,
I will push to the Pop dedicated machine.
In this state, when viewed from the Pop dedicated machine, the order is F => E => D => C => B => A.
Isn't it like this because you will be pushing?
After that, if you pop from the Pop dedicated machine like a stack,
The movement is a stack, but isn't the output of the system the same as the queue?
Somehow I got an image, so let's write it. The base is based on the previous article. https://qiita.com/AKpirion/items/b1bad123aebe72f35a77
stack_x2_queue.py
def __init__(self,size):
self.INstr = [] #Push dedicated machine
self.OUTstr = [] #Pop dedicated machine
self.size = size
It doesn't matter at all, next. For the time being, leave the trigger aside Push dedicated machine (or Pop dedicated machine) data I wanted to use the description to transfer to the uprooted Pop dedicated machine (or Push dedicated machine).
stack_x2_queue.py
#Moving from Push-only machine to Pop-only machine
def trans_IN2OUT(self):
#Uprooted movement of existing stored data length
for _ in range(len(self.INstr)):
self.OUTstr.append(self.INstr.pop())
#Moving from Pop-only machine to Push-only machine
def trans_OUT2IN(self):
#Uprooted movement of existing stored data length
for _ in range(len(self.OUTstr)):
self.INstr.append(self.OUTstr.pop())
For the time being, it's okay to write what you want to write, What should I do (* ´ω ｀) There is no choice but to match Tsuji 褄 (laugh)
Let's go from Push first. I don't care how much data the Push-only machine has If the data length of the Pop dedicated machine is 0, I thought it would be good if I could push to the Push dedicated machine. If the data length of the Pop dedicated machine is not 0, Use def trans_OUT2IN (self) to change from Pop-only machine to Push-only machine Move everything. After that, I made it so that I could push using recursion.
stack_x2_queue.py
def push(self,value):
#Check if the Push dedicated machine is Full
if len(self.INstr) >= self.size:
#Exception handling if Full
raise Stack.full
#Judge whether the Pop dedicated machine is empty
if len(self.OUTstr) == 0:
#If it is empty, push to a dedicated Push machine!
self.INstr.append(value)
else:
#If it is not empty, move all data from the Pop dedicated machine to the Push dedicated machine
Stack.trans_OUT2IN(self)
#If len using recursion(self.OUTstr) ==Substitute data for 0 and push
Stack.push(self,value)
Add the function you want to add with def, Fill in the blanks by adjusting the description in each def. .. Is it okay to do this? (ﾟ Ω ﾟ) Pokhan (ﾟ Д ﾟ y) y! ?? I'm sure there is a logical way to deal with it, I want to study
Well, do you want to go next, pop.
It's basically the opposite of push. If the data length stored in the Push dedicated machine is 0, Pop from a dedicated Pop machine. In cases other than the above, all data is sent from the Push dedicated machine. Move to the Pop dedicated machine. I think it will look like the following.
stack_x2_queue.py
def pop(self):
#If the Push dedicated machine is empty, pop from the Pop dedicated machine
if len(self.INstr) == 0:
print(f"pop data is {self.OUTstr.pop()}")
else:
#Move all data from Push dedicated machine to Pop dedicated machine
Stack.trans_IN2OUT(self)
#If len using recursion(self.INstr) ==Call the 0 condition again
Stack.pop(self)
The whole thing looks like this.
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
The execution result is also posted.
stack size is 4
1.push 2.pop: 1
push data is 1 #Push 1
[1] #Push dedicated machine
[] #Pop dedicated machine
1.push 2.pop: 1
push data is 2 #Push 2
[1, 2] #Push dedicated machine
[] #Pop dedicated machine
1.push 2.pop: 1
push data is 3 #Push 3
[1, 2, 3] #Push dedicated machine
[] #Pop dedicated machine
1.push 2.pop: 1
push data is 4 #Push 4
[1, 2, 3, 4] #Push dedicated machine
[] #Pop dedicated machine
1.push 2.pop: 2
pop data is 1 #Pop 1 from a dedicated Pop machine
[] #Push dedicated machine
[4, 3, 2] #Pop dedicated machine
1.push 2.pop: 2
pop data is 2 #Pop 2 from a dedicated Pop machine
[] #Push dedicated machine
[4, 3] #Pop dedicated machine
1.push 2.pop: 1
push data is 2 #Push Return the data to the dedicated machine and push 2
[3, 4, 2] #Push dedicated machine
[] #Pop dedicated machine
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
[]
[]
I stopped supplementing on the way, After sending all the data to each dedicated machine every time Push and Pop It seems difficult to maintain versatility without moving to Push and Pop actions (= ω =) y─┛ ○ o.
Also, if an error occurs in Full or Empty in the movement defined by the Push dedicated machine or Pop dedicated machine, exception handling will be started, so there is no need to change anything.
Thank you for your hard work ^^) _ Dan ~~
Recommended Posts