目录
一、828. 模拟栈 - AcWing题库
1.使用列表实现-摸鱼法
2.使用数组实现
二、AcWing 3302. 表达式求值 - AcWing
三、829. 模拟队列 - AcWing题库
四、830. 单调栈 - AcWing题库
五、154. 滑动窗口 - AcWing题库
一、828. 模拟栈 - AcWing题库
1.使用列表实现-摸鱼法
# 使用列表实现
'''
push x – 向栈顶插入一个数 x；
pop – 从栈顶弹出一个数；
empty – 判断栈是否为空；
query – 查询栈顶元素。
'''
def push(stack, x):stack.append(x)def pop(stack):stack.pop()def empty(stack):return 'YES' if len(stack) == 0 else 'NO'def query(stack):return stack[-1]if __name__ == '__main__':m = int(input())stack = []for _ in range(m):oper = input().split()if oper[0] == 'push':push(stack, int(oper[1]))elif oper[0] == 'pop':pop(stack)elif oper[0] == 'empty':print(empty(stack))else:print(query(stack))2.使用数组实现
多用数组实现。
# 使用数组实现
def init(N = 100010):global stack, topstack = [0] * Ntop = 0 # 栈顶指针def push(x):global stack, topstack[top] = xtop += 1def pop():global stack, toptop -= 1def empty():global stack, topreturn 'YES' if top <= 0 else 'NO' # 栈顶指针同时代表有多少个元素def query():global stack, topreturn stack[top - 1]m = int(input())
init()
for _ in range(m):oper = input().split()if oper[0] == 'push':push(int(oper[1]))elif oper[0] == 'pop':pop()elif oper[0] == 'empty':print(empty())else:print(query())二、AcWing 3302. 表达式求值 - AcWing
不会，思路来自题解（AcWing 3302. 表达式求值：多图讲解运算符优先级+详细代码注释 - AcWing），代码来自题解（AcWing 3302. 表达式求值 - AcWing）。
dic = {'(': 0, '+': 1, "-": 1, '*': 2, '/': 2} # 优先级
op = []
num = []def new_eval():# 计算函数b = num.pop() # 注意弹出顺序a = num.pop()c = op.pop()if c == '+':x = a + belif c == '-':x = a - belif c == '*':x = a * belse:x = int(a / b) # 向0取整num.append(x) # 压回栈s = input()
n = len(s)
i = 0
while i < n:c = s[i]if c.isdigit(): # 该函数检查字符是否为数字 x = 0while i < n and s[i].isdigit():x = x * 10 + int(s[i])i += 1# 循环结束时为运算符，退回一次进入下一次判断i -= 1 # 重要num.append(x)elif c == '(':# 左括号直接入栈op.append('(')elif c == ')':# 弹出进行运算，直到遇见'('while op[-1] != '(':new_eval()op.pop() # 左括号不要else:# 运算符while len(op) and dic[op[-1]] >= dic[c]:# 当运算符栈顶优先级大于等于遇到的运算符# 弹出运算# 当栈顶为左括号时直接进new_eval()# 入栈op.append(c)i += 1# 栈内剩余元素运算
while len(op):new_eval()
print(num[-1]) # 最后的栈顶即为运算结果三、829. 模拟队列 - AcWing题库
def init(N = 100010):global queue, front, rearqueue = [0] * Nfront = -1rear = -1def push(x):global queue, rearrear += 1queue[rear] = xdef pop():global frontfront += 1def empty():global front, rearreturn "YES" if front >= rear else "NO"def query():global queue, front, rearreturn queue[front + 1]m = int(input())
init()
for _ in range(m):oper = input().split()if oper[0] == "push":push(int(int(oper[1])))elif oper[0] == "pop":pop()elif oper[0] == "empty":print(empty())else:print(query())四、830. 单调栈 - AcWing题库
n = int(input())
nums = list(map(int, input().split()))
st = [] # 维护左边的单调递增栈
# ans = [-1] * n
for i, x in enumerate(nums):ans = -1 # 节省储存空间while st and st[-1] >= x: # 维护单调递增st.pop()# if st: ans[i] = st[-1]if st: ans = st[-1]print(ans, end = ' ')st.append(x)# # 输出
# for x in ans: print(x, end = ' ')五、154. 滑动窗口 - AcWing题库
思路来自题解（AcWing 154. 滑动窗口---海绵宝宝来喽 - AcWing）
当时没有想到怎么保证队内全都是窗口内的元素，答案：“当队头元素在窗口的左边的时候，弹出队头”，虽然不能保证队内一直没有窗口外的元素，但是能保证使用到的队内元素（队头）全是窗口内元素。当时是有想到这个方法的，但是以为不行，一下没转过来弯。
代码来自题解（AcWing 154. 滑动窗口 - AcWing）
队列储存索引而不是元素，通过储存索引使我们能够快速判断元素是否出窗口。
# 先进先出
# 单调队列（本质上是双端队列）
N = 1000010
queue = [0] * N # 储存下标
front, rear = 0, -1
n, k = map(int, input().split())
nums = list(map(int, input().split()))# 求最小值，单调递增队列
for i, x in enumerate(nums):# 弹出队头越界值while front <= rear and i - k >= queue[front]:front += 1# 弹出末尾大于x的值，注意这里是值比较while front <= rear and nums[queue[rear]] > x:rear -= 1# 将rear放入末尾rear += 1queue[rear] = i # 注意这里是下标而不是值# 输出，注意这里是k - 1，因为第一个窗口也要输出if i >= k - 1:print(nums[queue[front]], end = ' ')
print()front, rear = 0, -1 # 初始化
# 求最大值，单调递减队列
for i, x in enumerate(nums):# 队头弹出while front <= rear and i - k + 1 > queue[front]:front += 1# 队尾弹出，弹出操作均需要判断是否为空while front <= rear and nums[queue[rear]] < x:rear -= 1# 加入下标rear += 1queue[rear] = i# 输出if i >= k - 1:print(nums[queue[front]], end = ' ')完
感谢你看到这里！一起加油吧！
