1. 栈与队列的相爱相杀数据结构基础课今天咱们来聊聊数据结构里最经典的两个冤家——栈和队列。这俩就像咖啡店里的两种顾客栈是那种后进先出的傲娇客人LIFO最后一个来的反而最先被服务队列则是先进先出的老实人FIFO先来先得绝不插队。小知识栈的push/pop操作时间复杂度都是O(1)就像叠盘子你永远只能从最上面拿取队列的enqueue/dequeue同样O(1)像排队买奶茶后来的人必须乖乖站队尾。1.1 为什么需要互相实现面试官老爱问用栈实现队列这种问题不是故意刁难而是考察三个核心能力对数据结构本质的理解程度灵活运用基础工具解决问题的能力边界条件的处理意识就像给你螺丝刀却让你完成锤子的工作这种工具错配的题目最能检验基本功。接下来咱们就用四个经典题目把这套组合拳打明白。2. 232题用栈实现队列2.1 双栈魔术实现思路就像玩叠叠乐——用两个栈倒来倒去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 peek(self) - int: self._transfer() return self.out_stack[-1] def _transfer(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())关键点在于_transfer方法只有当输出栈空时才把输入栈的所有元素倒扣过来。这样最先进入的元素就会跑到输出栈的栈顶。2.2 时间复杂度分析操作平均时间复杂度最坏情况pushO(1)O(1)popO(1)O(n)peekO(1)O(n)虽然pop/peek最坏是O(n)但均摊下来仍是O(1)——就像银行排队虽然偶尔要等前面人办完所有业务但长期看等待时间还是稳定的。3. 225题用队列实现栈3.1 单队列的旋转舞步这次我们玩点更花的——用一个队列就能实现栈class MyStack: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) - int: return self.q.popleft()每次push时都把新元素后面的所有元素重新排队。这样最新元素永远在队首实现了栈的后进先出。3.2 双队列方案对比方法push时间复杂度pop时间复杂度空间复杂度单队列旋转O(n)O(1)O(n)双队列倒换O(1)O(n)O(n)实测发现单队列方案代码更简洁虽然push是O(n)但在LeetCode上跑分反而更高——因为Python的deque.popleft()非常高效。4. 20题有效的括号4.1 栈的经典战场括号匹配是栈的杀手级应用def isValid(s: str) - bool: pair {):(, ]:[, }:{} stack [] for char in s: if char in pair.values(): stack.append(char) elif stack and pair[char] stack[-1]: stack.pop() else: return False return not stack4.2 常见踩坑点忘记处理栈为空时遇到右括号的情况最后直接返回True而没检查栈是否为空用计数器替代栈无法处理([)]这种情况实战技巧面试时可以先问清楚字符串是否只包含括号字符这是边界条件检查的好习惯。5. 1047题删除字符串中的所有相邻重复项5.1 栈的消消乐这道题把栈当作消消乐的篮子def removeDuplicates(s: str) - str: stack [] for char in s: if stack and char stack[-1]: stack.pop() else: stack.append(char) return .join(stack)5.2 进阶思考如果要求删除重复项后字典序最小怎么办比如输入bcabc输出abc——这就变成了316题去除重复字母需要结合单调栈和哈希表来解决。6. 从题目看数据结构本质通过这四道题我们可以提炼出栈和队列的三个核心差异特性栈队列操作顺序LIFOFIFO典型操作push/popenqueue/dequeue应用场景函数调用、括号匹配BFS、缓存系统在实际工程中它们的变体应用更丰富单调栈解决Next Greater Element问题优先队列实现Dijkstra算法循环队列用于生产者-消费者模式7. 面试实战技巧白板编码时先口头说明思路面试官点头后再写边界条件要主动讨论空输入、极端用例等时间复杂度分析要区分均摊和最坏情况能给出多种解法时说明各自优劣比如用栈实现队列时可以主动提问需要我考虑线程安全吗——虽然题目通常不要求但能展示工程思维。8. 扩展训练建议想真正掌握这些数据结构建议用不同语言实现试试Go的slice或Java的LinkedList在本地IDE调试观察栈/队列的变化过程尝试改造题目如支持泛型、增加size方法等用可视化工具如visualgo.net动态观察我当年在准备面试时曾把栈和队列的题目打印出来贴在墙上每天刷牙时对着镜子口头解释一遍——肌肉记忆就是这么练出来的。