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. 図1.PNG

** 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? 図2.PNG 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

Realize a queue with two stacks
Create a stack with a queue and a queue with a stack (from LetCode / Implement Stack using Queues, Implement Queue using Stacks)
Pretend to be a server with two PCs
A4 size with python-pptx
Decorate with a decorator
Python-Draws a curve with equal Mahalanobis distance from two datasets
Learn librosa with a tutorial 1
Draw a graph with NetworkX
Try programming with a shell!
Create a homepage with django
Using a printer with Debian 10
Make a fortune with Python
Create a heatmap with pyqtgraph
Combine two images with Django
Create a directory with python
A little stuck with chainer
Draw a graph with networkx
Easily cProfile with a decorator
Make a fire with kdeplot