This article is participating in Python Theme Month. See the link for details

The application of the stack

Implement a browser forward and backward

I’m sure you’re familiar with the browser’s forward and backward functions.

After you have visited a series of pages A-B-C, click your browser’s back button to view the previous pages B and A. When you go back to page A and click the forward button, you can revisit pages B and C. However, if you go back to page B and click on a new page D, you can no longer see page C using the forward and backward functions.

If you were a developer of Chrome, how would you implement this feature?

We use two stacks, X and Y. We push the first page into stack X, and when the back button is clicked, we push the page out of stack X, and put the data out of stack into stack Y. When we click the forward button, we take data from stack Y in turn and put it into stack X. When there is no data in stack X, there are no pages to go back to. When there is no data in stack Y, there are no pages to browse by clicking the forward button.

For example, if you view page A, page B, and page C in sequence, we will push a, b, and page C in sequence. Then, the data of the two stacks will look like this:

When you go back from page C to page A using the browser’s back button, we pop c and B off stack X and onto stack Y. At this point, the data for both stacks looks like this:

Now, you want to see page B again, so you hit the forward button to get back to page B, and we’re going to take b off stack Y and put it on stack X. The data for the two stacks looks like this:

The realization of the stack

Def __init__(self): self.__items = [] def push(self, item): """ "self.__items.append(item) def pop(self): """ "return self.__items.pop() def peek(self): # return self.__items[-1] return self.__items[len(self.__items)-1] else: Return None def is_empty(self): """ "if self.__items == []: return True else: Return False # return self.__items == [] def size(self): """ "return len(self.__items)Copy the code

Use a stack to move the browser forward and backward

class Browser():

    def __init__(self):
        self.x = Stack()
        self.y = Stack()

    def can_forward(self):
        if self.y.is_empty():
            return False

        return True

    def can_back(self):
        if self.x.is_empty():
            return False

        return True

    def open(self, url):
        print("Open new url %s" % url, end="\n")
        self.x.push(url)

    def back(self):
        if self.x.is_empty():
            return

        top = self.x.pop()
        self.y.push(top)
        print("back to %s" % self.x.peek(), end="\n")

    def forward(self):
        if self.y.is_empty():
            return

        top = self.y.pop()
        self.x.push(top)
        print("forward to %s" % top, end="\n")


if __name__ == '__main__':
    browser = Browser()
    browser.open('a')
    browser.open('b')
    browser.open('c')
    if browser.can_back():
        browser.back()

    if browser.can_forward():
        browser.forward()

    browser.back()
    browser.back()
    browser.back()
Copy the code

Determines whether the string is valid

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.

A valid string must meet the following requirements:

  • An open parenthesis must be closed with a close parenthesis of the same type.
  • The left parentheses must be closed in the correct order.

Note that an empty string can be considered a valid string.

Example 1:

Input: "()" Output: trueCopy the code

Example 2:

Input: "()[]{}" Output: trueCopy the code

Example 3:

Input: "(]" Output: falseCopy the code

Their thinking

So when we started looking at this problem, we couldn’t help but wonder if we could calculate the number of open parentheses, and the number of close parentheses, if we had the same number of left and right parentheses, would that be valid parentheses?

In fact, no, if the input is [{]}, the left and right parentheses of each type are equal, but not valid parentheses. This is because the result also depends on the position of the parentheses.

def isValid(s):
    dic = {')': '(', ']': '[', '}': '{'}
    stack = []
    for i in s:
        if stack and i in dic:
            if stack[-1] == dic[i]:
                stack.pop()
            else:
                return False
        else:
            stack.append(i)

    return not stack


if __name__ == '__main__':
    print(isValid("()["))
Copy the code

Conversion from decimal to binary

The so-called “base” is how many characters are used to represent the integer.

Decimal is the ten numeric characters 0-9, binary is 0,1 two characters

We often need to convert integers between binary and decimal

Dividing by 2 gives the remainder from lowest to highest and the output from highest to lowest, so a stack is needed to reverse the order

def divideBy2(num): remstack = Stack() while num > 0: Num = num // 2 BSTR = "" while not remstack.is_empty(): bstr = bstr + str(remstack.pop()) return bstr print(divideBy2(233))Copy the code

Use stacks to solve maze problems

Give a two-dimensional list of mazes (0 for passages, 1 for walls). Give an algorithm to find a way out of the maze

Train of thought: Start at a node and find the next possible point. When you can’t find the next possible point, go back to the previous point and look for other points

maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 1, 0, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 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): stack = [] stack.append((x1, y1)) # print(stack) while (len(stack) > 0): If curNode[0] == x2 and curNode[1] == y2: Print (p) return True # x,y; x+1,y; x,y-1; X,y+1 for dir in dirs: nextNode = dir(curNode[0], curNode[1]) Stack. Append (nextNode) maze[nextNode[0]][nextNode[1]] = 2 # 2 Maze [nextNode[0]][nextNode[1]] = 2 stack.pop() else: print(" no path ") return False maze_path(1, 1, 8, 8)Copy the code