栈的顺序存储实现
class Stack:
# 初始化空栈
def __init__(self, size = 100):
self.stack = []
self.size = size
self.top = -1 # 栈顶元素指向 -1
# 判断栈是否为空
def is_empty(self):
return self.top == -1
# 判断栈是否已满
def is_full(self):
return self.top + 1 = self.size
# 入栈操作
def push(self, value):
if self.is_full():
raise Exception('Stack is full!')
else:
self.stack.append(value)
self.top += 1
# 出栈操作
def pop(self):
if self.is_empty():
raise Exception('Stack is empty!')
else:
self.stack.pop()
self.top -= 1
# 获取栈顶元素
def peek(self):
if self.empty():
raise Exception('Stack is empty!')
else:
return self.stack[self.top]
栈-先进后出
class Test:
def test(self):
# create a stack
stack = []
# add element
# time complexity: O(1)
stack.append(1)
stack.append(2)
stack.append(3)
print(stack) # [1,2,3]
# get the top of stack
# time complexity: O(1)
stack[-1]
# remove the top of stack
# time complexity: O(1)
temp = stack.pop()
print(temp) # 3
# get stack length
# time complexity: O(1)
len(stack)
# stack is empty?
# time complexity: O(1)
len(stack) == 0
# iterate stack
# time complexity: O(n)
while len(stack) > 0:
temp = stack.pop()
print(temp) # 2 1
if __name__ == '__main__':
test = Test()
test.test()
3. 堆栈的应用
堆栈是算法和程序中最常用的辅助结构，其的应用十分广泛。堆栈基本应用于两个方面：
- 使用堆栈可以很方便的保存和取用信息，因此长被用作算法和程序中的辅助存储结构，临时保存信息，供后面操作中使用。
例如：操作系统中的函数调用栈，浏览器中的前进、后退功能。 - 堆栈的后进先出规则，可以保证特定的存取顺序。
例如：翻转一组元素的顺序、铁路列车车辆调度。
练习
20. 有效的括号
输入：s = "()[]{}"
输出：true
# 方法1：使用栈
class Solution:
def isValid(self, s: str) -> bool:
stack = []
# 首先判断字符串的长度是否为奇数
if len(s)%2 == 1:
return False
# 用栈来完成判断
for i in s:
if i == '(' or i == '[' or i == '{':
stack.append(i)
else:
# 先判断栈是否为空
if len(stack) == 0:
return False
top = stack.pop()
if i == ')' and top != '(':
return False
elif i == ']' and top != '[':
return False
elif i == '}' and top != '{':
return False
# 最后看栈中元素是否为空
if len(stack) == 0:
return True
else:
return False
227. 基本计算器 II
整数除法仅保留整数部分。
输入：s = " 3+5 / 2 "
输出：5
输入：s = " 3/2 "
输出：1
class Solution:
def calculate(self, s: str) -> int:
# 运算符
cal = ['+', '-', '*', '/']
# 辅助栈
stack = []
index = 0
size = len(s)
# 默认运算,因为除了空字符串，第一个字符串肯定为数字
op = '+'
# 字符串遍历
while index < size:
# 对于空格的灵活处理
if s[index] == ' ':
index += 1
continue
# 对于数字字符的处理
if s[index].isdigit():
# 将字符串转化为数字
num = ord(s[index]) - ord('0')
# 对于连续多位数字字符串的处理
while index + 1 < size and s[index+1].isdigit():
# 需要注意及时更新索引
index += 1
num = 10*num + ord(s[index]) - ord('0')
# 得到数字之后和运算符一起压入栈中
if op == '+':
stack.append(num)
elif op == '-':
stack.append(0-num)
elif op == '*':
num_cal = stack.pop()
stack.append(num_cal*num)
# 整数除法仅保留整数部分
elif op == '/':
num_cal = stack.pop()
stack.append(int(num_cal/num))
# 对于运算符的处理
elif s[index] in cal:
op = s[index]
index += 1
return sum(stack)
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
# 方法1：借用一个辅助栈，同时存储两个值：当前值，当前的最小值
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
# 将元素压入栈
def push(self, val: int) -> None:
# 首先判断栈是否为空
if len(self.stack) == 0:
self.stack.append([val, val])
else:
self.stack.append([val, min(val, self.stack[-1][1])])
# 元素弹出
def pop(self) -> None:
self.stack.pop()
# 获取栈顶元素
def top(self) -> int:
return self.stack[-1][0]
# 获取栈的最小值
def getMin(self) -> int:
return self.stack[-1][1]
739. 每日温度
请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
# 使用一个栈
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
length = len(temperatures)
result = [0]*length
count = 0
for i in range(length):
# 当栈不为空，且栈顶索引对应的温度小于当前温度
while stack and temperatures[stack[-1]] < temperatures[i]:
# 索引出栈
index = stack.pop()
result[index] = i - index
stack.append(i)
return result
150. 逆波兰表达式求值
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
# 中缀表达式
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
cal = ['+', '-', '*', '/']
for tok in tokens:
if tok not in cal:
stack.append(int(tok))
else:
a = stack.pop()
b = stack.pop()
if tok == '+':
ans = b + a
elif tok == '-':
ans = b - a
elif tok == '*':
ans = b * a
elif tok == '/':
ans = int(b / a)
stack.append(ans)
return stack.pop()
394. 字符串解码
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
class Solution:
def decodeString(self, s: str) -> str:
stack_num = []
stack_str = []
s1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g','h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
num = 0
res = ''
for s_num in s:
if s_num.isdigit():
num = num*10 + int(s_num)
elif s_num in s1:
res += s_num
elif s_num == '[':
stack_num.append(num)
stack_str.append(res)
# 及时初始化
num = 0
res = ''
elif s_num ==']':
cur_num = stack_num.pop()
cur_res = stack_str.pop()
res = cur_res + cur_num * res
return res
946. 验证栈序列
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
# 对于pushed序列，每次进行push操作之后，有两种选择：继续push、弹出
# 进行实际模拟，查看结果是否相符
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
i = 0
for p in pushed:
stack.append(p)
while stack and stack[-1] == popped[i]:
stack.pop()
i += 1
# stack.append(p)
# 结束的判断：新建的栈是否都为空
return not stack
二、栈与深度优先搜索
深度优先搜索算法（Depth First Search）：英文缩写为 DFS。是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点，会尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
在深度优先遍历的过程中，我们需要将当前遍历节点 v 的相邻节点暂时存储起来，以便于在回退的时候可以继续访问它们。遍历到的节点顺序符合「后进先出」的特点，所以深度优先搜索可以通过「递归」或者「堆栈」来实现。
2.1 基于递归实现的深度优先搜索
def dfs_recrusive(graph, start, visited):
```
graph: 存储无向图的字典变量
start: 表示当前遍历边的开始节点
visited: 标记访问节点的set集合变量
```
visted = set()
visited.add(start)
# 遍历图
for end in graph[start]:
if end not in visited:
# 深度优先遍历节点
dfs_recursive(graph, end, visited)
2.2 基于栈实现的广度优先搜索
def dfs_stack(graph, start):
# 定义起始节点，并把起始节点进行标记并放在栈中
visited = set(start)
stack = [start]
# 递归结束的条件：栈为空
while stack:
node_u = stack.pop()
for node_v in graph[node_u]:
if node_v not in visited:
stack.append(node_v)
visted.appedn(node_v)
200. 岛屿数量
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
class Solution:
# 先定义深度优先搜索的算法
def dfs(self, grid, i, j):
# 计算行数和列数
n = len(grid)
m = len(grid[0])
# 递归的终止条件
if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == '0':
return 0
# 要及时将grid[i, j] = '1'的位置修改为'0',避免重复查找
grid[i][j] = '0'
# 对该点的上下左右进行检查
self.dfs(grid, i + 1, j)
self.dfs(grid, i, j + 1)
self.dfs(grid, i - 1, j)
self.dfs(grid, i, j - 1)
def numIslands(self, grid: List[List[str]]) -> int:
# 计数
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
# count += 1
self.dfs(grid, i, j)
count += 1
return count
133. 克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
# 深度优先算法
class Solution:
def dfs(self, node: 'Node', visited):
# 递归的终止条件
if node in visited:
return visited[node]
clone_node = Node(node.val, [])
# 新建复制节点 clone_node，赋值为 node.val。
visited[node] = clone_node
for neighbor in node.neighbors:
clone_node.neighbors.append(self.dfs(neighbor, visited))
return clone_node
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return node
# 使用字典变量 visited 存储访问过的节点，键值对为 原节点 : 新节点
visited = dict()
return self.dfs(node, visited)
1)实战-括号匹配
输入：(((()
输出：False
def parCheck(symbolString):
s = Stack()
balance = True
index = 0
while index < len(symbolString) and balance:
if symbolString[index] == '(':
s.push(symbolString[index])
else:
if s.isEmpty():
balance = False
else:
s.pop()
index += 1
if balance and s.isEmpty():
return True
else:
return False
print(parCheck('()(((())))'))
题目复杂化
要求判别 {{{{[[[((()))]]]}}}}
def parCheck(symbolString):
s = Stack()
balance = True
index = 0
while index < len(symbolString) and balance:
symbol = symbolString[index]
if symbol in '({[':
s.push(symbolString[index])
else:
if s.isEmpty():
balance = False
else:
# s.pop()
top = s.pop()
if not matches(top, symbol):
balance = False
index += 1
if balance and s.isEmpty():
return True
else:
return False
def matches(open, close):
opens = "([{"
closes = ")]}"
return opens.index(open) == closes.index(close)
print(parCheck('()(((([{(}]))))'))
2)十进制转二进制
def divideBy2(decNumber):
stack = Stack()
while decNumber > 0:
rem = decNumber % 2 # 求余数
stack.push(rem)
decNumber //= 2 # 取整数
binnumber = ''
while not stack.isEmpty():
binnumber += str(stack.pop())
return binnumber
print(divideBy2(5))
进阶：十进制转16以下任意进制
def divideBynum(decNumber, num):
stack = Stack()
digits = '0123456789ABCDEF'
while decNumber > 0:
rem = decNumber % num # 求余数
stack.push(rem)
decNumber //= num # 取整数
binnumber = ''
while not stack.isEmpty():
binnumber += digits[stack.pop()]
return binnumber
print(divideBynum(5, 16))
3)表达式转换
中缀表达式 A + B; A + B * C； (A + B) * C
前缀表达式 + AB ; + A * BC ； * +ABC
后缀表达式 AB + ; A B C * +； AB + C*
在中缀表达式中必须有的括号，在前缀和后缀表达式中消失了
思路
1 将中缀表达式转换为全括号的形式
2 将所有的操作符移动到子表达式所在的左括号（前缀）或者右括号（后缀）处，再删除其它所有的括号
def infixToPostfix(infixexpr):
# 记录操作符的优先级
prec = {}
prec['*'] = 3
prec['/'] = 3
prec['+'] = 2
prec['-'] = 2
prec['('] = 1
opStack = Stack()
postfixList = []
tokenList = infixexpr.split() # 将表达式解析为列表
# print(tokenList)
for token in tokenList:
if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':
postfixList.append(token)
elif token == '(':
opStack.push(token)
elif token == ')':
topToken = opStack.pop()
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
else:
while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList) # 合成后缀表达式字符串
a = '( A + B ) * C' # 输入字符必须用空格分开，不然无法split
print(infixToPostfix(a))
计算后序表达式
def compute1(s):
operandStack = Stack()
splitToken = s.split()
for token in splitToken:
if token in '0123456789':
operandStack.push(int(token))
else:
a = operandStack.pop()
b = operandStack.pop()
operandStack.push(compute2(token, a, b))
return operandStack.pop()
def compute2(token, a,b):
if token == '+':
c = a+b
elif token == '-':
c = a-b
elif token == '*':
c = a * b
else:
c = a/b
return c
print(compute1('1 2 + 1 *')) # 只能传入十以内数进行计算
网友评论