在编程的世界里，栈和队列是两个非常基础且重要的数据结构。它们不仅在算法设计中扮演着关键角色，而且在日常开发中也经常被用到。今天，我们就通过几个有趣的案例，深入探讨栈和队列的应用，带你领略编程的魅力。

1. 逆波兰表达式求值：栈的巧妙应用

逆波兰表达式是一种没有括号的算术表达式，操作符位于操作数之后。例如，“4 2 3 *”表示“4 2 + 3”。我们的目标是计算这个表达式的值。

思路：使用栈来存储操作数，遇到操作符时，从栈中弹出相应数量的操作数进行计算，并将结果压回栈中。

示例代码：

pythontokens = ["4", "-2", "/", "2", "-", "3", "-", "-"]stack_in = []for token in tokens:    if token not in {'+', '-', '*', '/'}:        stack_in.append(int(token))    else:        x1 = int(stack_in.pop())        x2 = int(stack_in.pop())        if token == '+':            stack_in.append(x2 + x1)        elif token == '-':            stack_in.append(x2 x1)        elif token == '*':            stack_in.append(x2 x1)        elif token == '/':            if x2 // x1 < 0:                if x2 % x1 == 0:                    stack_in.append(x2 // x1)                else:                    stack_in.append(x2 // x1 + 1)            else:                stack_in.append(x2 // x1)print(stack_in)

2. 滑动窗口最大值：双端队列的强大功能

滑动窗口是算法中常见的问题，特别是在处理连续子数组或子字符串时。我们的目标是找到每个滑动窗口的最大值。

正常思路：

pythonnums = [1, 3, -1, -3, 5, 3, 6, 7]k = 3slow = 0fast = slow + kstack = []while fast <= len(nums):    max_ = nums[slow]    for i in range(slow, fast):        if nums[i] > max_:            max_ = nums[i]    stack.append(max_)    slow += 1    fast += 1print(stack)

优化思路：使用双端队列（deque）来优化滑动窗口的最大值计算。

pythonfrom collections import dequedef maxSlidingWindow(nums, k):    result = []  # 用来保存结果    dq = deque()  # 初始化双端队列    for i in range(len(nums)):  # 遍历每一个元素        # 1. 移除不在窗口内的元素（即队列头部的索引小于当前窗口的左边界）        if dq and dq[0] < i k + 1:            dq.popleft()        # 2. 移除队列中所有比当前元素小的索引        while dq and nums[dq[-1]] < nums[i]:            dq.pop()        # 3. 将当前元素的索引加入队列        dq.append(i)        # 4. 当窗口大小达到k时，记录当前窗口的最大值        if i >= k 1:            result.append(nums[dq[0]])  # 队列头部的索引对应的是当前窗口的最大值    return result# 详细执行过程...

3. 前K个高频元素：排序与去重

在处理数据时，我们经常需要找出前K个高频出现的元素。例如，在给定的整数列表中，找出出现频率最高的前两个元素。

示例代码：

pythonnums = [1, 1, 1, 2, 2, 3]k = 2dict_ = {}for i in nums:    dict_[i] = dict_.get(i, 0) + 1dict_ = sorted(dict_.items(), key=lambda x: x[1], reverse=True)list_ = []for i in dict_[:k]:    list_.append(i[0])print(list_)

通过这些案例，我们可以看到栈和队列在编程中的强大功能和广泛应用。掌握这些基础数据结构，将为你在编程道路上打开更多的大门。希望本文能帮助你更好地理解和运用栈与队列，提升你的编程能力。