stack
Stack, also known as a stack is a special ordered table whose insertion and deletion operations are performed on the top of the stack and operate according to the rules of first-in-first-out and last-in-first-out.
As shown in the figure below
For example, in a gun's magazine, the first bullet put into the magazine is instead the last when fired, while the last bullet put into the magazine is the first fired when it is shot.
stack interface
If you create a stack, it should have the following interfaces to operate on it
| connector | descriptive |
|---|---|
| push() | push on |
| pop() | send a package to a warehouse |
| isEmpty() | Determine if the stack is empty |
| length() | Get the length of the stack |
| getTop() | Fetch the element at the top of the stack, the element is not out of the stack. |
Knowing that a stack requires the above interface, then in Python, a list is analogous to a stack, providing the interface as follows:
| manipulate | descriptive |
|---|---|
| s = [] | Creating a Stack |
| (x) | Add an element to the stack |
| () | Delete an element on the stack |
| not s | Determine if the stack is empty |
| len(s) | Get the number of elements on the stack |
| s[-1] | Getting the top of the stack |
Example of using the stack interface in Python:
# Create a stack In [1]: s = [] # Add an element to the stack In [2]: (1) In [3]: s Out[3]: [1] # Delete an element from the stack In [4]: () Out[4]: 1 In [5]: s Out[5]: [] # Determine if the stack is empty In [6]: not s Out[6]: True In [7]: (1) In [8]: not s Out[8]: False # Get the number of elements on the stack In [9]: len(s) Out[9]: 1 In [10]: (2) In [11]: (3) # Take the top element of the stack In [12]: s[-1] Out[12]: 3
A large wave of examples
After understanding the basic concepts of stacks, let's look at a few more examples to make it easier to understand stacks.
bracket match
theme
Suppose the expression is allowed to contain three parentheses (), [], and {} in any order of nesting, e.g.:
Correct formatting
{()[()]},[{({})}]
Incorrect formatting
[(]),[()),(()}
Write a function that determines whether an expression string, with parentheses matched, is correct or not
reasoning
- Creates an empty stack to store left brackets that have not yet been found;
- Convenience strings, left brackets are stacked when encountered, right brackets are out of the stack a left bracket is matched;
- During the second step, if a right bracket is encountered in the empty stack case, it means that the left bracket is missing and does not match;
- At the end of the second traversal step, the stack is not empty, indicating that the right bracket is missing and does not match;
solution code
Suggested breakpoints in pycharm for better understanding
#!/use/bin/env python
# _*_ coding:utf-8 _*_
LEFT = {'(', '[', '{'} # Left brackets
RIGHT = {')', ']', '}'} # Right brackets
def match(expr):
"""
:param expr: passed string
:return: Whether the return is correct or not
"""
stack = [] # Create a stack
for brackets in expr: # Iterate over all the strings passed
if brackets in LEFT: # If the current character is in left brackets
(brackets) # Put the current left bracket on the stack
elif brackets in RIGHT: # In case of right brackets
if not stack or not 1 <= ord(brackets) - ord(stack[-1]) <= 2:
# If the current stack is empty, ()]
# If the value of the right parenthesis minus the left parenthesis is not less than or equal to 2 or greater than or equal to 1
return False # Returns False
() # Remove left brackets
return not stack # Returns True if there is no value on the stack, otherwise returns False
result = match('[(){()}]')
print(result)
The maze problem
theme
Represent a simple maze as a two-dimensional array, with 0s denoting pathways and 1s denoting blockages, and a mouse can move four adjacent points, southeast, northwest, and north-west, at each point.Design an algorithm to simulate a mouse walking through a maze to find a path from the entrance to the exit.
as shown
The correct line to go out is shown as the red line in the diagram
reasoning
- Use a stack to record the path of the mouse from the entrance to the exit
- After walking to a point, the left side of the point is stacked and the point value is set to 1 to indicate that it has been walked;
- Choose any one of the four accessible points in the neighborhood and walk to that point;
- If none of the 4 points in close proximity after reaching a certain point, it means that you have reached a dead end, at which point you back out of the stack and take a step back to try another point;
- Repeat steps two, three and four until you find the exit;
solution code
#!/use/bin/env python # _*_ coding:utf-8 _*_ def initMaze(): """ :return: Initializing the maze """ maze = [[0] * 7 for _ in range(5 + 2)] # Create a 7*7 two-dimensional array with list parsing, in order to ensure that the maze is surrounded by walls walls = [ # Recorded the location of the wall (1, 3), (2, 1), (2, 5), (3, 3), (3, 4), (4, 2), # (4, 3), # If the point (4, 3) is also set as a wall, then the whole maze is not walkable, so it returns an empty list (5, 4) ] for i in range(7): # Set up a wall around the maze maze[i][0] = maze[i][-1] = 1 maze[0][i] = maze[-1][i] = 1 for i, j in walls: # Set all wall points to 1 maze[i][j] = 1 return maze """ [1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 1, 0, 0, 1] [1, 1, 0, 0, 0, 1, 1] [1, 0, 0, 1, 1, 0, 1] [1, 0, 1, 0, 0, 0, 1] [1, 0, 0, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 1] """ def path(maze, start, end): """ :param maze: maze :param start: Start point :param end: end point :return: each point traveled """ i, j = start # The coordinates of the starting point of the decomposition ei, ej = end # To the left of the end point of decomposition stack = [(i, j)] # Create a stack and have the mouse stand in the starting position # maze[i][j] = 1 # The road traveled is set to one while stack: # Keep going if the stack isn't empty, otherwise quit # i, j = stack[-1] # Get the current location point where the mouse is standing if (i, j) == (ei, ej): break # If the rats find an exit # for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # Left, right, up, down if maze[i + di][j + dj] == 0: # If the current point is walkable maze[i + di][j + dj] = 1 # Set the current point to 1 ((i + di, j + dj)) # Add the current position to the stack break else: # If all the dots are untraceable # () # Return to previous step return stack # If the maze can't be walked then return to the empty stack # Maze = initMaze() # Initialize the maze result = path(maze=Maze, start=(1, 1), end=(5, 5)) # The mice began to walk the maze print(result) # [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (4, 3), (4, 4), (4, 5), (5, 5)]
Suffix expression evaluation
theme
When computing an expression, the compiler usually uses a postfix expression, which does not require parentheses:
| affix expression | suffix expression |
|---|---|
| 2 + 3 * 4 | 2 3 4 * + |
| ( 1 + 2 ) * ( 6 / 3 ) + 2 | 1 2 + 6 3 / * 2 + |
| 18 / ( 3 * ( 1 + 2 ) ) | 18 3 1 2 + * / |
Write a program to implement the suffix expression evaluation function.
reasoning
- Create a stack to store the operands to be computed;
- Iterate through the string, meet the operand is pressed into the stack, meet the operation symbol is out of the stack operand (n times), the corresponding calculation, the result of the calculation is the new operand pressed back into the stack, waiting for the calculation
- By following the above procedure, the entire expression is traversed and only the final result remains on the stack;
solution code
#!/use/bin/env python
# _*_ coding:utf-8 _*_
operators = { # Table of operator operations
'+': lambda op1, op2: op1 + op2,
'-': lambda op1, op2: op1 - op2,
'*': lambda op1, op2: op1 * op2,
'/': lambda op1, op2: op1 / op2,
}
def evalPostfix(e):
"""
:param e: suffix expression
:return: Normally the first element of the stack is the calculated value.
"""
tokens = () # Split the incoming postfix expression into lists
stack = []
for token in tokens: # Iterate over the elements of the list
if (): # If the current element is a number
(int(token)) # Just append to the stack
elif token in (): # If the current element is the operator
f = operators[token] # Get the corresponding lambda expression in the operator manipulation table
op2 = () # Let the second element out of the stack first according to the first-in-first-out principle
op1 = () # On getting the first element off the stack #
(f(op1, op2)) # Put the result of the calculation on the stack #
return () # Return the first element of the stack
result = evalPostfix('2 3 4 * +')
print(result)
# 14
Backpack issues
title
There is a backpack that holds 10kg of items, now there are 6 items each:
| Item name | weights |
|---|---|
| Item 0 | 1kg |
| Item 1 | 8kg |
| Item 2 | 4kg |
| Item 3 | 3kg |
| Item 4 | 5kg |
| Item 5 | 2kg |
Write to find all the solutions that will fill the backpack, such as item 1 + item 5.
solution code
#!/use/bin/env python # _*_ coding:utf-8 _*_ def knapsack(t, w): """ :param t: total backpack capacity :param w: list of item weights :return. """ n = len(w) # of items available stack = [] # Create a stack k = 0 # Currently selected item cursor while stack or k < n: # The stack is not empty or k<n while t > 0 and k < n: # With room to spare and items to load if t >= w[k]: # Remaining space is greater than or equal to current item weight (k) # Equip your backpack with items t -= w[k] # Reduced backpack space k += 1 # Keep looking back if t == 0: # Finding understanding print(stack) # The fallback process k = () # Take out the last item t += w[k] # Total backpack capacity plus w[k] k += 1 # Load the next item knapsack(10, [1, 8, 4, 3, 5, 2]) """ [0, 2, 3, 5] [0, 2, 4] [1, 5] [3, 4, 5] """
summarize
The above is the entire content of this article, I hope the content of this article on your learning or work can bring some help, if there are questions you can leave a message to exchange.