Python 알고리즘 애플리케이션 스택에 대한 자세한 설명

스택(stack)

스택은 스택이라고도 하며, 삽입과 삭제 작업은 스택의 맨 위에서 수행되며, 선입(first-in) 규칙을 따릅니다. 후입선출(last-in-first-out) 작업을 수행합니다.

아래 그림과 같이

예를 들어 총의 탄창은 탄창에 처음 넣은 총알이 발사되었을 때 마지막 총알이 됩니다. 탄창에 넣은 마지막 총알은 발사 시 처음으로 발사되는 총알입니다.

스택 인터페이스

스택을 생성하는 경우 스택을 작동하려면 다음과 같은 인터페이스가 있어야 합니다.

스택에 대해 알아두기 위의 인터페이스가 필요한 경우 Python의 경우 목록은 스택과 유사하며 제공되는 인터페이스는 다음과 같습니다.

Python의 스택 인터페이스 사용 예:

# 创建一个栈
In [1]: s = []
# 往栈内添加一个元素
In [2]: s.append(1)
In [3]: s
Out[3]: [1]
# 删除栈内的一个元素
In [4]: s.pop()
Out[4]: 1
In [5]: s
Out[5]: []
# 判断栈是否为空
In [6]: not s
Out[6]: True
In [7]: s.append(1)
In [8]: not s
Out[8]: False
# 获取栈内元素的数量
In [9]: len(s)
Out[9]: 1
In [10]: s.append(2)
In [11]: s.append(3)
# 取栈顶的元素
In [12]: s[-1]
Out[12]: 3

많은 예제

스택의 기본 개념을 이해한 후, 스택에 대한 이해를 돕기 위해 몇 가지 예제를 더 살펴보겠습니다.

괄호 일치

질문

표현식에 세 개의 대괄호(), [], {}가 포함될 수 있는 경우 중첩 순서는 임의적입니다. 예:

올바른 형식

{()[()]},[{({})}]

잘못된 형식

[(]),[()),(()}

표현식 문자열의 괄호 일치가 올바른지 확인하는 함수 작성

아이디어

아직 발견되지 않은 왼쪽 대괄호를 저장하기 위해 빈 스택을 생성합니다.

편의 문자열, 왼쪽 대괄호를 만나면 스택을 푸시하고 오른쪽 대괄호를 만나면 일치를 위해 왼쪽 대괄호를 팝합니다.

두 번째 단계에서 스택이 비어 있을 때 오른쪽 대괄호가 발견되면 왼쪽 대괄호가 누락되어 일치하지 않음을 의미합니다.

두 번째 단계 순회가 끝나면 스택이 비어 있지 않음, 이는 누락되었음을 나타냄 오른쪽 괄호, 불일치

솔루션 코드

더 나은 이해를 위해 pycharm에서 점을 나누는 것이 좋습니다

#!/use/bin/env python
# _*_ coding:utf-8 _*_
LEFT = {'(', '[', '{'} # 左括号
RIGHT = {')', ']', '}'} # 右括号
def match(expr):
 """
 :param expr: 传过来的字符串
 :return: 返回是否是正确的
 """
 stack = [] # 创建一个栈
 for brackets in expr: # 迭代传过来的所有字符串
 if brackets in LEFT: # 如果当前字符在左括号内
  stack.append(brackets) # 把当前左括号入栈
 elif brackets in RIGHT: # 如果是右括号
  if not stack or not 1 <= ord(brackets) - ord(stack[-1]) <= 2:
  # 如果当前栈为空，()]
  # 如果右括号减去左括号的值不是小于等于2大于等于1
  return False # 返回False
  stack.pop() # 删除左括号
 return not stack # 如果栈内没有值则返回True，否则返回False
result = match(&#39;[(){()}]&#39;)
print(result)

미로 문제

질문

2차원 배열을 사용하여 간단한 미로를 표현하고, 0을 사용하여 경로를 표현하고, 1을 사용하여 표현합니다. 각 지점에서 마우스는 남동쪽, 북서쪽의 인접한 4개 지점을 이동하고 미로를 통과하는 마우스를 시뮬레이션하고 입구에서 출구까지의 경로를 찾는 알고리즘을 설계할 수 있습니다.

사진과 같이

사진에서 빨간색 선으로 나오는 올바른 경로가 표시됩니다

생각

스택을 사용하여 입구에서 출구까지 마우스의 경로를 기록합니다

특정 지점에 도달한 후 지점의 왼쪽을 스택 위로 밀어 넣고 지점의 값을 1로 설정하고,

인접한 4개 지점 중 도달 가능한 지점 중 하나를 선택하고 해당 지점으로 이동하세요.

도달한 후 인접한 4개 지점으로 이동하지 않으면; 특정 지점에 도달했다는 의미입니다. 이때 스택에서 물러나서 한 단계 뒤로 이동하여 다른 지점을 시도하세요.

출구를 찾을 때까지 2, 3, 4단계를 반복하세요. 🎜>

코드 풀기

#!/use/bin/env python
# _*_ coding:utf-8 _*_
def initMaze():
 """
 :return: 初始化迷宫
 """
 maze = [[0] * 7 for _ in range(5 + 2)] # 用列表解析创建一个7*7的二维数组，为了确保迷宫四周都是墙
 walls = [ # 记录了墙的位置
 (1, 3),
 (2, 1), (2, 5),
 (3, 3), (3, 4),
 (4, 2), # (4, 3), # 如果把(4, 3)点也设置为墙，那么整个迷宫是走不出去的，所以会返回一个空列表
 (5, 4)
 ]
 for i in range(7): # 把迷宫的四周设置成墙
 maze[i][0] = maze[i][-1] = 1
 maze[0][i] = maze[-1][i] = 1
 for i, j in walls: # 把所有墙的点设置为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: 迷宫
 :param start: 起始点
 :param end: 结束点
 :return: 行走的每个点
 """
 i, j = start # 分解起始点的坐标
 ei, ej = end # 分解结束点的左边
 stack = [(i, j)] # 创建一个栈，并让老鼠站到起始点的位置
 maze[i][j] = 1 # 走过的路置为1
 while stack: # 栈不为空的时候继续走，否则退出
 i, j = stack[-1] # 获取当前老鼠所站的位置点
 if (i, j) == (ei, ej): break # 如果老鼠找到了出口
 for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # 左右上下
  if maze[i + di][j + dj] == 0: # 如果当前点可走
  maze[i + di][j + dj] = 1 # 把当前点置为1
  stack.append((i + di, j + dj)) # 把当前的位置添加到栈里面
  break
 else: # 如果所有的点都不可走
  stack.pop() # 退回上一步
 return stack # 如果迷宫不能走则返回空栈
Maze = initMaze() # 初始化迷宫
result = path(maze=Maze, start=(1, 1), end=(5, 5)) # 老鼠开始走迷宫
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)]

후위식 평가

질문

식을 평가할 때 , 컴파일러는 일반적으로 괄호가 필요 없는 후위 표현식을 사용합니다.

후위 표현식 평가 함수를 구현하는 프로그램을 작성합니다.

아이디어

계산할 피연산자를 저장할 스택을 생성합니다.

문자열을 탐색하여 피연산자를 만나면 스택에 밀어넣고, 만나면 튀어나옵니다. 연산 기호 스택 피연산자(n 회), 해당 계산 수행, 계산 결과는 스택에 다시 푸시된 새 피연산자, 계산 대기

위 프로세스에 따라 전체 표현식을 순회하고, 최종 결과는 스택에 남습니다 ;

해결 코드

#!/use/bin/env python
# _*_ coding:utf-8 _*_
operators = { # 运算符操作表
 '+': 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: 后缀表达式
 :return: 正常情况下栈内的第一个元素就是计算好之后的值
 """
 tokens = e.split() # 把传过来的后缀表达式切分成列表
 stack = []
 for token in tokens: # 迭代列表中的元素
 if token.isdigit(): # 如果当前元素是数字
  stack.append(int(token)) # 就追加到栈里边
 elif token in operators.keys(): # 如果当前元素是操作符
  f = operators[token] # 获取运算符操作表中对应的lambda表达式
  op2 = stack.pop() # 根据先进后出的原则，先让第二个元素出栈
  op1 = stack.pop() # 在让第一个元素出栈
  stack.append(f(op1, op2)) # 把计算的结果在放入到栈内
 return stack.pop() # 返回栈内的第一个元素
result = evalPostfix('2 3 4 * +')
print(result)
# 14

배낭 문제

질문

10kg을 담을 수 있는 배낭이 있습니다 현재 6개의 항목이 있습니다. :

항목 1 + 항목 5 등 배낭을 채울 수 있는 모든 솔루션을 작성하고 찾아보세요.

솔루션 코드

#!/use/bin/env python
# _*_ coding:utf-8 _*_
def knapsack(t, w):
 """
 :param t: 背包总容量
 :param w: 物品重量列表
 :return:
 """
 n = len(w) # 可选的物品数量
 stack = [] # 创建一个栈
 k = 0 # 当前所选择的物品游标
 while stack or k < n: # 栈不为空或者k<n
 while t > 0 and k < n: # 还有剩余空间并且有物品可装
  if t >= w[k]: # 剩余空间大于等于当前物品重量
  stack.append(k) # 把物品装备背包
  t -= w[k] # 背包空间减少
  k += 1 # 继续向后找
 if t == 0: # 找到了解
  print(stack)
 # 回退过程
 k = stack.pop() # 把最后一个物品拿出来
 t += w[k] # 背包总容量加上w[k]
 k += 1 # 装入下一个物品
knapsack(10, [1, 8, 4, 3, 5, 2])
"""
[0, 2, 3, 5]
[0, 2, 4]
[1, 5]
[3, 4, 5]
"""

요약

위 글의 내용은 모두의 공부나 업무에 도움이 되었으면 좋겠습니다. 궁금한 점이 있으면 메시지를 남겨서 소통할 수 있습니다.

Python 알고리즘 응용에 대한 실제 스택에 대한 자세한 설명은 PHP 중국어 웹사이트를 참고하세요!