Problem 09 uses two stacks to implement queues

Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. If there are no elements in the queue, the deleteHead operation returns -1

Train of thought

A stack A is used to join the queue, and A stack B is used to leave the queue. When leaving the queue, whether stack B is empty is determined first. If it is empty, the element joining stack A will be removed from the stack and merged into stack B, and the top element will be popped out.

code

class CQueue:
    def __init__(self) :
        self.stack_in = []
        self.stack_out = []

    def appendTail(self, value: int) - >None:
        self.stack_in.append(value)

    def deleteHead(self) - >int:
        if not self.stack_out:
            if not self.stack_in: # is empty
                return -1
            else: Dump everything in the in stack into the out stack
                while self.stack_in:
                    self.stack_out.append(self.stack_in.pop())
        
        return self.stack_out.pop()
Copy the code

Problem number 10: Fibonacci number 1

F(n-1), F(n-2), F(n-1), F(n-2

class Solution:
    def fib(self, n: int) - >int:
        if n == 0:
            return 0
        if n == 1:
            return 1

        res = [0.1]
        for i in range(2,n):
            tmp = res[0]
            res[0] = res[1]
            res[1] = res[1] + tmp

        return sum(res)%1000000007# The module is required in the problem
Copy the code