一：栈
1、栈的特性：栈和队列不一样；队列是先进先出；而队列是先进后出；后进后出！
2、栈的常见操作
def create_stack():
stack=[]#在python中；通常用列表实现栈的操作
return stack
def push(stack,data):
stack.append(data)#将data压入栈中
def peek(stack):
return stack[-1]#返回栈顶元素
def pop(stack):
return stack.pop()#弹出栈顶元素
def is_empty(stack):
return len(stack)==0#判断栈是否为空
def size(stack):
return len(stack)#返回栈的大小
def print_stack(stack):
for i in stack:
print(i,end=' ')#打印栈中的元素
二：刷题
题目20有效的括号
#方法1：使用计数实现
'''def func(s):
count=0
for i in s:
if i=='(':
count+=1
elif i==')':
count-=1
if count<0:
return False
return True
s="()[]{}"
print(func(s)) # True'''
#方法2：使用栈实现
def func(s):
stack = []
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack or stack.pop() != '(':#只要条件成立一个就返回False
return False
return not stack#判断列表是否为空；如果为空的话返回TRUE，否则返回FALSE
s="()[]{}"
print(func(s)) # True
#方法3：使用消除法实现
'''def func(s):
while '{}' in s or '()' in s or '[]' in s:
s=s.replace('{}','')
s=s.replace('()','')
s=s.replace('[]','')
return s==''#检查最后的字符串是不是为空；如果是空的返回True，否则返回False
#就是一个简答的灯饰
s="()[]{}"
print(func(s)) # True'''
题目496下一个更大的元素
#暴力解法
def next_greater_element(nums1, nums2):
# 初始化结果数组
ans = []
# 遍历 nums1 中的每一个元素
for x in nums1:
# 在 nums2 中找到 x 的位置
found = False
for i in range(len(nums2)):
if nums2[i] == x:
found = True
# 如果已经找到了 x，在其右侧寻找第一个更大的元素
if found and nums2[i] > x:
ans.append(nums2[i])
break
else:
# 如果没有找到比 x 更大的元素，记录 -1
ans.append(-1)
return ans
#单调栈
def next_greater_element(nums1, nums2):
# 创建一个字典来存储每个元素的下一个更大元素
next_greater = {}
# 创建一个栈用于存放还没有找到下一个更大元素的元素
stack = []
# 遍历 nums2
for num in nums2:
# 如果栈顶元素比当前元素小，则找到栈顶元素的下一个更大元素
while stack and stack[-1] < num:
next_greater[stack.pop()] = num
# 将当前元素压入栈中
stack.append(num)
# 栈中剩余的元素都是没有下一个更大元素的，设置为 -1
while stack:
next_greater[stack.pop()] = -1
# 对 nums1 中的每个元素，返回它的下一个更大元素
return [next_greater[num] for num in nums1]