1, Stack

1. Basic usage

class Stack:
    def __init__(self):
        self.stack = []
    # Push 
    def push(self,element):
        self.stack.append(element)
    # Out of stack
    def pop(self):
        if len(self.stack) > 0:
            return  self.stack.pop()
        else:
            return None
    def get_top(self):
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None
    def is_empty(self):
        return len(self.stack) == 0

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) # 3
print(stack.get_top()) # 2

Features: in and out

2. Bracket matching

class Stack:
    def __init__(self):
        self.stack = []
    def push(self,element):
        self.stack.append(element)
    def pop(self):
        if len(self.stack) > 0:
            return self.stack.pop()
        else:
            return None
    def get_top(self):
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None
    def is_empty(self):
        return len(self.stack) == 0

def brace_match(arr):
    match = {')':'(','}':'{',']':'['}
    inMatch = {'(','{','['}
    stack = Stack()
    for i in arr:
        if i in inMatch:
            stack.push(i)
        else:
            if stack.is_empty(): # If empty
                return False
            elif stack.get_top() == match[i]: # If the bracket in the stack corresponds to the value in the dictionary, let it out of the stack
                stack.pop()
            else: # If not, it indicates a mismatch
                return False
    # After all traversal, if there are parentheses in the stack, it indicates that they do not match, otherwise they match
    if stack.is_empty():
        return True
    else:
        return False

print(brace_match('[](())}')) # False
print(brace_match('[](()){()}')) # True

Bracket matching is a classic problem in the stack. Each traversal will (, {, [be put into the stack, and the elements to be put into the stack next time will match it. If the matching is successful, it will be put out of the stack, otherwise it will be put into the stack. Until all traversals are completed, if there are still elements in the stack, it means that the matching is not successful, otherwise the matching is successful.

3. Maze problem (deep search backtracking method)

maze = [
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,1,0,1,0,1,1,1,1],
    [1,0,1,0,1,1,0,0,1,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,1,0,0,1,0,1,1,0,1],
    [1,1,1,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]

dirs = [
    lambda x,y: (x+1,y),
    lambda x,y: (x-1,y),
    lambda x,y: (x,y+1),
    lambda x,y: (x,y-1)
]

def maze_path(x1,y1,x2,y2): # Start and end coordinates
    stack = []
    stack.append((x1,y1)) # Put the starting point into the stack first
    while len(stack) > 0:
        curNode = stack[-1] # Get current node
        # After the loop is completed, it is found that it has reached the end point, and the elements in the stack are output
        if curNode[0] == x2 and curNode[1] == y2:
            for i in stack:
                print(i)
            return True
        # x. Y try walking in all four directions
        for dir in dirs:
            nextNode = dir(curNode[0],curNode[1]) # Get next node
            if maze[nextNode[0]][nextNode[1]] == 0: # It means you can go
                stack.append(nextNode) # Walk into the stack if you can
                maze[nextNode[0]][nextNode[1]] = 2 # Mark the points to be passed
                break # Stop when you can go in one direction
        else:
            # If you can't walk in all four directions, mark the point as walking, delete it from the top of the stack, and then find the next stack vertex
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()
    else:
        print("No way")
        return False
maze_path(1,1,6,8)

Maze problem is a classic problem. The method of searching the top of the stack is always the first method. Each time, find that the next node has four directions, and test whether this direction can go according to the initial initialization order (when the problem is 0). If it can go, repeat the above steps, then test whether the next direction can go, put the node that can go into the stack, and mark the node to go (the problem is marked as 2). If you can't walk, first mark the node as walking, and take the node that can't walk out of the stack. Repeat the above operation for the new stack top element until the last stack top element becomes the end coordinate, and output all elements in the stack. Otherwise, there is no way.

2, Queue

1. Basic usage

class Queue:
    def __init__(self,size=100):
        self.queue = [0 for _ in range(size)]
        self.size = size
        self.rear = 0 # Tail pointer
        self.front = 0 # Team leader pointer
    def push(self,element):
        if not self.is_filled():
            # Move the end of line pointer forward one bit and add the element
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = element
        else:
            raise IndexError('Queue is filled.')
    def pop(self):
        if not self.is_empty():
            # Move the team leader pointer forward one bit, and then delete the team leader element
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise IndexError('Queue is empty.')
    # Judge team empty
    def is_empty(self):
        return self.rear == self.front
    # Judge team full
    def is_filled(self):
        return (self.rear + 1) % self.size == self.front

queue = Queue()
queue.push(1)
queue.push(2)
queue.push(3)
print(queue.pop())
print(queue.pop())
print(queue.pop())
print(queue.is_empty())

Features: first in first out

Circular queue, surrounded by a circle

2. Maze problem (guangsou)

from collections import deque
maze = [
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,1,0,1,0,1,1,1,1],
    [1,0,1,0,1,1,0,0,1,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,1,0,0,1,0,1,1,0,1],
    [1,1,1,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]

dirs = [
    lambda x,y: (x+1,y),
    lambda x,y: (x-1,y),
    lambda x,y: (x,y+1),
    lambda x,y: (x,y-1)
]

# Starting from the end coordinate, pour one coordinate forward according to the index of the end coordinate, and repeat the operation until the index reaches - 1, because the initial value is written as - 1
def print_r(path): # There are many paths in this path
    curNode = path[-1] # The last is the endpoint coordinate, which is the current node
    realpath = [] # Real path
    while curNode[2] != -1: # This - 1 is an index defined at the start point
        realpath.append((curNode[0:2])) # No index is needed in the real path, so x and y can be obtained by slicing
        curNode = path[curNode[2]] # The next current node is the index of the previous node
    realpath.append(curNode[0:2]) # Put the starting point in
    realpath.reverse()
    for i in realpath:
        print(i)

def maze_path_queue(x1,y1,x2,y2):
    queue = deque()
    queue.append((x1,y1,-1)) # Create a three-dimensional space and add an index
    path = [] # Dequeued element in order to store index values
    while len(queue) > 0:
        curNode = queue.popleft() # First out queue
        path.append(curNode) # Save the out of line elements
        # It's the end
        if curNode[0] == x2 and curNode[1] == y2:
            # Output the elements in the queue
            print_r(path)
            return True
        for dir in dirs:
            # Check whether the next node can go. If so, enter the queue
            nextNode = dir(curNode[0],curNode[1]) # Next node
            if maze[nextNode[0]][nextNode[1]] == 0:
                queue.append((nextNode[0],nextNode[1],len(path)-1)) # The last point is the index, which records which node brought him
                maze[nextNode[0]][nextNode[1]] = 2 # Mark the points to be passed
    else:
        print("No way")
        return False

maze_path_queue(1,1,6,8)

Maze problem can get the shortest path by using the wide search of queue. The idea is to build a three-dimensional space and store an index in addition to X and Y coordinates. This index is very important. It is used when you go back from the end point. My understanding is that because it is a wide search, there will be many useless paths in the path, so the function of the index can ensure that there will be no confusion when walking back from the end point. Remember first in first out in the queue. First enter the starting point into the queue, and then exit the queue, and save it in a path array. Then traverse the four directions to see if you can go, mark and record which point brought him. Note that the difference between this and the deep search of the stack is that you can join the team as long as there is a way in each direction, unlike the stack break ing after entering the stack in the specified order. In this process, all the elements are saved in the path. So I went back to what I said at the beginning. Many useless paths are saved in this path, but each path is marked with an index value. Therefore, when finally looking for a path, I fall from the end point. Pour the index of the end point to the previous point (the last point with him), then find the index of this point, and repeat the above operations until the index is - 1 (the index given to the starting point at the beginning). Finding this step shows that the whole road is through. Remember to add the starting point. So far, this path is the shortest, but because it is inverted from the end, it is reversed. Use reverse to complete the search.

3, Practice

The following content has nothing to do with the text, just water and water
It's 17.23 now, 37 minutes from work. More than half of the month's internship has passed. It seems that we can get the essence of fishing more and more. The company's atmosphere is good. Maybe there are several students around. They still have a strong sense of belonging. At least they won't feel bullied when they are around? Maybe you can survive being bullied, hahaha. To tell the truth, although the internship is in a small company, I still feel nervous when I first joined the company. Unlike other students who interned with me, they all have at least some project experience. Only I know I can't do anything and my foundation is not solid. Sure enough, the first two weeks were the hardest. The first week was good. Maybe I wanted to test the water. The first week's project was not very difficult. It didn't involve any logic. It was almost all css. In react, I didn't even know css. Fortunately, there was only css. I had written css, I still had an impression in my mind, and the time cycle was relatively long. Next to me was a very gentle and powerful boss, The first week is finished. Okay, okay.
The second week is not good. The first difficulty: interaction. They started to interact. Although they had adjusted the interface before, they didn't actually communicate with live people at the back end, and they didn't read the interface documents very well. So I first asked others how to tune it, and then they explained the interface I didn't understand in words I didn't understand, which made them more confused Orz. Then go online to find a video to learn first. It seems that you can watch it?
The second difficulty: scheduling. Before doing the project, the team leader will write the schedule of the whole project in the form, which is actually what he did every day and whether he completed the task of the day. Every morning, the team leader will hold a small meeting to report the progress of the project. At the beginning, because he can't do anything, he is still working overtime when he comes home from work, but he still can't finish it, so the schedule can't keep up with the progress. When reporting, they... Completed the schedule yesterday, but I haven't finished it yet
The third difficulty: the demand always changes. It's not easy. The demand has changed?! The schedule can't keep up again. What we used to do has to be deleted and rewritten Orz.
But! Sure enough, ddl is the primary productive force. In order to catch up with the schedule, I learned more and faster this week than I learned in recent months. I also learned to read documents. Moreover, my daily internship was forced to make my work and rest regular. I probably didn't do it for a long time when I woke up at 7 a.m. last weekend (laughs). The logic has been clarified. I feel that the most difficult thing is css, The current project feels that css has not been adjusted well. It is estimated that there will be a lot of bugs when the test returns. At the beginning of the third week, because the new project hasn't come yet, the test asked for leave (speaking, the test raised more bugs that need to be modified than the ones you wrote, Orz) so that you can learn (FISH) by yourself. There's nothing to learn about data structures these two days. You've forgotten a lot before.
I seem to be getting lazier and lazier. It turned out that I would get up at 6.30 in the first week, put on makeup, have a meal, and then take the bus to the company. When I go back at night, I won't work overtime, and then study and work. The next week, when I was late, my mother would send me to the company. Now in the third week, I get up at 7 o'clock and don't make up. Then I go straight to my mother to send me to school. I also lie down and chase the play at night, Orz. These two days are also relatively idle. There is no ddl urging me, and the efficiency has become low. Oh, it's time. Get off work! You must study hard tomorrow