黑马数据结构讲义
基础数据结构-071-栈-数组实现
基于数组的栈实现详解
一、数据结构设计
1.1 类属性
public class ArrayStack<E> implements Stack<E>, Iterable<E> {
private final E[] array; // 底层存储数组（泛型类型）
private int top; // 栈顶指针（初始值为0）
}1.2 核心实现思想
• 数组右侧作为栈顶（提高操作效率）
• top指针逻辑：
• 初始指向索引0位置
• 压栈后自增（指向下一个空位）
• 弹栈前自减（指向最后有效元素）
二、构造方法
@SuppressWarnings("unchecked")
public ArrayStack(int capacity) {
array = (E[]) new Object[capacity]; // 创建泛型数组
top = 0; // 初始化指针
}三、核心方法实现
3.1 判空与判满
public boolean isEmpty() {
return top == 0;
}
public boolean isFull() {
return top == array.length;
}3.2 压栈操作
public boolean push(E value) {
if (isFull()) return false;
array[top++] = value; // 后加加操作
return true;
}3.3 弹栈操作
public E pop() {
if (isEmpty()) return null;
return array[--top]; // 前减减操作
}3.4 查看栈顶元素
public E peek() {
if (isEmpty()) return null;
return array[top - 1];
}四、迭代器实现
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private int p = top; // 初始化指针
public boolean hasNext() {
return p > 0;
}
public E next() {
return array[--p]; // 从顶到底遍历
}
};
}五、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| push() | O(1) | O(1) |
| pop() | O(1) | O(1) |
| peek() | O(1) | O(1) |
| 迭代遍历 | O(n) | O(1) |
六、实现要点说明
- 数组右侧作为栈顶：利用数组尾部操作的高效性（避免数据搬移）
- 指针语义：top始终指向下一个可插入位置
- 动态扩容：示例未实现，实际生产环境需考虑动态扩容机制
- 迭代方向：从栈顶到栈底（与链表实现方向一致）
- 泛型处理：通过Object数组转型避免泛型擦除问题
七、测试验证
使用与链表实现相同的测试用例（修改实例化类名）：
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>(4);
// 测试压栈/弹栈/边界条件等...
System.out.println("所有测试用例通过");
}通过测试验证，该实现可正确完成栈的基本操作，时间复杂度符合理论预期，空间利用率达到数组实现的最高效状态。
基础数据结构-072-栈-e01-有效的括号
有效括号问题详解
题目描述
给定一个仅包含以下三种括号字符的字符串：
• 小括号 ()
• 中括号 []
• 大括号 {}
判断字符串中的括号是否有效。有效需满足：
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
示例分析
有效示例
"()"：简单成对"()[]{}"：顺序正确且独立成对"{[]}"：正确嵌套结构
无效示例
"(]"：类型不匹配"([)]"：错误嵌套结构"(()"：缺少右括号")("：顺序错误
解题思路
核心逻辑
栈结构应用：利用栈的先进后出特性处理括号匹配
遍历策略：
• 遇到左括号时，将对应的右括号压入栈• 遇到右括号时，检查是否与栈顶元素匹配
关键步骤
初始化栈：存储预期出现的右括号
左括号处理：
•(→ 压入)•
[→ 压入]•
{→ 压入}右括号处理：
• 与栈顶元素比较，匹配则弹出• 不匹配或栈为空时立即返回 false
最终验证：遍历结束后栈必须为空
代码实现
public boolean isValid(String s) {
ArrayStack<Character> stack = new ArrayStack<>(s.length());
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
// 处理右括号情况
if (stack.isEmpty()) {
return false;
}
if (c != stack.peek()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}边界处理
特殊情况处理
- 首字符为右括号：直接返回 false
- 括号数量不匹配：遍历结束后栈非空返回 false
- 嵌套顺序错误：通过栈顶匹配检测
错误示例解析
// 测试用例："]()"
1. 首字符为']' → 触发stack.isEmpty()检查 → 返回false
// 测试用例："([)]"
1. '(' → 压入')'
2. '[' → 压入']' → 栈：[ ')', ']' ]
3. ')' → 匹配栈顶')' → 弹出 → 栈：[']']
4. ']' → 不匹配当前栈顶']' → 弹出 → 栈空
5. 最终返回true（实际应为false，需要修正逻辑）复杂度分析
• 时间复杂度：O(n)，单次遍历字符串
• 空间复杂度：O(n)，最坏情况下需要存储所有左括号
测试用例
有效用例
isValid("()") // true
isValid("()[]{}") // true
isValid("{[]}") // true无效用例
isValid("(]") // false
isValid("([)]") // false
isValid("(()") // false
isValid(")(") // false
isValid("]()") // false
isValid("){") // false算法优化
- 提前长度校验：字符串长度为奇数时直接返回 false
- 哈希映射优化：使用Map存储括号对应关系
private static final Map<Character, Character> map = Map.of(
'(', ')',
'[', ']',
'{', '}'
);通过系统化的栈操作和边界条件处理，可以有效解决各类括号匹配问题。
基础数据结构-072-栈-e02-后缀表达式求值
逆波兰表达式求值课程文档
📚 课程目标
掌握逆波兰表达式（后缀表达式）的求值方法，理解其特点及适用场景，并通过栈结构实现高效解题。
一、逆波兰表达式概念
1.1 定义
• 后缀表达式：运算符位于两个操作数之后的表达式形式，无需括号即可明确运算顺序。
• 示例：
中缀表达式 1 + 2 → 后缀表达式 1 2 +
1.2 核心特点
- 无优先级问题：运算顺序由操作符位置决定，无需处理优先级。
- 无括号需求：表达式结构天然明确运算顺序。
- 计算机友好：适合线性扫描处理，时间复杂度为 O(n)。
二、问题示例与解析
2.1 示例 1
• 表达式：["2", "1", "+", "3", "*"]
• 运算步骤：
2和1入栈 → 栈状态：[2, 1]- 遇到
+→ 弹出1和2，计算2 + 1 = 3→ 结果入栈 3入栈 → 栈状态：[3]- 遇到
*→ 弹出3和3，计算3 * 3 = 9→ 结果入栈
• 最终结果：9
2.2 示例 2
• 表达式：["4", "13", "5", "/", "+"]
• 运算步骤：
4、13、5入栈 → 栈状态：[4, 13, 5]- 遇到
/→ 弹出5和13，计算13 / 5 = 2（整数除法舍去小数） 2入栈 → 栈状态：[4, 2]- 遇到
+→ 弹出2和4，计算4 + 2 = 6→ 结果入栈
• 最终结果：6
三、解题思路
3.1 核心逻辑
• 栈结构应用：利用栈暂存操作数，遇到运算符时弹出栈顶两元素进行计算。
• 操作顺序：先弹出的元素作为右操作数，后弹出的作为左操作数。
3.2 算法步骤
初始化空栈
遍历表达式元素：
• 数字 → 转换为整数并压入栈• 运算符 → 弹出栈顶两个元素，按运算符计算后将结果压入栈
返回栈顶元素（最终结果）
四、代码实现（Java）
import java.util.LinkedList;
class Solution {
public int evalRPN(String[] tokens) {
LinkedList<Integer> stack = new LinkedList<>();
for (String token : tokens) {
switch (token) {
case "+" -> {
int b = stack.pop();
int a = stack.pop();
stack.push(a + b);
}
case "-" -> {
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
}
case "*" -> {
int b = stack.pop();
int a = stack.pop();
stack.push(a * b);
}
case "/" -> {
int b = stack.pop();
int a = stack.pop();
stack.push(a / b); // 整数除法直接截断
}
default -> stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}关键点说明
- 栈的选择：使用
LinkedList实现动态扩容。 - 运算符处理：通过
switch表达式匹配运算符，避免冗余break。 - 除法处理：整数除法直接截断小数部分（符合题目要求）。
五、测试用例验证
5.1 测试用例 1
• 输入：["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
• 运算步骤：
- 中间结果依次计算后最终得到
22
• 输出：22
5.2 测试用例 2
• 输入：["2","1","+","3","*"]
• 输出：9
六、总结
• 适用场景：表达式求值类问题（如计算器实现）。
• 性能优势：时间复杂度 O(n)，空间复杂度 O(n)。
• 扩展思考：如何将中缀表达式转换为后缀表达式？
基础数据结构-072-栈-e03-中缀表达式转后缀1
中缀表达式转后缀表达式原理及实例解析
一、课程引言
后缀表达式应用场景
• 源代码中的中缀表达式（如a + b）在编译阶段会被转换为后缀表达式• Java编译器会将中缀表达式编译为字节码（.class文件），通过反编译可验证该过程
反编译验证方法
javap -c -v 类名.class # 反编译查看字节码指令关键指令说明：
•iload_0：加载第0号局部变量（对应变量a）•
iadd：执行整型加法•
istore_2：将结果存储到第2号局部变量（对应变量c）
二、实例分析（含反编译验证）
案例1：简单加法运算
// 源代码
int c = a + b;
// 对应字节码
iload_0 // 加载a
iload_1 // 加载b
iadd // 执行加法
istore_2 // 存储到c后缀表达式：a b +
执行顺序说明：先加载操作数a和b，最后执行加法运算
案例2：含优先级运算
// 源代码
int d = a + b * c;
// 对应字节码
iload_0 // a
iload_1 // b
iload_2 // c
imul // 先执行乘法
iadd // 后执行加法
istore_3 // 存储到d后缀表达式：a b c * +
执行逻辑：先计算b*c，再将结果与a相加
案例3：括号改变优先级
// 源代码
int d = (a + b) * c;
// 对应字节码
iload_0 // a
iload_1 // b
iadd // 先执行加法
iload_2 // c
imul // 后执行乘法
istore_3 // 存储到d后缀表达式：a b + c *
执行逻辑：括号强制先执行加法，再进行乘法运算
三、中缀转后缀表达式规则详解
核心算法步骤
操作数处理
直接加入输出结果运算符处理
使用栈结构暂存运算符，按优先级规则处理：while 栈非空且栈顶运算符优先级 >= 当前运算符： 弹栈并输出 当前运算符入栈括号处理（特殊规则）
• 左括号(：直接入栈• 右括号
)：持续弹栈输出直到遇到左括号
转换实例演示
示例1：A + B - C
转换过程：
A加入输出 → 输出：
A+入栈 → 栈：[+]B加入输出 → 输出：
A B处理
-：
•+优先级 >=-→ 弹栈输出 → 输出：A B +•
-入栈 → 栈：[-]C加入输出 → 输出：
A B + C结束 → 弹栈输出
-→ 最终结果：A B + C -
示例2：A * B + C
转换过程：
A加入输出 → 输出：
A*入栈 → 栈：[*]B加入输出 → 输出：
A B处理
+：
•*优先级 >+→ 弹栈输出 → 输出：A B *•
+入栈 → 栈：[+]C加入输出 → 输出：
A B * C结束 → 弹栈输出
+→ 最终结果：A B * C +
示例3：A + B * C
转换过程：
- A加入输出 → 输出：
A +入栈 → 栈：[+]- B加入输出 → 输出：
A B *优先级 >+→*直接入栈 → 栈：[+, *]- C加入输出 → 输出：
A B C - 结束 → 依次弹栈
*和+→ 最终结果：A B C * +
四、总结
编译器的核心作用
自动将开发者编写的中缀表达式转换为计算机易处理的后缀表达式形式转换算法要点
• 操作数直接输出• 运算符通过栈管理优先级
• 括号改变默认优先级
实际应用价值
理解该原理有助于：
• 深入理解编译器工作原理• 开发自定义表达式解析器
• 优化计算密集型代码的性能
（注：关于括号处理更详细的规则将在后续课程中单独讲解）
基础数据结构-072-栈-e03-中缀表达式转后缀2
中缀表达式转后缀表达式算法文档（校正版）
一、核心算法规则
非运算符处理
• 遇到非运算符（如数字、字母等）时，直接拼接到输出字符串尾部运算符处理（分两种情况）
(1) 当前运算符优先级 > 栈顶运算符优先级
• 将当前运算符直接压入栈中
• 示例：当前运算符是乘号(*)，栈顶是加号(+)
(2) 当前运算符优先级 ≤ 栈顶运算符优先级
• 将栈中所有优先级≥当前运算符的运算符依次弹出并拼接到输出字符串
• 最后将当前运算符压入栈中
- 最终处理
• 遍历完所有字符后，将栈中剩余运算符依次弹出拼接到输出字符串尾部
二、优先级判定方法
private int priority(char c) {
return switch (c) {
case '+', '-' -> 1;
case '*', '/' -> 2;
default -> throw new IllegalArgumentException("不合法运算符: " + c);
};
}三、核心实现代码（Java）
public String infixToPostfix(String infix) {
LinkedList<Character> stack = new LinkedList<>();
StringBuilder postfix = new StringBuilder(infix.length());
for (int i = 0; i < infix.length(); i++) {
char c = infix.charAt(i);
switch (c) {
case '+', '-', '*', '/' -> {
// 处理运算符优先级
if (stack.isEmpty()) {
stack.push(c);
} else {
while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
postfix.append(stack.pop());
}
stack.push(c);
}
}
default -> postfix.append(c); // 非运算符直接拼接
}
}
// 处理剩余运算符
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix.toString();
}四、测试用例验证
- 输入：A+B → 输出：AB+
- 输入：A+B-C → 输出：AB+C-
- 输入：A+BC → 输出：ABC+
- 输入：AB-C → 输出：ABC-
五、补充说明
- 运算符扩展：可通过修改priority()方法支持更多运算符
- 括号处理：当前版本未包含括号处理逻辑，需要扩展算法实现
- 错误处理：遇到非法运算符时会抛出IllegalArgumentException
注：文档已修正原始录音中的文字错误（如"入斩"→"入栈"，"D"→"低"，"战"→"栈"等），并优化了代码示例的语法准确性。
基础数据结构-072-栈-e03-中缀表达式转后缀3
中缀表达式转后缀表达式处理括号规则详解
一、核心规则说明
- 运算符优先级设定（新增括号处理）
• 乘除运算符：优先级2
• 加减运算符：优先级1
• 左括号'('：优先级0（特殊处理）
• 右括号')'：不参与优先级比较，仅作为终止符
- 括号处理原则
左括号处理：
• 无条件直接入栈
• 优先级设为最低（0）以保证后续运算符正常入栈
右括号处理：
- 触发连续出栈操作，直到弹出左括号
- 左括号出栈后丢弃（不加入结果表达式）
- 右括号本身不入栈
二、算法流程示例解析
示例1：(A + B) * C
'('入栈
A输出
'+'优先级 > 栈顶'(', 入栈
B输出
遇到')'触发操作：
• 弹出'+'并输出 → AB+• 弹出'('并丢弃
'*'入栈
C输出
弹出''并输出 → AB+C
最终后缀表达式：AB+C*
示例2：(A + B _ C - D) _ E
处理流程：
括号内部处理：
• BC优先计算 → BC• A+BC* → ABC*+
• -D → ABC*+D-
弹出栈中剩余''与E组合 → ABC+D-E*
最终后缀表达式：ABC*+D-E*
示例3：A * (B + C)
特殊处理流程：
'*'先入栈
括号处理：
• B+C → BC+栈中''后处理 → ABC+
最终后缀表达式：ABC+*
三、关键代码实现
def infix_to_postfix(expression):
precedence = {'*':2, '/':2, '+':1, '-':1, '(':0}
stack = []
output = []
for token in expression:
if token.isalnum():
output.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # 弹出左括号不输出
else:
while stack and precedence[token] <= precedence.get(stack[-1],0):
output.append(stack.pop())
stack.append(token)
while stack:
output.append(stack.pop())
return ' '.join(output)四、测试用例验证
| 中缀表达式 | 后缀表达式 | 测试结果 |
|---|---|---|
| (A + B) _ C | A B + C _ | ✔️ |
| (A + B _ C - D) _ E | A B C _ + D - E _ | ✔️ |
| A _ (B + C) | A B C + _ | ✔️ |
五、注意事项
- 表达式合法性假设：要求输入表达式括号必须成对匹配
- 错误处理：实际应用中需添加括号匹配检测
- 优先级扩展：可根据需求扩展其他运算符（如^幂运算）
- 空栈检测：在弹出操作前必须检查栈是否为空
六、核心算法流程图解
[新字符]
↓
是操作数？ → 直接输出
↓
是'('？ → 入栈
↓
是')'？ → 弹出至'('
↓
运算符处理：
while(栈非空且栈顶优先级≥当前):
弹出栈顶元素
当前运算符入栈最终弹出所有剩余运算符完成转换
七、复杂度分析
• 时间复杂度：O(n) 线性复杂度
• 空间复杂度：O(n) 栈空间最坏情况存储全部运算符
该算法通过单次扫描输入表达式，配合栈的临时存储，高效完成中缀到后缀表达式的转换，特别适用于需要处理复杂运算符优先级和嵌套括号的场景。
基础数据结构-072-栈-e04-双栈模拟队列
双栈模拟队列实现详解
问题需求
用两个栈模拟一个队列，实现队列的基本操作：
- 队列尾部添加元素（
push） - 队列头部移除元素（
pop） - 获取队列头部元素（
peek） - 判断队列是否为空（
empty）
数据结构特性
• 队列：先进先出（FIFO），支持队尾添加、队头移除
• 栈：后进先出（LIFO），仅支持栈顶操作
解题思路
核心设计
栈分工
• S2 栈：模拟队列尾部操作（存储逆向数据）• S1 栈：模拟队列头部操作（存储正向数据）
入队操作
• 直接将元素压入 S2 栈顶出队操作
• 当 S1 为空时，将 S2 所有元素依次弹出并压入 S1• 弹出 S1 栈顶元素
代码实现
class MyQueue {
private Stack s1;
private Stack s2;
public MyQueue() {
s1 = new Stack(100);
s2 = new Stack(100);
}
// 入队操作
public void push(int x) {
s2.push(x);
}
// 出队操作
public int pop() {
if (s1.isEmpty()) {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
return s1.pop();
}
// 查看队首
public int peek() {
if (s1.isEmpty()) {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
return s1.peek();
}
// 判空
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
// 栈实现（简版）
class Stack {
private int[] data;
private int top = -1;
public Stack(int capacity) {
data = new int[capacity];
}
public void push(int x) {
data[++top] = x;
}
public int pop() {
return data[top--];
}
public int peek() {
return data[top];
}
public boolean isEmpty() {
return top == -1;
}
}关键操作说明
元素转移条件
仅在 S1 为空时转移 S2 元素，保证：
• 时间复杂度均摊为 O(1)• 保持队列的 FIFO 特性
时间复杂度分析
•push(): O(1)•
pop(): 最差 O(n)，均摊 O(1)•
peek(): 同 pop空间复杂度
O(n)，n 为操作次数上限
测试验证
public static void main(String[] args) {
MyQueue queue = new MyQueue();
queue.push(1); // 队列: [1]
queue.push(2); // 队列: [1,2]
System.out.println(queue.peek()); // 输出 1
System.out.println(queue.pop()); // 输出 1，队列: [2]
System.out.println(queue.empty()); // 输出 false
}实际应用
• 主要用作数据结构基础训练
• 理解栈和队列的本质区别
• 面试常见基础题型
注意事项
- 栈容量需根据操作次数上限设定
- 元素转移操作是性能关键点
- 确保栈实现的基础方法正确性
通过这种实现方式，我们成功用两个 LIFO 的栈结构模拟出了 FIFO 的队列特性。这种设计模式在需要限制数据结构使用场景的编程问题中具有典型意义。
基础数据结构-072-栈-e05-单队列模拟栈
用单个队列模拟栈的实现详解
题目描述
• 需求：使用两个队列实现栈的功能，进阶要求仅使用单个队列模拟栈。
• 目标：通过该问题深入理解队列（先进先出）和栈（后进先出）的特性差异。
解题思路
核心思想
• 队列模拟栈的关键：确保新入栈的元素始终位于队列头部，使后续的pop和top操作符合栈的后进先出（LIFO）特性。
• 实现方法：
Push操作：
◦ 将新元素加入队列尾部。◦ 将新元素之前的所有元素依次从队列头部移除，并重新加入队列尾部。这使得新元素移动到队列头部（即栈顶）。
Pop/Top操作：直接操作队列头部元素，无需额外处理。
操作示例
• Push(A)：队列元素为[A]，栈顶为A。
• Push(B)：
• 队列变为[A, B]。
• 将A移到尾部，队列变为[B, A]，栈顶为B。
• Push(C)：
• 队列变为[B, A, C]。
• 依次移动B和A到尾部，队列变为[C, B, A]，栈顶为C。
代码实现
队列定义（辅助类）
class ArrayQueue {
private int[] array;
private int head;
private int tail;
public ArrayQueue(int capacity) {
array = new int[capacity];
head = 0;
tail = 0;
}
public void offer(int value) {
array[tail++] = value;
}
public int poll() {
return array[head++];
}
public int peek() {
return array[head];
}
public boolean isEmpty() {
return head == tail;
}
public int size() {
return tail - head;
}
}栈实现（单队列）
class MyStack {
private ArrayQueue queue;
private int size; // 维护元素数量
public MyStack() {
queue = new ArrayQueue(100); // 题目保证最多100次操作
size = 0;
}
// 入栈操作
public void push(int x) {
queue.offer(x);
size++;
// 将新元素前的所有元素移到队列尾部
for (int i = 0; i < size - 1; i++) {
queue.offer(queue.poll());
}
}
// 出栈操作
public int pop() {
size--;
return queue.poll();
}
// 获取栈顶元素
public int top() {
return queue.peek();
}
// 判断栈是否为空
public boolean empty() {
return queue.isEmpty();
}
}关键点说明
- Push操作的时间复杂度：O(n)，每次需要移动n-1个元素。
- Pop/Top时间复杂度：O(1)，直接操作队列头部。
- 空间复杂度：O(n)，队列存储所有元素。
- 题目约束：题目保证调用
pop和top时栈非空，因此无需空值检查。
测试验证
• 测试用例：
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // 返回2
stack.pop(); // 返回2
stack.empty(); // 返回false• LeetCode提交：代码通过所有测试用例。
通过这种实现方式，我们仅用单个队列便成功模拟了栈的行为，深入体现了队列与栈的结构差异及操作逻辑的转换。
基础数据结构-073-双端队列-链表实现-1
双端队列（Deque）课程文档
一、数据结构对比
- 队列（Queue）
• 定义：
• 只能在队列尾（Rear）进行添加操作
• 只能在队列头（Front）进行删除操作
• 特点：
• FIFO（First In First Out）先进先出
• 先进入队列的元素会先被移除
- 栈（Stack）
• 定义：
• 只能在同一端（栈顶）进行添加和删除操作
• 特点：
• LIFO（Last In First Out）后进先出
• 最后压入栈的元素最先弹出
- 双端队列（Deque）
• 定义：
• 允许在队列头和队列尾进行添加/删除操作
• 队列中间不可直接操作
• 特点：
• 同时支持FIFO和LIFO操作
• 相比普通队列操作更灵活
二、双端队列接口定义
接口名称Deque（Double Ended Queue 的缩写）
核心方法
| 方法名 | 功能描述 |
|---|---|
offerFirst(E e) | 在队列头部添加元素 |
offerLast(E e) | 在队列尾部添加元素 |
pollFirst() | 删除并返回队列头部元素 |
pollLast() | 删除并返回队列尾部元素 |
peekFirst() | 获取队列头部元素（不删除） |
peekLast() | 获取队列尾部元素（不删除） |
isEmpty() | 判断队列是否为空 |
isFull() | 判断队列是否已满 |
三、双向环形链表实现
实现选择原因
双向链表：
• 每个节点包含prev和next指针• 支持高效的头尾双向操作
环形结构：
• 使用单一哨兵节点（Sentinel）同时表示头尾• 节省存储空间，简化边界条件处理
节点类定义
class Node<E> {
Node<E> prev;
Node<E> next;
E value;
Node(E value) {
this.value = value;
}
}双端队列类结构
public class LinkedListDeque<E> implements Deque<E> {
private final int capacity;
private int size;
private final Node<E> sentinel;
public LinkedListDeque(int capacity) {
this.capacity = capacity;
this.sentinel = new Node<>(null);
// 初始化环形结构
sentinel.prev = sentinel;
sentinel.next = sentinel;
}
// 方法实现...
}迭代器实现
@Override
public Iterator<E> iterator() {
return new Iterator<>() {
Node<E> p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public E next() {
E value = p.value;
p = p.next;
return value;
}
};
}四、关键实现逻辑
哨兵节点（Sentinel）初始化
• prev和next指针均指向自身
• 作为虚拟头尾节点，避免空指针异常
操作时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 头部/尾部插入 | O(1) |
| 头部/尾部删除 | O(1) |
| 获取头尾元素 | O(1) |
五、扩展说明
其他队列类型（课程提及）
优先级队列（Priority Queue）
延迟队列（Delay Queue）
并发队列：
• 非阻塞队列（ConcurrentLinkedQueue）• 阻塞队列（BlockingQueue）
六、术语修正记录
| 原始表述 | 修正后 | 说明 |
|---|---|---|
| 站 | 栈 | 数据结构名称修正 |
| 异端 | 一端 | 语义修正 |
| praise指针 | prev指针 | 指针命名规范修正 |
| poor fast | pollFirst | 方法名修正 |
| peg first | peekFirst | 方法名修正 |
（文档整理完毕）
基础数据结构-074-双端队列-链表实现-2
基于双向链表实现双端队列的详细文档
一、数据结构核心设计
- 双向链表结构：使用带有哨兵节点（sentinel）的双向链表
- 容量属性：capacity 表示队列最大容量
- 计数属性：size 实时记录当前元素数量
二、核心方法实现
- 判空与判满方法
def is_empty(self):
"""判断队列是否为空"""
return self.size == 0
def is_full(self):
"""判断队列是否已满"""
return self.size == self.capacity- 元素添加方法
(1) offer_first() - 头部添加
def offer_first(self, value):
if self.is_full():
return False
# 确定前后节点指针
A = self.sentinel
B = self.sentinel.next
# 创建新节点并维护指针
new_node = Node(prev=A, next=B, value=value)
A.next = new_node
B.prev = new_node
self.size += 1
return True(2) offer_last() - 尾部添加
def offer_last(self, value):
if self.is_full():
return False
# 确定前后节点指针
A = self.sentinel.prev
B = self.sentinel
# 创建新节点并维护指针
new_node = Node(prev=A, next=B, value=value)
A.next = new_node
B.prev = new_node
self.size += 1
return True- 元素移除方法
(1) poll_first() - 头部移除
def poll_first(self):
if self.is_empty():
return None
# 定位相关节点
A = self.sentinel
removed = A.next
B = removed.next
# 调整指针关系
A.next = B
B.prev = A
self.size -= 1
return removed.value(2) poll_last() - 尾部移除
def poll_last(self):
if self.is_empty():
return None
# 定位相关节点
B = self.sentinel
removed = B.prev
A = removed.prev
# 调整指针关系
A.next = B
B.prev = A
self.size -= 1
return removed.value- 元素查看方法
(1) peek_first()
def peek_first(self):
return self.sentinel.next.value if not self.is_empty() else None(2) peek_last()
def peek_last(self):
return self.sentinel.prev.value if not self.is_empty() else None三、测试用例验证
测试用例1：头部添加+尾部添加
dq = LinkedListDeque(capacity=5)
dq.offer_first(1) # 队列：1
dq.offer_first(2) # 队列：2←1
dq.offer_first(3) # 队列：3←2←1
dq.offer_last(4) # 队列：3←2←1→4
dq.offer_last(5) # 队列：3←2←1→4→5
assert dq.offer_last(6) is False # 已满测试用例2：尾部添加+混合操作
dq = LinkedListDeque(capacity=5)
dq.offer_last(1) # 队列：1
dq.offer_last(2) # 队列：1→2
dq.offer_last(3) # 队列：1→2→3
dq.offer_last(4) # 队列：1→2→3→4
dq.offer_last(5) # 队列：1→2→3→4→5
assert dq.poll_first() == 1 # 队列：2→3→4→5
assert dq.poll_first() == 2 # 队列：3→4→5
assert dq.poll_last() == 5 # 队列：3→4
assert dq.poll_last() == 4 # 队列：3
assert dq.poll_last() == 3 # 队列空
assert dq.peek_first() is None
assert dq.is_empty()四、实现要点说明
哨兵节点机制：
• 初始化时创建自环哨兵节点• 所有操作均通过哨兵节点进行指针操作
• 保证空队列时的指针安全性
指针维护原则：
• 添加操作需同时维护前后节点的指针• 移除操作需将被移除节点的前后节点直接连接
• 每个操作保证四个指针的正确性（新节点的prev/next，相邻节点的next/prev）
时间复杂度：
• 所有操作均为 O(1) 时间复杂度• 无需遍历链表，直接通过指针操作实现
内存管理：
• 移除节点后主动断开引用关系• 避免内存泄漏和野指针问题
五、典型应用场景
- 滑动窗口算法实现
- 浏览器前进后退功能
- 任务调度系统中的优先级队列
- 需要双向操作的缓存系统
基础数据结构-075-双端队列-数组实现-1
以下是整理后的课程文档，已纠正转录中的错别字和技术术语错误，保持技术描述的准确性：
基于循环数组实现双端队列
实现思路
数据结构
• 使用循环数组作为存储结构
• 维护两个指针：
• head：头指针（初始指向索引0）
• tail：尾指针（初始指向索引0）
• 数组长度为capacity + 1（为区分空满状态需浪费一个位置）
核心操作
添加元素
• offerLast()（尾部添加）：在
tail指向位置插入元素tail指针通过increment方法后移
• offerFirst()（头部添加）：
head指针通过decrement方法前移在新
head位置插入元素删除元素
• pollFirst()（头部删除）：取出
head指向元素head指针通过increment方法后移
• pollLast()（尾部删除）：
tail指针通过decrement方法前移- 取出新
tail位置元素
状态判断
• 空队列：head == tail
• 满队列：(tail + 1) % array.length == head
索引维护方法
increment(i)（后移指针）
private int increment(int i) {
if (++i >= array.length) {
i = 0;
}
return i;
}decrement(i)（前移指针）
private int decrement(int i) {
if (--i < 0) {
i = array.length - 1;
}
return i;
}代码结构
类定义
public class ArrayDeque<E> {
private E[] array;
private int head;
private int tail;
public ArrayDeque(int capacity) {
array = (E[]) new Object[capacity + 1]; // 多分配一个空间
head = 0;
tail = 0;
}
// 其他方法实现...
}关键方法模板
// 添加方法
public boolean offerFirst(E e) {
// 实现逻辑
}
public boolean offerLast(E e) {
// 实现逻辑
}
// 删除方法
public E pollFirst() {
// 实现逻辑
}
public E pollLast() {
// 实现逻辑
}
// 判空方法
public boolean isEmpty() {
return head == tail;
}实现细节
循环利用：通过索引计算方法实现指针循环移动，避免数组越界
空间利用：
• 实际可用容量 = 数组长度 - 1• 通过浪费一个位置区分空满状态
时间复杂度：所有操作均为O(1)
指针行为差异：
• offerLast/pollFirst 先操作元素后移动指针• offerFirst/pollLast 先移动指针后操作元素
示例流程
假设数组长度4（索引0-3）：
| 操作 | 结果 | head | tail |
|---|---|---|---|
| 初始状态 | [] | 0 | 0 |
| offerLast(A) | [A] | 0 | 1 |
| offerLast(B) | [A, B] | 0 | 2 |
| offerFirst(C) | [C, A, B] | 3 | 2 |
| pollFirst() | 返回C → [A,B] | 0 | 2 |
| pollLast() | 返回B → [A] | 0 | 1 |
本实现参考JDK中ArrayDeque的设计思路，通过指针移动和状态判断实现高效的双端队列操作。
基础数据结构-076-双端队列-数组实现-2
以下是课程录音整理后的详细技术文档（已修正错别字并优化表述）：
环形队列核心方法实现原理
一、isEmpty 方法
判断条件
当 head 和 tail 指针指向相同索引位置时，队列为空
def isEmpty() -> bool:
return self.head == self.tail二、isFull 方法
判断条件分析
队列满分为两种情况（设数组长度为 capacity）：
tail > head 时：
• 有效元素数 = tail - head• 队列满条件：tail - head == capacity - 1
tail < head 时：
• 有效元素数 = (capacity - head) + tail• 队列满条件：head - tail == 1
代码实现
def isFull() -> bool:
if self.tail > self.head:
return (self.tail - self.head) == self.capacity - 1
elif self.tail < self.head:
return (self.head - self.tail) == 1
return False # 指针相等时空队列三、指针移动辅助方法
增量计算（处理循环）
def increment(index: int) -> int:
return (index + 1) % self.capacity减量计算（处理循环）
def decrement(index: int) -> int:
return (index - 1 + self.capacity) % self.capacity四、核心操作方法
- offerFirst (头部入队)
def offerFirst(e: Any) -> bool:
if self.isFull():
return False
self.head = self.decrement(self.head)
self.array[self.head] = e
return True- offerLast (尾部入队)
def offerLast(e: Any) -> bool:
if self.isFull():
return False
self.array[self.tail] = e
self.tail = self.increment(self.tail)
return True- pollFirst (头部出队)
def pollFirst() -> Any:
if self.isEmpty():
return None
val = self.array[self.head]
self.head = self.increment(self.head)
return val- pollLast (尾部出队)
def pollLast() -> Any:
if self.isEmpty():
return None
self.tail = self.decrement(self.tail)
return self.array[self.tail]五、实现要点说明
环形数组特性：通过取模运算实现指针循环，保证索引合法性
空间浪费策略：约定数组最后一个位置不存储元素，用于区分空/满状态
指针移动顺序：
• 头部入队：先移动指针再存储元素• 尾部入队：先存储元素再移动指针
• 出队操作与对应入队操作保持对称逻辑
时间复杂度：所有操作均为 O(1) 时间复杂度
六、示例验证
场景1：顺序插入（capacity=4）
- offerLast(A) → head=0, tail=1
- offerLast(B) → head=0, tail=2
- offerLast(C) → head=0, tail=3
- isFull() → 3-0=3 == 4-1 → True
场景2：头部插入（capacity=4）
- offerFirst(A) → head=3, tail=0
- offerFirst(B) → head=2, tail=0
- offerFirst(C) → head=1, tail=0
- isFull() → 1-0=1 → True
本实现方案保证了环形队列的高效操作，正确处理了边界条件下的指针移动和状态判断。
基础数据结构-077-双端队列-数组实现-3
基于数组实现的双端队列内存管理详解
一、问题背景
在数组实现的队列、栈、双端队列等数据结构中，当删除元素时必须考虑内存释放问题。对于存储引用类型的数据结构，需特别处理防止内存泄漏，而基本数据类型无需额外操作。
二、内存释放分析
- 基本数据类型
• 示例：int类型数组[100, 200]
• 删除操作：移动头指针head++即可
• 内存特性：元素占固定内存空间，无需清零处理
• 原理：无论是否清零，内存占用保持不变（int固定4字节）
- 引用类型
• 示例：对象引用数组[R1->E1, R2->E2]
• 删除隐患：仅移动指针会导致数组继续持有引用
• 解决方案：
- 获取被删元素后，将数组对应位置置为
null - 解除数组对对象的引用，帮助GC回收
• 核心代码：
// pollFirst 方法示例
E element = (E) array[head];
array[head] = null; // 解除引用
head = increment(head);
return element;三、代码实现要点
关键方法改进
方法 改进内容 pollFirst将原 head位置置空后移动指针pollLast将原 tail-1位置置空后移动指针remove循环删除时逐个置空元素 Peek方法实现
// 查看队首元素
public E peekFirst() {
if (isEmpty()) return null;
return (E) array[head];
}
// 查看队尾元素
public E peekLast() {
if (isEmpty()) return null;
return (E) array[dec(tail)]; // tail需减1处理
}- 迭代器实现
public Iterator<E> iterator() {
return new Iterator<>() {
int p = head;
final int end = tail;
public boolean hasNext() {
return p != end;
}
public E next() {
E element = (E) array[p];
p = increment(p);
return element;
}
};
}四、测试用例验证
- 基础功能测试
// 测试用例1：容量3的队列
Deque<Integer> deque = new ArrayDeque<>(3);
assert deque.offerFirst(1); // 头部插入1
assert deque.offerFirst(2); // 头部插入2 → [2,1]
assert deque.offerLast(3); // 尾部插入3 → [2,1,3]
assert !deque.offerLast(4); // 队列已满
assert deque.pollFirst() == 2; // 头部移除- 混合操作测试
// 测试用例2：容量7的队列
Deque<Integer> deque = new ArrayDeque<>(7);
deque.offerLast(1); // [1]
deque.offerLast(2); // [1,2]
deque.offerLast(3); // [1,2,3]
deque.offerFirst(4); // [4,1,2,3]
deque.offerFirst(5); // [5,4,1,2,3]
deque.offerFirst(6); // [6,5,4,1,2,3]
deque.offerFirst(7); // [7,6,5,4,1,2,3]
assert deque.pollFirst() == 7; // 头部移除
assert deque.pollLast() == 3; // 尾部移除- 边界条件测试
// 测试用例3：空队列操作
Deque<Integer> deque = new ArrayDeque<>(2);
assert deque.pollFirst() == null; // 空队列返回null
assert deque.peekLast() == null; // 空队列返回null五、核心机制说明
- 索引计算
•increment()方法处理索引递增循环
• dec()方法处理索引递减循环
// 索引递增逻辑
private int increment(int i) {
return (++i >= array.length) ? 0 : i;
}
// 索引递减逻辑
private int dec(int i) {
return (--i < 0) ? array.length-1 : i;
}- 内存管理
• 删除操作时间复杂度：O(1)
• 内存释放策略：立即解除引用（非延迟回收）
• GC友好性：避免僵尸引用，加快内存回收
六、设计总结
| 特性 | 说明 |
|---|---|
| 时间复杂度 | 增删查操作均为O(1) |
| 空间复杂度 | O(n) 固定容量 |
| 适用场景 | 确定容量规模的引用类型存储 |
| 优势 | 内存可控，无动态扩容开销 |
| 局限性 | 容量固定，需预判数据规模 |
通过合理的内存管理机制，该实现既保证了基础操作的高效性，又避免了常见的内存泄漏问题，是资源受限场景下的理想选择。
基础数据结构-078-双端队列-e01-二叉树Z字层序遍历
以下是经过整理的课程文档，已修正错别字并优化表述：
二叉树Z字形层序遍历专题课程
一、问题定义
1.1 层序遍历基础
• 常规层序遍历：按层级从左到右逐层访问节点
• 示例二叉树结构：
1
/ \
2 3
/ \ / \
4 5 6 7• 常规层序遍历结果：[[1], [2,3], [4,5,6,7]]
1.2 Z字形层序遍历要求
• 访问方向交替变化：
• 奇数层（第1、3层等）：从左向右
• 偶数层（第2、4层等）：从右向左
• 示例遍历结果：[[1], [3,2], [4,5,6,7]]
二、实现方案分析
2.1 常规层序遍历实现
核心组件：
- 队列数据结构（先进先出）
- 分层处理逻辑（通过记录当前层节点数）
基础实现代码框架：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}2.2 Z字形遍历改进思路
关键改进点：
方向控制：使用布尔标志位记录当前层奇偶性
数据结构优化：将ArrayList改为LinkedList（双端队列）
插入方式控制：
• 奇数层：尾部插入（offerLast）• 偶数层：头部插入（offerFirst）
三、具体实现方案
3.1 代码改进步骤
- 修改层级存储结构：
List<Deque<Integer>> result = new ArrayList<>(); // 外层结果集不变
Deque<Integer> level = new LinkedList<>(); // 内层使用双端队列- 添加方向控制逻辑：
boolean isOddLevel = true; // 初始为奇数层
while (!queue.isEmpty()) {
// ... 层级处理循环
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (isOddLevel) {
level.offerLast(node.val); // 奇数层尾部添加
} else {
level.offerFirst(node.val); // 偶数层头部添加
}
// 子节点入队列逻辑保持不变
}
result.add(new ArrayList<>(level)); // 转换回List接口类型
level.clear();
isOddLevel = !isOddLevel; // 切换层级方向
}3.2 完整实现代码
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean isOddLevel = true;
while (!queue.isEmpty()) {
int levelSize = queue.size();
Deque<Integer> level = new LinkedList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (isOddLevel) {
level.offerLast(node.val);
} else {
level.offerFirst(node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(new ArrayList<>(level));
isOddLevel = !isOddLevel;
}
return result;
}四、复杂度分析
时间复杂度：O(n)
• 每个节点访问且仅访问一次空间复杂度：O(n)
• 队列存储最宽层节点数• 结果集存储所有节点值
五、扩展讨论
5.1 其他实现方式
- 反向收集法：正常收集后反转偶数层列表
- 栈实现方案：使用双栈交替处理（空间复杂度较高）
5.2 边界条件处理
• 空树处理：直接返回空列表
• 单节点树：返回[[root.val]]
• 完全二叉树场景优化
六、示例验证
测试案例：
/*
1
/ \
2 3
/ \ / \
4 5 6 7
*/程序输出：
[[1], [3, 2], [4, 5, 6, 7]]各层处理过程：
- 第一层（奇数层）：[1] → 正序
- 第二层（偶数层）：先2后3 → 反序存储为[3,2]
- 第三层（奇数层）：按4,5,6,7顺序存储
注：实际实现中节点添加顺序与子节点入队列顺序保持一致，方向控制仅影响结果存储顺序。
基础数据结构-079-优先级队列-无序数组实现
数据结构课程笔记：优先级队列（基于无序数组实现）
一、优先级队列 vs 普通队列
| 特性 | 普通队列 | 优先级队列 |
|---|---|---|
| 出入队规则 | FIFO（先进先出） | 按优先级出队（优先级高者优先） |
| 时间复杂度 | 入队O(1)，出队O(1) | 入队O(1)，出队O(n) |
| 元素排列 | 按插入顺序排列 | 元素无序排列 |
| 典型应用场景 | 任务调度、消息队列 | 急诊分诊、任务优先级调度 |
二、核心实现原理
- 数据结构设计
• 使用普通数组存储元素
• 维护size变量记录元素数量
• 元素需实现Priority接口（需提供priority()方法）
public class PriorityQueue<E extends Priority> implements Queue<E> {
private Priority[] array;
private int size;
public PriorityQueue(int capacity) {
array = new Priority[capacity];
}
}- 关键操作实现
（1）入队操作（offer）
@Override
public boolean offer(E e) {
if (isFull()) return false;
array[size++] = e; // 直接添加到数组尾部
return true;
}（2）出队操作（poll）
@Override
public E poll() {
if (isEmpty()) return null;
int max = selectMax(); // 查找最大优先级索引
E removed = (E) array[max];
remove(max); // 删除该元素
return removed;
}
// 辅助方法：查找最大优先级元素索引
private int selectMax() {
int max = 0;
for (int i = 1; i < size; i++) {
if (array[i].priority() > array[max].priority()) {
max = i;
}
}
return max;
}（3）查看队首（peek）
@Override
public E peek() {
if (isEmpty()) return null;
return (E) array[selectMax()];
}- 元素删除逻辑
private void remove(int index) {
if (index < size - 1) {
// 将被删元素后的元素前移
System.arraycopy(array, index + 1, array, index, size - index - 1);
}
size--;
}三、时间复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| offer() | O(1) | 直接插入数组尾部 |
| poll() | O(n) | 需要遍历查找最大优先级元素 |
| peek() | O(n) | 同poll()，但不执行删除操作 |
四、测试用例验证
// 测试元素类
class Task implements Priority {
private String name;
private int priority;
// constructor & getters
@Override
public int priority() {
return priority;
}
}
// 测试流程
public static void main(String[] args) {
PriorityQueue<Task> queue = new PriorityQueue<>(5);
queue.offer(new Task("Task1", 4));
queue.offer(new Task("Task2", 2));
queue.offer(new Task("Task3", 1));
queue.offer(new Task("Task4", 5));
// 出队顺序应为：Task4(5) → Task1(4) → Task2(2) → Task3(1)
}五、实现特点总结
优势：
• 实现简单直观
• 入队操作效率极高
• 适合频繁插入、较少删除的场景
局限：
• 出队操作效率随队列规模线性下降
• 不适合元素频繁变化的场景
• 内存利用率取决于初始容量设置
六、关键概念修正
- "IFIFO" → 正确应为 "FIFO"（First In First Out）
- "poor" → 正确方法名为 "poll"
- "初对" → 正确应为 "出队"
- "selectmax" → 规范命名应为 "selectMax"（驼峰式命名法）
基础数据结构-080-优先级队列-有序数组实现
以下是整理后的课程文档（已纠正错别字并优化技术表达）：
优先级队列实现专题（二）——基于有序数组的实现
一、实现原理
1.1 数据结构特性
• 使用有序数组存储队列元素
• 数组按元素优先级升序排列（优先级越高越靠近尾部）
• 索引排列示例：[1(优先级), 4, 5, 8, 10]
1.2 核心操作特性
| 操作 | 时间复杂度 | 实现原理 |
|---|---|---|
| 入队(offer) | O(n) | 类似插入排序，寻找合适位置 |
| 出队(poll) | O(1) | 直接删除尾部元素 |
| 查看(peek) | O(1) | 直接访问尾部元素 |
二、方法实现详解
2.1 peek() 方法
public PriorityElement peek() {
if (isEmpty()) return null;
return (PriorityElement) array[size - 1];
}实现逻辑：
- 直接访问数组最后一个元素（size-1位置）
- 空队列返回null
2.2 poll() 方法
public PriorityElement poll() {
if (isEmpty()) return null;
size--;
PriorityElement removed = (PriorityElement) array[size];
array[size] = null; // 帮助垃圾回收
return removed;
}实现逻辑：
- 记录尾部元素（size-1位置）
- 将size减1实现逻辑删除
- 显式置空原位置引用
2.3 offer() 方法
public boolean offer(PriorityElement e) {
if (isFull()) return false;
insert(e);
size++;
return true;
}
private void insert(PriorityElement e) {
int i = size - 1;
while (i >= 0 && e.priority() < ((PriorityElement) array[i]).priority()) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = e;
}实现逻辑：
从数组末端(size-1)开始向前遍历
当遇到优先级更高的元素时：
• 将当前元素后移一位• 指针i前移
找到第一个优先级更低的元素时：
• 在i+1位置插入新元素
三、时间复杂度分析
入队操作：O(n)
• 最坏情况需要移动所有元素（如插入最小优先级元素）出队/查看操作：O(1)
• 直接操作数组尾部
四、实现对比（与无序数组实现）
| 实现方式 | 入队时间复杂度 | 出队时间复杂度 | 适用场景 |
|---|---|---|---|
| 无序数组 | O(1) | O(n) | 写多读少 |
| 有序数组 | O(n) | O(1) | 读多写少 |
五、测试用例验证
测试代码结构：
public static void main(String[] args) {
PriorityQueue2 queue = new PriorityQueue2(5);
// 添加不同优先级的元素
queue.offer(new Task(3, "task1"));
queue.offer(new Task(5, "task2"));
// 验证出队顺序
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}
}预期结果：
- 优先级5的元素最先出队
- 元素按优先级降序出队
六、优化方向
- 空间优化：动态扩容机制
- 插入优化：二分查找定位（减少比较次数）
- 类型安全：泛型实现
七、后续内容预告
第三种实现方式将采用堆（Heap）数据结构，结合：
• O(log n) 的入队/出队时间复杂度
• 空间效率优化
• 更适合动态数据场景