引言
在计算机科学和软件工程领域，栈（Stack）和队列（Queue）是两种最基础且最重要的线性数据结构。它们不仅是算法课程的核心内容，更是技术面试中高频出现的考点。无论是初级开发岗位还是高级架构师面试，面试官都倾向于通过栈和队列相关的问题来考察候选人的数据结构基础、算法思维以及问题解决能力。
本文将从栈与队列的基础概念出发，深入探讨它们的实现原理、操作特性，然后通过丰富的面试题库和实战案例，帮助你系统性地掌握相关知识，从而在技术面试中游刃有余。
一、栈（Stack）基础概念与实现
1.1 栈的定义与特性
栈是一种后进先出（LIFO, Last In First Out） 的线性数据结构。想象一个叠放盘子的场景：你只能从顶部添加或移除盘子，最后放上去的盘子会最先被取走。
栈的核心操作包括：
- 入栈（Push）：将元素添加到栈顶
- 出栈（Pop）：移除并返回栈顶元素
- 查看栈顶（Peek/Top）：返回栈顶元素但不移除
- 判空（isEmpty）：检查栈是否为空
1.2 栈的实现方式
栈可以通过数组或链表来实现。以下是使用Python实现的两种方式：
数组实现（顺序栈）
class ArrayStack:
def __init__(self, capacity=10):
self.capacity = capacity
self.stack = [None] * capacity
self.top = -1 # 栈顶指针
def push(self, item):
if self.is_full():
raise Exception("Stack overflow")
self.top += 1
self.stack[self.top] = item
def pop(self):
if self.is_empty():
raise Exception("Stack underflow")
item = self.stack[self.top]
self.top -= 1
return item
def peek(self):
if self.is_empty():
raise Exception("Stack is empty")
return self.stack[self.top]
def is_empty(self):
return self.top == -1
def is_full(self):
return self.top == self.capacity - 1
def size(self):
return self.top + 1
# 使用示例
stack = ArrayStack(5)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) # 输出: 3
print(stack.peek()) # 输出: 2
链表实现（链式栈）
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedStack:
def __init__(self):
self.head = None
self.size = 0
def push(self, item):
new_node = Node(item)
new_node.next = self.head
self.head = new_node
self.size += 1
def pop(self):
if self.is_empty():
raise Exception("Stack is empty")
item = self.head.value
self.head = self.head.next
self.size -= 1
return item
def peek(self):
if self.is_empty():
raise Exception("Stack is empty")
return self.head.value
def is_empty(self):
return self.head is None
def get_size(self):
return self.size
# 使用示例
stack = LinkedStack()
stack.push('a')
stack.push('b')
print(stack.pop()) # 输出: 'b'
print(stack.peek()) # 输出: 'a'
1.3 栈的时间复杂度分析
| 操作 | 数组实现 | 链表实现 |
|---|---|---|
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
| Peek | O(1) | O(1) |
| Space | O(n) | O(n) |
注意：数组实现的栈在扩容时需要O(n)时间，但均摊分析下仍为O(1)。
二、队列（Queue）基础概念与实现
2.1 队列的定义与特性
队列是一种先进先出（FIFO, First In First Out） 的线性数据结构。想象排队买票的场景：先到的人先得到服务，新来的人排在队尾。
队列的核心操作包括：
- 入队（Enqueue）：将元素添加到队尾
- 出队（Dequeue）：移除并返回队首元素
- 查看队首（Front）：返回队首元素但不移除
- 判空（isEmpty）：检查队列是否为空
2.2 队列的实现方式
队列同样可以通过数组或链表实现。以下是Python实现：
数组实现（循环队列）
class CircularQueue:
def __init__(self, capacity=10):
self.capacity = capacity
self.queue = [None] * capacity
self.front = 0 # 队首指针
self.rear = 0 # 队尾指针
self.size = 0
def enqueue(self, item):
if self.is_full():
raise Exception("Queue is full")
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.is_empty():
raise Exception("Queue is empty")
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
def peek(self):
if self.is_empty():
raise Exception("Queue is empty")
return self.queue[self.front]
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity
def get_size(self):
return self.size
# 使用示例
queue = CircularQueue(5)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue()) # 输出: 1
print(queue.peek()) # 输出: 2
链表实现（链式队列）
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedQueue:
def __init__(self):
self.front = None
self.rear = None
self.size = 0
def enqueue(self, item):
new_node = Node(item)
if self.is_empty():
self.front = self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
self.size += 1
def dequeue(self):
if self.is_empty():
raise Exception("Queue is empty")
item = self.front.value
self.front = self.front.next
if self.front is None:
self.rear = None
self.size -= 1
return item
def peek(self):
if self.is_empty():
raise Exception("Queue is empty")
return self.front.value
def is_empty(self):
return self.front is None
def get_size(self):
return self.size
# 使用示例
queue = LinkedQueue()
queue.enqueue('a')
queue.enqueue('b')
print(queue.dequeue()) # 输出: 'a'
print(queue.peek()) # 输出: 'b'
2.3 队列的时间复杂度分析
| 操作 | 数组实现（循环队列） | 链表实现 |
|---|---|---|
| Enqueue | O(1) | O(1) |
| Dequeue | O(1) | O(1) |
| Front | O(1) | O(1) |
| Space | O(n) | O(n) |
三、栈与队列的高级变种
3.1 双端队列（Deque）
双端队列允许在两端进行插入和删除操作，结合了栈和队列的特性。
from collections import deque
# Python内置的deque实现
dq = deque()
# 从右侧操作（类似栈）
dq.append(1) # 入栈
dq.append(2)
print(dq.pop()) # 出栈，输出: 2
# 从左侧操作（类似队列）
dq.appendleft(3)
print(dq.popleft()) # 出队，输出: 3
# 双端操作
dq.append(4)
dq.appendleft(5)
print(dq) # 输出: deque([5, 1, 4])
3.2 优先队列（Priority Queue）
优先队列根据优先级而非插入顺序来处理元素。通常使用堆（Heap）实现。
import heapq
# 最小堆实现的优先队列
pq = []
# 入队（元素为元组：(优先级, 元素)）
heapq.heappush(pq, (3, 'task3'))
heapq.heappush(pq, (1, 'task1'))
heapq.heappush(pq, (2, 'task2'))
# 出队（优先级最低的先出队）
print(heapq.heappop(pq)) # 输出: (1, 'task1')
print(heapq.heappop(pq)) # 输出: (2, 'task2')
3.3 单调栈与单调队列
单调栈：栈内元素保持单调递增或递减的顺序，常用于解决”下一个更大元素”问题。
def next_greater_element(nums):
"""找到每个元素的下一个更大元素"""
stack = []
result = [-1] * len(nums)
for i in range(len(nums)):
# 当栈不为空且当前元素大于栈顶元素时
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
# 示例
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # 输出: [4, 2, 4, -1, -1]
单调队列：队列内元素保持单调性，常用于滑动窗口最大值问题。
from collections import deque
def max_sliding_window(nums, k):
"""滑动窗口最大值"""
dq = deque()
result = []
for i in range(len(nums)):
# 移除队列中所有小于当前元素的元素
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
# 添加当前索引
dq.append(i)
# 移除超出窗口的索引
if dq[0] <= i - k:
dq.popleft()
# 当窗口形成后，记录最大值
if i >= k - 1:
result.append(nums[dq[0]])
return result
# 示例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k)) # 输出: [3, 3, 5, 5, 6, 7]
四、经典面试题库详解
4.1 栈相关面试题
题目1：有效的括号（LeetCode 20）
问题描述：给定一个只包含字符 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 的字符串，判断输入的字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
解题思路：使用栈来匹配括号。遇到左括号入栈，遇到右括号时检查栈顶是否为对应的左括号。
代码实现：
def is_valid_parentheses(s):
"""判断括号字符串是否有效"""
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping.values(): # 左括号
stack.append(char)
elif char in mapping: # 右括号
if not stack or stack.pop() != mapping[char]:
return False
else:
# 非括号字符，根据需求处理
continue
return not stack
# 测试用例
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("([)]")) # False
print(is_valid_parentheses("{[]}")) # True
时间复杂度：O(n)，n为字符串长度 空间复杂度：O(n)，最坏情况下所有字符都是左括号
题目2：最小栈（LeetCode 155）
问题描述：设计一个支持 push、pop、top 操作，并能在常数时间内检索最小元素的栈。
解题思路：使用两个栈，一个存储所有元素，另一个存储最小值历史。
代码实现：
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
# 如果最小栈为空或当前值小于等于最小栈顶，则入栈
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if not self.stack:
return
val = self.stack.pop()
# 如果弹出的值等于最小栈顶，则同时弹出最小栈
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1] if self.stack else None
def get_min(self):
return self.min_stack[-1] if self.min_stack else None
# 测试
min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print(min_stack.get_min()) # 输出: -3
min_stack.pop()
print(min_stack.top()) # 输出: 0
print(min_stack.get_min()) # 输出: -2
时间复杂度：所有操作均为O(1) 空间复杂度：O(n)，需要额外空间存储最小值
题目3：逆波兰表达式求值（LeetCode 150）
问题描述：根据逆波兰表示法（后缀表达式）计算表达式的值。逆波兰表达式的特点是操作符在操作数之后。
解题思路：使用栈存储操作数，遇到操作符时弹出两个操作数进行计算，结果重新入栈。
代码实现：
def eval_rpn(tokens):
"""计算逆波兰表达式的值"""
stack = []
operators = {'+', '-', '*', '/'}
for token in tokens:
if token not in operators:
# 操作数，直接入栈
stack.append(int(token))
else:
# 操作符，弹出两个操作数
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
# 注意整数除法向零取整
stack.append(int(a / b))
return stack[0]
# 测试用例
tokens = ["2", "1", "+", "3", "*"]
print(eval_rpn(tokens)) # 输出: 9
tokens = ["4", "13", "5", "/", "+"]
print(eval_rpn(tokens)) # 输出: 6
时间复杂度：O(n)，n为tokens数量 空间复杂度：O(n)，栈的空间
4.2 队列相关面试题
题目1：用队列实现栈（LeetCode 225）
问题描述：使用队列实现栈的下列操作：
- push(x)：将元素 x 推入栈顶
- pop()：移除并返回栈顶元素
- top()：返回栈顶元素
- empty()：返回栈是否为空
解题思路：使用两个队列，一个主队列，一个辅助队列。push操作时，先将元素加入辅助队列，然后将主队列的所有元素移动到辅助队列，最后交换两个队列。
代码实现：
from collections import deque
class MyStack:
def __init__(self):
self.queue1 = deque() # 主队列
self.queue2 = deque() # 辅助队列
def push(self, x):
# 将新元素加入辅助队列
self.queue2.append(x)
# 将主队列的所有元素移动到辅助队列
while self.queue1:
self.queue2.append(self.queue1.popleft())
# 交换队列
self.queue1, self.queue2 = self.queue2, self.queue1
def pop(self):
if not self.queue1:
return None
return self.queue1.popleft()
def top(self):
if not self.queue1:
return None
return self.queue1[0]
def empty(self):
return not self.queue1
# 测试
stack = MyStack()
stack.push(1)
stack.push(2)
print(stack.top()) # 输出: 2
print(stack.pop()) # 输出: 2
print(stack.empty()) # 输出: False
时间复杂度：push操作为O(n)，其他操作为O(1) 空间复杂度：O(n)
题目2：用栈实现队列（LeetCode 232）
问题描述：使用栈实现队列的下列操作：
- push(x)：将元素 x 推入队列尾部
- pop()：移除并返回队列头部的元素
- peek()：返回队列头部的元素
- empty()：返回队列是否为空
解题思路：使用两个栈，一个输入栈，一个输出栈。push操作时，将元素压入输入栈。pop或peek操作时，如果输出栈为空，则将输入栈的所有元素弹出并压入输出栈，然后从输出栈操作。
代码实现：
class MyQueue:
def __init__(self):
self.input_stack = []
self.output_stack = []
def push(self, x):
self.input_stack.append(x)
def pop(self):
if not self.output_stack:
# 将输入栈的所有元素移动到输出栈
while self.input_stack:
self.output_stack.append(self.input_stack.pop())
if not self.output_stack:
return None
return self.output_stack.pop()
def peek(self):
if not self.output_stack:
while self.input_stack:
self.output_stack.append(self.input_stack.pop())
if not self.output_stack:
return None
return self.output_stack[-1]
def empty(self):
return not self.input_stack and not self.output_stack
# 测试
queue = MyQueue()
queue.push(1)
queue.push(2)
print(queue.peek()) # 输出: 1
print(queue.pop()) # 输出: 1
print(queue.empty()) # 输出: False
时间复杂度：pop和peek操作均摊为O(1)，push操作为O(1) 空间复杂度：O(n)
题目3：滑动窗口最大值（LeetCode 239）
问题描述：给定一个数组 nums 和一个大小为 k 的滑动窗口，找出滑动窗口里的最大值。
解题思路：使用单调队列（双端队列）来维护窗口内的最大值。队列中存储数组的索引，保持队列中索引对应的值单调递减。
代码实现：
from collections import deque
def max_sliding_window(nums, k):
"""滑动窗口最大值"""
if not nums or k == 0:
return []
dq = deque()
result = []
for i in range(len(nums)):
# 移除队列中所有小于当前元素的元素
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
# 添加当前索引
dq.append(i)
# 移除超出窗口的索引
if dq[0] <= i - k:
dq.popleft()
# 当窗口形成后，记录最大值
if i >= k - 1:
result.append(nums[dq[0]])
return result
# 测试用例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k)) # 输出: [3, 3, 5, 5, 6, 7]
nums = [1]
k = 1
print(max_sliding_window(nums, k)) # 输出: [1]
时间复杂度：O(n)，每个元素最多入队和出队一次 空间复杂度：O(k)，队列最多存储k个元素
五、栈与队列的实战应用场景
5.1 深度优先搜索（DFS）与栈
DFS通常使用递归实现，但也可以显式使用栈来避免递归的系统开销。
# 二叉树的DFS遍历（非递归，使用栈）
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_traversal(root):
"""前序遍历：根->左->右"""
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
# 先右后左，因为栈是后进先出
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
# 示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_traversal(root)) # 输出: [1, 2, 4, 5, 3]
5.2 广度优先搜索（BFS）与队列
BFS通常使用队列来实现，按层次遍历图或树。
from collections import deque
# 二叉树的BFS遍历（层序遍历）
def level_order_traversal(root):
"""层序遍历"""
if not root:
return []
queue = deque([root])
result = []
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
# 示例
print(level_order_traversal(root)) # 输出: [[1], [2, 3], [4, 5]]
5.3 表达式求值与语法分析
编译器中的表达式求值通常使用栈来处理运算符优先级。
def infix_to_postfix(expression):
"""中缀表达式转后缀表达式"""
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
stack = []
output = []
for token in expression.split():
if token.isdigit():
output.append(token)
elif token in precedence:
while (stack and stack[-1] != '(' and
precedence.get(stack[-1], 0) >= precedence[token]):
output.append(stack.pop())
stack.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
if stack:
stack.pop() # 弹出左括号
while stack:
output.append(stack.pop())
return ' '.join(output)
# 示例
expression = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
print(infix_to_postfix(expression)) # 输出: 3 4 2 * 1 5 - 2 3 ^ ^ / +
5.4 撤销/重做功能（Undo/Redo）
在文本编辑器中，撤销和重做功能通常使用两个栈来实现。
class TextEditor:
def __init__(self):
self.text = ""
self.undo_stack = []
self.redo_stack = []
def write(self, text):
# 保存当前状态到撤销栈
self.undo_stack.append(self.text)
self.redo_stack.clear() # 清空重做栈
self.text += text
def undo(self):
if not self.undo_stack:
return
# 保存当前状态到重做栈
self.redo_stack.append(self.text)
self.text = self.undo_stack.pop()
def redo(self):
if not self.redo_stack:
return
# 保存当前状态到撤销栈
self.undo_stack.append(self.text)
self.text = self.redo_stack.pop()
def get_text(self):
return self.text
# 测试
editor = TextEditor()
editor.write("Hello")
editor.write(" World")
print(editor.get_text()) # 输出: "Hello World"
editor.undo()
print(editor.get_text()) # 输出: "Hello"
editor.redo()
print(editor.get_text()) # 输出: "Hello World"
六、面试技巧与常见陷阱
6.1 面试常见问题类型
- 基础概念题：考察栈和队列的定义、特性、实现方式
- 算法应用题：如括号匹配、表达式求值、滑动窗口等
- 设计题：如设计最小栈、用队列实现栈等
- 变种题：如双端队列、优先队列、单调栈/队列的应用
6.2 面试回答技巧
- 明确问题：确保完全理解题目要求，特别是边界条件
- 分析复杂度：主动分析时间和空间复杂度
- 考虑优化：提出可能的优化方案
- 代码规范：写出清晰、可读的代码，注意变量命名和注释
- 测试用例：主动提供测试用例验证代码正确性
6.3 常见陷阱与注意事项
数组实现的边界条件：
- 栈：栈空时pop/peek，栈满时push
- 队列：队空时dequeue，队满时enqueue
- 循环队列：判满条件（size或rear+1%capacity==front）
递归与迭代的选择：
- 递归简洁但可能栈溢出
- 迭代（使用栈/队列）可控但代码稍复杂
语言特性：
- Python的list可以作为栈使用，但作为队列效率低（pop(0)是O(n)）
- Java的Stack类已过时，推荐使用Deque
- C++的stack和queue是容器适配器
内存管理：
- 链表实现要注意内存泄漏
- 数组实现要注意扩容策略
七、进阶学习资源
7.1 推荐书籍
- 《算法导论》（Thomas H. Cormen等）- 经典算法教材
- 《数据结构与算法分析》（Mark Allen Weiss）- 清晰易懂
- 《剑指Offer》- 面试算法题库
7.2 在线资源
- LeetCode：https://leetcode.com/（大量栈队列相关题目）
- GeeksforGeeks：https://www.geeksforgeeks.org/（详细算法解释）
- 牛客网：https://www.nowcoder.com/（国内面试题库）
7.3 实践项目建议
- 实现一个简单的表达式计算器
- 设计一个支持撤销/重做的文本编辑器
- 实现一个浏览器的前进/后退功能
- 开发一个简单的任务调度器（使用优先队列）
八、总结
栈和队列作为基础数据结构，在算法和系统设计中扮演着重要角色。通过本文的学习，你应该已经掌握了：
- 基础概念：栈和队列的定义、特性、实现方式
- 高级变种：双端队列、优先队列、单调栈/队列
- 经典算法：括号匹配、表达式求值、滑动窗口等
- 实战应用：DFS/BFS、撤销/重做、语法分析等
- 面试技巧：问题分析、代码实现、复杂度分析
最后建议：
- 多刷LeetCode相关题目（标签：Stack, Queue）
- 理解每种数据结构的适用场景
- 在实际项目中尝试应用这些数据结构
- 保持对算法复杂度的敏感度
记住，面试不仅考察知识掌握程度，更考察问题解决能力和思维过程。在面试中，清晰地表达你的思路，即使最终没有完全解决，也能给面试官留下良好印象。
祝你在技术面试中取得优异成绩！