基础数据结构-061-队列-链表实现-2

队列实现文档（链表实现）

一、数据结构设计
• 哨兵节点：用于简化链表边界条件处理

• 指针定义：

• head：始终指向哨兵节点

• tail：指向队列最后一个有效节点

• 新增属性：

class LinkedQueue:
    def __init__(self, capacity=float('inf')):
        self.sentinel = Node(None)  # 哨兵节点
        self.head = self.sentinel
        self.tail = self.sentinel
        self.size = 0
        self.capacity = capacity

二、核心方法实现

1. isEmpty() 方法
   功能：检查队列是否为空
   实现逻辑：

def is_empty(self):
    return self.head == self.tail

2. peek() 方法
   功能：查看队首元素但不移除
   实现逻辑：

def peek(self):
    if self.is_empty():
        return None
    return self.head.next.value

3. poll() 方法
   功能：移除并返回队首元素
   实现逻辑：

def poll(self):
    if self.is_empty():
        return None

    first_node = self.head.next
    return_val = first_node.value

    # 调整指针
    self.head.next = first_node.next

    # 处理移除最后一个节点的情况
    if first_node == self.tail:
        self.tail = self.head

    self.size -= 1
    return return_val

4. offer() 方法（带容量限制）
   功能：添加元素到队尾
   实现逻辑：

def offer(self, value):
    if self.is_full():
        return False

    new_node = Node(value)
    self.tail.next = new_node
    self.tail = new_node
    self.size += 1
    return True

5. isFull() 方法
   功能：检查队列是否已满
   实现逻辑：

def is_full(self):
    return self.size >= self.capacity

三、关键逻辑说明

1. 哨兵节点机制：
   • 初始化时 head 和 tail 都指向哨兵节点

   • 所有操作通过哨兵节点统一处理边界条件

2. 容量控制：
   • 默认容量为无限（float('inf')）

   • 可通过构造函数指定最大容量

   • 每次添加/删除元素时更新 size 计数器

3. 指针调整策略：
   • 删除最后一个节点时，将 tail 重新指向哨兵节点

   • 添加新节点时，始终更新 tail 到新节点

四、复杂度分析

方法	时间复杂度	空间复杂度
isEmpty()	O(1)	O(1)
peek()	O(1)	O(1)
poll()	O(1)	O(1)
offer()	O(1)	O(1)
isFull()	O(1)	O(1)

五、测试用例说明

1. 基础功能测试：
   • 空队列的 isEmpty() 校验

   • 单元素队列的 peek/poll 操作

   • 多元素队列的顺序操作

2. 边界条件测试：
   • 容量满时的 offer 操作

   • 删除最后一个元素后的指针状态

   • 反复添加/删除的稳定性测试

3. 异常处理测试：
   • 空队列执行 poll 操作

   • 满队列执行 offer 操作

   • 初始化不同容量的队列测试

文档已修正原录音中的术语错误（如"tell"修正为"tail"，"shopping节点"修正为"哨兵节点"），确保技术术语准确性。实现方案采用标准的链表队列模式，通过哨兵节点简化边界处理，容量控制机制保证队列的安全性。

基础数据结构-062-队列-环形数组实现-方法1-1

环形数组实现队列详解

一、环形数组基础概念

1. 定义：
   • 环形数组是一种逻辑上首尾相连的固定大小数组

• 物理存储仍为线性结构，通过程序控制索引循环（例如索引4之后回到0）

2. 索引计算规则：
   • 计算公式：新索引 = (当前索引 + 步数) % 数组长度

• 示例：

• 数组长度5，当前索引3，前进2步：(3+2)%5=0

• 数组长度5，当前索引4，前进1步：(4+1)%5=0

二、与普通数组实现队列对比

操作类型	普通数组实现	环形数组实现
入队（尾部添加元素）	O(1)	O(1)
出队（头部移除元素）	O(n)	O(1)

普通数组劣势分析：
• 移除头部元素时需要整体前移所有元素

• 必须固定以索引0为队列头，导致数据迁移

三、环形队列核心实现机制

1. 指针管理：
   • 头指针（Head）：指向队列第一个有效元素

• 尾指针（Tail）：指向下一个可插入位置

2. 初始状态：
   • 头尾指针均指向索引0

• 队列为空状态：head == tail

3. 关键操作逻辑：
   • 入队操作：

4. 在tail位置插入元素

5. 更新tail：tail = (tail + 1) % size
   • 出队操作：

6. 从head位置取出元素

7. 更新head：head = (head + 1) % size

四、队列状态判断

1. 判空条件：
   • head == tail

• 示例：初始化时头尾指针均为0

2. 判满条件：
   • (tail + 1) % size == head

• 需浪费一个存储空间用于状态区分

• 示例：数组长度5时最大存储4个元素

五、环形队列优势分析

1. 性能优势：
   • 避免数据迁移操作

• 充分利用CPU缓存（局部性原理）

2. 应用场景：
   • 有界队列实现

• 环形缓冲区（Ring Buffer）

• 实时系统和高性能计算场景

六、实现示意图

索引：0 [A] <- head
      1 [B]
      2 [C]
      3 [D] <- tail
      4 [空]

说明：
• 头指针指向当前队首元素

• 尾指针指向下一个插入位置

• 当(3+1)%5=4不等于head(0)时，可继续插入

七、注意事项

1. 容量计算：
   • 实际可用容量 = 数组长度 - 1

• 需在初始化时预先确定最大容量

2. 并发控制：
   • 多线程环境下需要同步机制

• 推荐使用原子操作或锁保护指针修改

3. 动态扩容：
   • 固定大小特性不适用于需要动态扩容的场景

• 扩容需要创建新数组并迁移数据

八、扩展知识

1. 环形缓冲区应用：
   • 网络数据包缓冲

• 音频/视频流处理

• 实时数据采集系统

2. 优化变种：
   • 双缓冲区（Double Buffer）结构

• 分块环形缓冲区

• 带优先级的环形队列

[注] 本文档已修正原始录音中的术语错误（如"初对操作"→"出队操作"），并优化了技术表述的准确性。

基础数据结构-063-队列-环形数组实现-方法1-2

环形数组队列实现文档

一、类定义与成员变量

public class ArrayQueue1<E> implements Queue<E> {
    @SuppressWarnings("unchecked")
    private final E[] array;    // 泛型数组存储元素
    private int head = 0;       // 头指针（初始值0）
    private int tail = 0;       // 尾指针（初始值0）
}

二、构造函数

public ArrayQueue1(int capacity) {
    array = (E[]) new Object[capacity + 1];  // 实际数组大小 = 容量 + 1
}

• 预留一个空位用于区分队列满/空状态

• 示例：期望容量4时创建大小为5的数组

三、核心方法实现

1. 判空与判满

@Override
public boolean isEmpty() {
    return head == tail;
}

@Override
public boolean isFull() {
    return (tail + 1) % array.length == head;
}

• 判空：头尾指针重合

• 判满：尾指针+1取模后等于头指针

2. 入队操作（offer）

@Override
public boolean offer(E value) {
    if (isFull()) return false;
    array[tail] = value;
    tail = (tail + 1) % array.length;
    return true;
}

• 尾指针处插入元素

• 更新尾指针：(当前值+1) % 数组长度

3. 出队操作（poll）

@Override
public E poll() {
    if (isEmpty()) return null;
    E value = array[head];
    head = (head + 1) % array.length;
    return value;
}

• 头指针处取出元素

• 更新头指针：(当前值+1) % 数组长度

4. 查看队首（peek）

@Override
public E peek() {
    return isEmpty() ? null : array[head];
}

5. 迭代器实现

@Override
public Iterator<E> iterator() {
    return new Iterator<>() {
        int p = head;

        @Override
        public boolean hasNext() {
            return p != tail;
        }

        @Override
        public E next() {
            E value = array[p];
            p = (p + 1) % array.length;
            return value;
        }
    };
}

• 遍历条件：p指针不等于尾指针

• 索引更新：(当前值+1) % 数组长度

四、实现要点说明

1. 环形索引处理：所有指针移动都需要进行(current + 1) % array.length运算

2. 空位策略：通过牺牲一个数组位置简化满队列判断

3. 时间复杂度：
   • 所有操作 O(1)

   • 空间复杂度 O(n)

4. 线程安全：非线程安全实现，需外部同步控制

五、测试结果
• 通过所有标准队列操作测试用例（添加、移除、查看元素等）

• 验证了边界条件：

• 空队列操作返回null

• 满队列拒绝添加

• 正确处理环形索引回绕

完整实现已通过JUnit测试，测试用例基于链表队列测试用例改造，验证了环形数组实现的正确性。

基础数据结构-064-队列-环形数组实现-方法2

循环队列空满判断方法对比 - 使用size变量实现

一、原头尾指针实现方案

1. 核心机制
   • 使用头指针(head)和尾指针(tail)判断队列状态

• 数组容量需设置为capacity+1

• 通过(head+1)%n == tail判断队列满

2. 主要缺点
   • 必须预留一个空位给尾指针

• 实际存储空间减少一个单位

• 头尾指针重合时需区分空/满状态

二、改进方案（引入size变量）

1. 类结构修改

class ArrayQueue2 {
    private final int[] array;
    private int head = 0;
    private int tail = 0;
    private int size = 0;  // 新增size变量

    public ArrayQueue2(int capacity) {
        array = new int[capacity];  // 去除+1
    }
}

2. 关键方法实现
   判空逻辑

public boolean isEmpty() {
    return size == 0;
}

判满逻辑

public boolean isFull() {
    return size == array.length;
}

入队操作

public boolean offer(int value) {
    if (isFull()) return false;
    array[tail] = value;
    tail = (tail + 1) % array.length;
    size++;  // 维护size值
    return true;
}

出队操作

public int poll() {
    if (isEmpty()) return -1;
    int value = array[head];
    head = (head + 1) % array.length;
    size--;  // 维护size值
    return value;
}

3. 迭代器实现调整

public Iterator<Integer> iterator() {
    return new Iterator<>() {
        int p = head;
        int count = 0;  // 新增遍历计数器

        @Override
        public boolean hasNext() {
            return count < size;  // 基于元素数量判断
        }

        @Override
        public Integer next() {
            int value = array[p];
            p = (p + 1) % array.length;
            count++;  // 更新遍历进度
            return value;
        }
    };
}

三、方案对比

特性	头尾指针方案	size变量方案
存储空间利用率	少1个单位	完全利用
状态判断复杂度	O(1)	O(1)
额外变量数量	2（head/tail）	3（head/tail/size）
指针移动逻辑	需要处理空位	直接操作
并发环境适用性	较优	需同步size

四、测试验证
• 修改测试用例（TestArrayQ2）后全部通过

• 验证场景包括：

• 空队列状态判断

• 满队列状态判断

• 循环存储边界处理

• 迭代器遍历准确性

五、总结建议

1. 优先选择size方案：
   • 当需要最大化存储空间利用率时

   • 在单线程环境下

   • 需要更直观的状态判断时

2. 头尾指针方案适用场景：
   • 内存敏感环境（减少变量数量）

   • 需要减少状态维护成本时

   • 并发环境需结合锁机制使用时

两种方案时间复杂度均为O(1)，具体选择应根据实际应用场景的需求平衡空间利用率和代码复杂度。

基础数据结构-065-队列-环形数组实现-方法3-1

以下是整理后的课程文档（已修正错别字并优化表述）：

队列判空/满的三种实现方案

背景介绍
前两种方法存在的不足：

1. 方法一：仅使用 head 和 tail 指针判空/满
   • 指针存储计算后的索引值，每次操作需进行取模运算

   • 存在索引越界问题需要特殊处理

2. 方法二：引入辅助变量 size
   • 通过维护元素数量判断队列状态

   • 需要额外空间存储状态变量

方法三：动态计算索引法（优化方案）

核心思想
• 让 head/tail 持续自增，不存储实际索引

• 随用随算：使用时通过取模动态计算真实索引

• 解决前两种方法的存储冗余问题

实现细节
初始状态

int head = 0;  // 持续递增的头指针
int tail = 0;  // 持续递增的尾指针
Object[] array = new Object[capacity];

元素入列（offer）

public boolean offer(E value) {
    if(isFull()) return false;
    array[tail % array.length] = value;  // 动态计算存储位置
    tail++;  // 尾指针持续递增
    return true;
}

元素出列（poll）

public E poll() {
    if(isEmpty()) return null;
    E value = array[head % array.length];  // 动态计算读取位置
    head++;  // 头指针持续递增
    return value;
}

判空条件

public boolean isEmpty() {
    return head == tail;  // 头尾指针重合时为空
}

判满条件

public boolean isFull() {
    return tail - head == array.length;  // 元素间距等于容量时为满
}

迭代器实现

public Iterator<E> iterator() {
    return new Iterator<>() {
        int p = head;  // 从当前头指针开始遍历

        public boolean hasNext() {
            return p != tail;  // 遍历至尾指针结束
        }

        public E next() {
            E value = array[p % array.length];  // 动态计算索引
            p++;
            return value;
        }
    };
}

关键优势

1. 空间优化：无需预留空位或维护size变量
2. 计算优化：指针仅做自增运算，索引按需计算
3. 逻辑清晰：空/满判断条件直观且无冗余计算

索引计算原理
• 实际索引 = 指针值 % 数组长度

• 示例：数组长度3时

指针值	计算过程	实际索引
0	0%3=0	0
1	1%3=1	1
2	2%3=2	2
3	3%3=0	0

操作示例

1. 入列A（tail=0→1）
2. 入列B（tail=1→2）
3. 入列C（tail=2→3）
4. 入列D（tail=3→4，实际存储索引为3%3=0）

总结对比

方法	优点	缺点
基础指针法	实现简单	需处理索引越界问题
Size辅助法	判断逻辑简单	需要额外存储空间
动态索引法	无冗余存储，计算高效	需理解指针递增原理

基础数据结构-066-队列-环形数组实现-方法3-2

以下是课程内容的整理文档：

---

队列实现中的整数溢出问题及解决方案

问题背景
在实现环形队列时，发现当head/tail指针持续自增超过Java整型最大值（2,147,483,647）时，会导致索引计算错误。测试用例中当tail初始值为2,147,483,640时，连续插入10个元素会导致指针溢出。

问题复现
测试用例配置：
• 队列容量：10

• 初始tail值：2,147,483,640

• 操作：连续执行10次offer()插入元素

错误现象：
• 前8次插入成功（tail=2,147,483,640~2,147,483,647）

• 第9次插入时tail自增至2,147,483,648（超出整型范围变为-2,147,483,648）

• 索引计算：tail % capacity 得到负数索引导致ArrayIndexOutOfBoundsException

原因分析
Java整型溢出特性：

int max = Integer.MAX_VALUE; // 2,147,483,647
max + 1 = Integer.MIN_VALUE; // -2,147,483,648

解决方案
步骤：

1. 将head/tail指针转换为无符号长整型
2. 使用长整型进行索引计算
3. 最终结果转换回整型索引

代码实现：

// 插入元素方法修改
public boolean offer(int value) {
    if(isFull()) return false;
    // 将tail转为无符号长整型计算索引
    int index = (int) (Integer.toUnsignedLong(tail) % elements.length);
    elements[index] = value;
    tail++;
    return true;
}

// 删除元素方法修改
public int poll() {
    if(isEmpty()) throw new RuntimeException();
    // 将head转为无符号长整型计算索引
    int index = (int) (Integer.toUnsignedLong(head) % elements.length);
    int value = elements[index];
    head++;
    return value;
}

优化原理

1. Integer.toUnsignedLong()方法将int值转换为无符号long值：

   int tail = -2147483648;
   long unsignedTail = Integer.toUnsignedLong(tail); // 转换为2,147,483,648

2. 长整型计算保证索引始终为正数
3. 最终转换为int索引满足数组访问要求

测试验证
修改后测试用例执行结果：
• 成功插入10个元素（0-9）

• 索引计算正确（0-9循环）

• 无数组越界异常

潜在优化方向

1. 使用长整型存储head/tail指针（需权衡内存开销）
2. 添加指针重置机制（当head/tail超过阈值时重置归零）

---

文档已修正所有技术术语（如"tell"→"tail"、"ETEGER"→"Integer"），统一代码格式，优化了技术表述的准确性。如需进一步补充细节请告知。

基础数据结构-067-队列-环形数组实现-方法3-3

二进制求模运算的优化规律及实现方法

一、二进制求模运算规律

1. 核心发现
   当除数为2的N次方时，二进制形式的求模运算存在以下规律：
   • 商 = 被除数的二进制前（总位数-N位）

• 余数 = 被除数的二进制后N位

2. 示例验证
   例1：100 ÷ 8（8=2³）

十进制计算：100 ÷ 8 = 12 余4
二进制形式：
被除数 100  -> 01100100
前5位(1100) -> 12（商）
后3位(100)  -> 4（余数）

例2：111 ÷ 8

十进制计算：111 ÷ 8 = 13 余7
二进制形式：
被除数 111  -> 01101111
前5位(1101) -> 13（商）
后3位(111)  -> 7（余数）

例3：任意数 ÷ 16（2⁴）

二进制形式：
被除数 xxxx xxxx
前（总位数-4位） -> 商
后4位           -> 余数

二、位运算实现原理

1. 位运算规律
   对于除数M=2ⁿ：

余数 = 被除数 & (M-1)

原理说明：
• M-1的二进制形式是N个连续的1（如8-1=7=0111）

• 按位与操作会保留被除数的最后N位

2. 性能优势
   相比传统求模运算：
3. 免去除法运算，性能提升约5-8倍
4. 自动屏蔽符号位影响，避免负数处理问题

三、代码实现应用

1. 环形队列场景
   假设数组长度capacity=2ⁿ，指针计算：

// 原始方法
int index = tail % capacity;

// 优化方法
int index = tail & (capacity - 1);

2. 完整代码示例

// 入队操作
public boolean enqueue(E element) {
    if ((tail - head) == capacity) return false;

    elements[tail & (capacity - 1)] = element;
    tail++;
    return true;
}

// 出队操作
public E dequeue() {
    if (head == tail) return null;

    E element = elements[head & (capacity - 1)];
    head++;
    return element;
}

四、边界情况处理

1. 指针越界问题
   当指针超过Integer.MAX_VALUE时：
   • 按位与操作自动取后N位，无需特殊处理

• 示例：tail=2147483647+1时：

二进制形式：10000000 00000000 00000000 00000000
按位与操作：& (capacity-1)  // 例如capacity=8时&7
结果自动归零，实现环形队列效果

2. 元素数量计算
   tail - head的可靠性：
   • 最大差值为capacity（2ⁿ），远小于Integer.MAX_VALUE

• 32位int类型可安全表示2³¹范围内的数值差

五、实现要求

1. 必须保证数组长度为2的幂次
2. 初始化时需验证容量：

if ((capacity & (capacity - 1)) != 0) {
    throw new IllegalArgumentException("容量必须是2的幂次");
}

六、性能对比

操作类型	指令周期数	备注
传统求模运算	20-30	涉及除法运算
位运算实现	3-5	单次按位与操作

此优化方法广泛应用于：
• Java HashMap实现

• Disruptor环形缓冲区

• Netty内存池管理

• Linux内核循环队列

通过这种位运算优化，可以在保持算法正确性的同时显著提升程序性能，特别是在高并发、高频访问的场景下效果尤为明显。

基础数据结构-068-队列-环形数组实现-方法3-4

课程文档：确保数组容量为2的N次方的两种策略及实现

一、核心背景
在队列实现中，当使用位运算替代取模运算时，数组长度（capacity）必须满足2的N次方。若用户传入的capacity不满足此条件，需采取以下两种策略处理：

二、策略一：参数校验及异常抛出

1. 判断逻辑
   核心公式：capacity & (capacity-1) == 0

原理分析：
• 2的N次方数二进制形式为100...0（如8=1000₂）

• 该数减一后得到011...1（如7=0111₂）

• 二者按位与结果为0时，说明是2的N次方

2. 代码实现

public CircularQueue(int capacity) {
    if ((capacity & (capacity - 1)) != 0) {
        throw new IllegalArgumentException("Capacity must be a power of two");
    }
    this.array = new Object[capacity];
}

三、策略二：自动转换至最近2的N次方

方法1：基于对数运算的转换

1. 实现步骤

2. 数学原理：
   • 计算log₂(capacity)并向上取整

   • 目标值 = 2^(向上取整结果)

3. Java实现：

public static int convertToPowerOfTwo(int capacity) {
    if (capacity < 1) return 1;
    int c = capacity - 1; // 处理原始值已是2的N次方的情况
    int n = (int)(Math.log(c) / Math.log(2)) + 1;
    return 1 << n; // 等价于2^n
}

2. 示例验证

   输入值	处理过程	输出值
   30	log₂(29)=4.85 → n=5	32
   32	log₂(31)=4.95 → n=5	32

方法2：位运算优化方案

1. 实现原理
   通过位扩散将最高位的1复制到所有低位，最后+1得到2的N次方：

2. 原始值-1确保自身为2的N次方时保持原值

3. 逐步右移并进行按位或操作

4. 最终+1得到结果

5. 代码实现

public static int convertToPowerOfTwoBitwise(int capacity) {
    if (capacity < 1) return 1;
    int c = capacity - 1;
    c |= c >> 1;
    c |= c >> 2;
    c |= c >> 4;
    c |= c >> 8;
    c |= c >> 16;
    return c + 1;
}

3. 位运算过程演示（以30为例）

原始值: 30 (0001 1110₂)
c = 29: 0001 1101
c |= c>>1: 0001 1101 | 0000 1110 = 0001 1111
c |= c>>2: 0001 1111 | 0000 0111 = 0001 1111
...后续移位无变化
最终c=31 → 31+1=32

四、策略对比

策略	优点	缺点
抛异常	严格校验参数合法性	需调用方处理异常
自动转换	保证程序健壮性	可能产生非预期容量调整
对数运算法	数学逻辑清晰	涉及浮点运算精度问题
位运算法	性能高效，无精度损失	算法理解成本较高

五、工程实践建议

1. 防御性编程：建议采用自动转换策略，确保程序健壮性
2. 容量限制：添加最大容量阈值（如1<<30）防止溢出
3. 日志记录：建议记录原始capacity和转换后的值
4. 参数校验：需处理capacity<=0的特殊情况

本文档已纠正原始录音中的术语错误（如"安慰语"→"按位与"），优化了技术表述的准确性，并补充了完整的实现示例和验证过程。

基础数据结构-069-队列-e01-二叉树层序遍历1

二叉树层序遍历课程文档

---

一、问题描述
层序遍历（Level Order Traversal）是指按二叉树层级从上到下、每层从左到右依次访问所有节点的过程。例如对于如下二叉树：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

层序遍历结果为：1 → 2 → 3 → 4 → 5 → 6 → 7。

---

二、二叉树定义

1. 二叉树特性
   • 每个节点最多有两个子节点（左孩子、右孩子）。

   • 子节点可以为空，或只有一个子节点。

2. 节点类的代码表示

   class TreeNode {
       int val;          // 节点值
       TreeNode left;    // 左孩子
       TreeNode right;   // 右孩子
   
       // 构造函数
       TreeNode(int val) {
           this.val = val;
       }
   
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

---

三、解题思路
核心思想：利用队列实现层序遍历

1. 初始化：将根节点加入队列。

2. 循环处理队列：
   • 从队列头部取出节点，访问其值。

   • 若该节点有左孩子，将左孩子加入队列。

   • 若该节点有右孩子，将右孩子加入队列。

3. 终止条件：队列为空时，遍历完成。

过程示例：

步骤	队列状态	处理节点	访问顺序
1	[1]	1	1
2	[2, 3]	2	1 → 2
3	[3, 4, 5]	3	1 → 2 → 3
4	[4, 5, 6, 7]	4	1 → 2 → 3 → 4
5	[5, 6, 7]	5	... → 5
6	[6, 7]	6	... → 6
7	[7]	7	... → 7

---

四、代码实现

import java.util.LinkedList;
import java.util.Queue;

public class LevelOrderTraversal {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        // 构建示例二叉树
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(6), new TreeNode(7)));

        // 层序遍历
        levelOrder(root);
    }

    public static void levelOrder(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 根节点入队

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); // 从队列头部取出节点
            System.out.print(node.val + " "); // 访问节点值

            // 左孩子入队
            if (node.left != null) {
                queue.offer(node.left);
            }

            // 右孩子入队
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
}

输出结果：

1 2 3 4 5 6 7

---

五、关键点说明

1. 队列选择：使用链表实现的队列（LinkedList），因其无容量限制，适合处理未知节点数的二叉树。
2. 时间复杂度：O(n)，每个节点仅访问一次。
3. 空间复杂度：O(n)，最坏情况下队列存储所有叶子节点（满二叉树时约 n/2 个节点）。

---

六、扩展思考
• 如何记录每层的节点数（如输出 [[1], [2,3], [4,5,6,7]]）？

• 如何实现反向层序遍历（从下到上、每层从右到左）？

基础数据结构-069-队列-e01-二叉树层序遍历2

二叉树层序遍历分层输出实现详解

一、需求分析

1. 原始需求：实现二叉树层序遍历单行输出（所有节点值输出到同一行）
2. 改进需求：实现分层输出效果，每层节点单独成行
3. 力扣题目要求：返回嵌套列表结构，外层列表包含各层节点值的子列表

二、实现原理

1. 队列辅助层序遍历：
   • 使用队列数据结构存储待处理节点

   • 初始将根节点加入队列

2. 分层控制核心逻辑：
   • currentLevelSize变量记录当前层节点数

   • nextLevelSize变量记录下一层节点数

   • 通过双层循环实现分层控制：

   ◦ 外层循环控制层数

   ◦ 内层循环处理当前层所有节点

三、实现步骤
步骤1：基础层序遍历

// 伪代码示例
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    System.out.print(node.val + " ");
    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
}

步骤2：分层输出控制

// 伪代码示例
int currentLevelSize = 1;
while (currentLevelSize > 0) {
    int nextLevelSize = 0;
    // 处理当前层所有节点
    for (int i = 0; i < currentLevelSize; i++) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        // 统计下层节点数
        if (node.left != null) nextLevelSize++;
        if (node.right != null) nextLevelSize++;
    }
    System.out.println(); // 换行标志
    currentLevelSize = nextLevelSize;
}

步骤3：力扣标准答案实现

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);
    int currentLevelSize = 1;

    while (currentLevelSize > 0) {
        List<Integer> level = new ArrayList<>();
        int nextLevelSize = 0;

        for (int i = 0; i < currentLevelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null) {
                queue.offer(node.left);
                nextLevelSize++;
            }
            if (node.right != null) {
                queue.offer(node.right);
                nextLevelSize++;
            }
        }

        result.add(level);
        currentLevelSize = nextLevelSize;
    }

    return result;
}

四、关键点解析

1. 变量命名优化：
   • 原录音中的"C1"改为currentLevelSize

   • "C2"改为nextLevelSize

2. 边界条件处理：
   • 根节点为空时直接返回空列表

   • 使用队列前进行非空判断

3. 层次控制原理：
   • 当前层节点全部出队后，用统计的下一层节点数更新currentLevelSize

   • 每层处理完成后将level列表加入result

4. 时间复杂度：
   • 时间复杂度：O(n)

   • 空间复杂度：O(n)

五、测试用例示例

/*
        1
       / \
      2   3
     / \ / \
    4  5 6  7
*/
// 预期输出：
// [[1], [2,3], [4,5,6,7]]

六、常见问题解决

1. 单节点树处理：
   • 保证能正确返回包含单个元素的列表

2. 非完全二叉树处理：
   • 自动适应缺失子节点的情况

3. 大数据量测试：
   • 验证算法的时间复杂度有效性

七、算法扩展

1. 自底向上层序遍历：最终反转result列表
2. Z字形层序遍历：根据层级判断元素添加顺序
3. 获取层最大值：在level列表收集阶段记录最大值

注：本文档已修正原录音中的术语错误（如"PRINLINE"修正为"println"，"C1/C2"修正为规范的变量名），并优化了代码结构和注释说明。

基础数据结构-070-栈-链表实现

数据结构-栈详解

一、栈的定义
栈（Stack）是一种线性数据结构，具有以下特性：

1. 仅允许在栈顶进行添加（push）和删除（pop）操作
2. 遵循后进先出（LIFO）原则
3. 类比现实中的一摞书，只能在顶部取放

二、线性结构对比

数据结构	操作限制
数组/链表	任意位置操作
队列	尾部添加，头部删除（FIFO）
栈	仅栈顶操作（LIFO）

三、栈接口定义

interface Stack<E> {
    boolean push(E value);  // 压栈
    E pop();                 // 弹栈
    E peek();                // 查看栈顶元素
    boolean isEmpty();       // 判空
    boolean isFull();        // 判满
}

四、链表实现（带哨兵节点）

1. 节点结构

class Node<E> {
    E value;
    Node<E> next;

    Node(E value, Node<E> next) {
        this.value = value;
        this.next = next;
    }
}

2. 实现细节
   属性说明：
   • capacity：栈容量限制

• size：当前元素数量

• head：哨兵节点（始终指向虚拟头节点）

核心方法实现：

class LinkedListStack<E> implements Stack<E> {
    private final int capacity;
    private int size = 0;
    private final Node<E> head = new Node<>(null, null);

    // 压栈操作
    public boolean push(E value) {
        if (isFull()) return false;
        head.next = new Node<>(value, head.next);
        size++;
        return true;
    }

    // 弹栈操作
    public E pop() {
        if (isEmpty()) return null;
        Node<E> first = head.next;
        head.next = first.next;
        size--;
        return first.value;
    }

    // 查看栈顶元素
    public E peek() {
        return isEmpty() ? null : head.next.value;
    }

    // 辅助方法
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == capacity; }
}

五、测试用例
测试1：基础操作

// 创建容量为3的栈
Stack<Integer> stack = new LinkedListStack<>(3);

stack.push(1);  // true
stack.push(2);  // true
stack.push(3);  // true
stack.push(4);  // false（栈满）

// 遍历输出顺序应为3->2->1

测试2：边界条件

Stack<Integer> stack = new LinkedListStack<>(3);
stack.push(1);
stack.push(2);
stack.push(3);

stack.pop();  // 3
stack.pop();  // 2
stack.pop();  // 1
stack.pop();  // null（栈空）

六、实现要点

1. 时间复杂度：
   • push/pop/peek：O(1)

   • 空间复杂度：O(n)

2. 哨兵节点优势：
   • 简化边界条件处理

   • 统一空栈和非空栈的操作逻辑

3. 容量管理：
   • 通过size属性动态追踪元素数量

   • 严格限制操作不超过容量上限

七、应用场景

1. 函数调用栈
2. 括号匹配验证
3. 表达式求值（逆波兰式）
4. 浏览器前进/后退功能
5. 撤销（Undo）操作实现