스택이란? 제한된 작업을 수행하는 선형 테이블인 선입후출(First In Last Out) 데이터 구조로 이해할 수 있습니다. 다음 글은 주로 파이썬에서 스택을 실제로 적용하는 방법을 소개합니다. 도움이 필요한 친구들이 함께 참고해 보세요.
stack
스택은 스택이라고도 합니다. 삽입 및 삭제 작업은 스택의 맨 위에서 수행되며 선입, 후-의 규칙에 따라 수행됩니다. 아웃 및 후입선출 작업.
아래 그림과 같이
예를 들어 총의 탄창에서는 탄창에 처음으로 넣은 총알이 발사될 때 마지막 총알이 되고 탄창에 마지막으로 넣은 총알은 발사되었을 때 처음으로 발사되었습니다.
스택 인터페이스
스택을 생성하는 경우 스택을 작동하려면 다음과 같은 인터페이스가 있어야 합니다. )
스택으로 푸시
| 스택에서 팝 | |
|---|---|
| length() | |
| getTop() | |
| 스택에 위의 인터페이스가 필요하다는 것을 알고 나면 Python에서 목록은 다음과 유사합니다. 제공되는 인터페이스는 다음과 같습니다. | |
| Description |
s = []
Create a stack
| 스택에 요소 추가 | |
|---|---|
| s | |
| len(s) | |
| s[-1] | |
| 많은 예제 |
스택의 기본 개념을 이해한 후 이해를 돕기 위해 몇 가지 예제를 더 살펴보겠습니다. 괄호 일치
Question
표현식에 세 개의 대괄호(), [], {}가 포함될 수 있는 경우 중첩 순서는 임의적입니다. 예:
올바른 형식{()[()]},[{({})}]
잘못된 형식
[(]),[()),(()}
표현식 문자열의 대괄호 일치가 올바른지 확인하는 함수를 작성하세요
Idea
빈 스택을 만들어 아직 찾지 못한 왼쪽 대괄호를 저장하세요.
편의 문자열은 왼쪽 대괄호를 만나면 스택에 푸시되고, 오른쪽 대괄호를 만나면 일치를 위해 왼쪽 대괄호가 스택에서 튀어나옵니다.
두 번째 단계에서 오른쪽 대괄호가 나오면 스택이 비어 있을 때 대괄호가 발생하면 왼쪽 대괄호가 누락되었음을 의미합니다.
순회 두 번째 단계가 끝나면 스택이 비어 있지 않아 오른쪽 괄호가 누락되었음을 나타냅니다.
코드 해결 방법
#!/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('[(){()}]')
print(result)Question
사진과 같이
올바른 나가는 경로는 사진의 빨간색 선으로 표시됩니다Idea스택을 사용하여 입구에서 출구까지 마우스의 경로를 기록하세요 특정 지점에 도달한 후 지점의 왼쪽을 스택에 밀어 넣고 지점 값을 1로 설정하여 걸었다는 것을 나타냅니다.
근처에 있는 4개의 지점 중 도달 가능한 지점 중 하나를 선택하세요.
특정 지점에 도달한 후 근처 4개 지점으로 이동하지 않으면 이때 막다른 골목에 도달했다는 의미입니다. 다른 점을 시도하십시오. 컴파일러는 일반적으로 괄호가 필요 없는 후위 표현식을 사용합니다.
중위 표현식
2 + 3 * 4
1 2 + 6 3 / * 2 +
编写程序实现后缀表达式求值函数。 思路 建立一个栈来存储待计算的操作数； 遍历字符串，遇到操作数则压入栈中，遇到操作符号则出栈操作数(n次)，进行相应的计算，计算结果是新的操作数压回栈中，等待计算 按上述过程，遍历完整个表达式，栈中只剩下最终结果； 解决代码 背包问题 题目 有一个背包能装10kg的物品，现在有6件物品分别为： 编写找出所有能将背包装满的解，如物品1+物品5。 解决代码
위 내용은 Python 알고리즘 응용 실무 스택의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!#!/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物品名称 重量 物品0 1kg 物品1 8kg 物品2 4kg 物品3 3kg 物品4 5kg 物品5 2kg #!/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]
"""
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
