摘要：栈和队列是编程竞赛中高频出现的核心数据结构，理解其特性及应用场景是解题的关键。以下为栈与队列的常见题型及解法总结：
栈和队列是编程竞赛中高频出现的核心数据结构，理解其特性及应用场景是解题的关键。以下为栈与队列的常见题型及解法总结：
一、基础操作与实现
栈（LIFO）Ø 操作：push（压栈）、pop（弹栈）、top（栈顶元素）。
Ø 应用场景：括号匹配、逆波兰表达式、DFS非递归实现。
Ø 实现：数组或链表均可，C++中可用std::stack，Python用list（注意append和pop）。
队列（FIFO）Ø 操作：enqueue（入队）、dequeue（出队）、front（队首元素）。
Ø 应用场景：BFS、滑动窗口、任务调度。
Ø 实现：C++用std::queue或std::deque，Python用collections.deque（高效两端操作）。
二、高频竞赛题型与解法
1. 括号匹配（LeetCode 20）
问题：判断字符串中的括号是否有效闭合。解法：用栈模拟，左括号入栈，右括号匹配栈顶元素。关键点：栈最终须为空，否则存在多余左括号。示例代码：python
def isValid(s: str) -> bool:
stack =
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top = stack.pop if stack else '#'
if mapping[char] != top:
return False
else:
stack.append(char)
return not stack
2. 用栈实现队列（LeetCode 232）
解法：双栈（输入栈 + 输出栈）。Ø 入队：直接压入输入栈。
Ø 出队：若输出栈为空，将输入栈元素全部弹出压入输出栈。
代码核心：python
class MyQueue:
def __init__(self):
self.in_stack =
self.out_stack =
def push(self, x: int) -> None:
self.in_stack.append(x)
def pop(self) -> int:
self._transfer
return self.out_stack.pop
def _transfer(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop)
3. 下一个更大元素（LeetCode 496, 503）
问题：数组每个元素的下一个更大元素（含循环数组）。解法：单调递减栈。Ø 线性数组：遍历时弹出比当前元素小的栈顶元素，记录结果。
Ø 循环数组：遍历长度翻倍（或两次遍历），用i % n模拟循环。
示例代码（循环数组）：python
def nextGreaterElements(nums: List[int]) -> List[int]:
n = len(nums)
res = [-1] * n
stack =
for i in range(2 * n):
while stack and nums[i % n] > nums[stack[-1]]:
res[stack.pop] = nums[i % n]
if i
stack.append(i)
return res
4. 滑动窗口最大值（LeetCode 239）
解法：单调双端队列（保存可能成为最大值的索引）。Ø 入队：移除队尾小于当前值的元素，确保队列递减。
Ø 出队：检查队首是否在窗口内。
代码实现：python
复制
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
from collections import deque
q = deque
res =
for i, num in enumerate(nums):
while q and nums[q[-1]]
q.pop
q.append(i)
if q[0] == i - k: # 移除出窗口的元素
q.popleft
if i >= k - 1:
res.append(nums[q[0]])
return res
三、进阶技巧总结
单调栈/队列：通过维护结构内元素的单调性，将时间复杂度优化至O(n)。边界处理：栈空时的操作、窗口越界、循环数组的索引取模。空间优化：合理利用双栈、双队列减少冗余操作。掌握这些核心题型及模板，能高效解决多数栈与队列相关的竞赛题目。
来源：老客数据一点号
