一、先遣了解和回顾

1、预览快速对比表格

2、Java中的包装类

【1】装箱/装包：把基本数据类型变为包装类型。Java 中的基本数据类型（如 int、double 等）是原始类型，而包装类型（如 Integer、Double 等）是类。

例如：

                Integer i = Integer.valueOf(i);    //显示装箱，通过包装类的静态方法 valueOf() 转换

                Integer n = 2025;     //自动装箱 ，编译器自动调用 Integer.valueOf() 方法

【2】拆箱/拆包：把包装类型变为基本数据类型。

例如：

                int  a = n.intValue();    //显示拆箱，通过包装类的实例方法 intValue() 转换

                 int b = n;   //自动拆箱，编译器自动调用 n.intValue() 方法

补充说明：

（1）性能问题：自动装箱和拆箱虽然方便，但可能会带来性能开销。因为每次装箱都会创建一个新的对象，而每次拆箱都需要调用方法。如果在性能敏感的代码中，建议尽量避免频繁的装箱和拆箱操作。

（2）空指针异常：在使用自动拆箱时，如果包装类型变量为 null，调用拆箱方法会抛出 NullPointerException。例如：

Integer m = null;
int c = m; // 抛出 NullPointerException，因为 m 为 null

（3）缓存机制：Integer.valueOf() 方法有一个缓存机制。对于 -128 到 127 之间的整数，valueOf() 方法会直接返回缓存的对象，而不是每次创建新对象。例如：

Integer x = 100; // 自动装箱，使用缓存对象
Integer y = 100; // 自动装箱，使用相同的缓存对象
System.out.println(x == y); // 输出 true

但超出这个范围时，每次调用 valueOf() 都会创建新的对象：

Integer z = 2025;
Integer w = 2025;
System.out.println(z == w); // 输出 false

二、数据结构代码说明及其对比

1、数组（Array）

C/C++

C/C++ 中数组是一块连续的内存空间，声明方式如int arr[5];，可通过arr[i]访问元素

//原生数组
int arr[5] = {1, 2, 3, 4, 5}; // 静态数组
int size = sizeof(arr) / sizeof(arr[0]); // 获取数组大小

补充：在C++11起，可以使用标准库容器 std::array来读取数组大小，必须要使用<array>头文件。（所有 STL 容器（如 std::list, std::map, std::string 等）均支持 .size()：）

#include <array>
std::array<int, 5> arr = {1, 2, 3, 4, 5};
size_t length = arr.size(); // size_t是C++中的无符号整型

Java

Java 中数组是对象，可用new关键字创建，如int[] arr = new int[5];，通过arr[i]访问元素。Java 数组有length属性获取长度，如arr.length

int[] arr = {1, 2, 3, 4, 5}; // 静态数组
int size = arr.length; // 获取数组大小

2、动态数组（Dynamic Array）

C++

C++中使用std::vector来实现动态数组。使用<vector>头文件。

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> vec = { 1,2,3,4,5 };vec.push_back(6);  //1. 添加元素，在末尾cout << "添加元素后：";for (int n : vec) cout << n << " ";// 值传递（创建副本）遍历cout << endl;vec.insert(vec.begin() + 2, 712);  //2. 指定位置添加元素cout << "指定位置添加元素后：";for (auto it = vec.begin();it != vec.end();++it)  cout << *it << " ";//使用迭代器遍历cout << endl;vec.erase(vec.begin() + 3);  //3. 删除元素，索引为3的元素被删除cout << "删除第四个元素后：";for (int i = 0;i < vec.size();++i) cout << vec[i] << " ";cout << endl;cout << "获取长度：" << vec.size() << endl;  //4. 获取长度cout << "获取索引为3的元素：" << vec[3] << endl;  //5. 获取指定元素return 0;
}

Java

Java中使用ArrayList来实现动态数组，功能类似。需要导入 java.util.ArrayList

动态数组不能使用.length而是要使用.size()获取长度！！！ .length 是数组的属性​​，.size() 是ArrayList 的方法​​

import java.util.ArrayList;
import java.util.Arrays;public class FirstTest {public static void main(String[] args){ArrayList<Integer> number = new ArrayList<>(Arrays.asList(1,2,3,4,5));number.add(100);//1. 添加元素，会添加到最后System.out.println("添加后："+number);number.add(1,711);//2. 在指定位置添加元素System.out.println("指定添加后："+number);number.remove(1);//3. 删除第二个元素System.out.println("删除后："+number);System.out.println("长度："+number.size());//4. 获取长度System.out.println("索引为1（即第二个）的元素："+number.get(1));//5. 获取指定元素}
}

3、链表（Linked List）

C/C++

链表通过指针连接节点，每个节点包含数据和指向下一节点的指针。

如定义单链表节点struct ListNode { int val; ListNode* next; };，需手动管理内存，通过malloc分配内存，free释放内存。

//C++代码
#include <iostream>
using namespace std;//单向链表节点结构体
struct ListNode {int val;  // 节点存储的数据ListNode* next;  // 指向下一个节点的指针explicit ListNode(int x):val(x),next(nullptr){}//定义了一个只允许显式调用的构造函数，用给定值初始化节点数据，并把 next 置空。
};//在链表头部插入节点
ListNode* addNode(ListNode*& head, int val) {ListNode* newNode = new ListNode(val);  // 创建新节点newNode->next = head;                   // 新节点指向原头节点return newNode;                         // 返回新的头节点
}
//打印链表
void printList(ListNode*& head) {for (ListNode* cur = head;cur;cur = cur->next) {cout << cur->val << " ";}cout << endl;
}int main()
{ListNode* head = nullptr;head = addNode(head, 3);head = addNode(head, 2);head = addNode(head, 1);printList(head);//输出1 2 3return 0;
}

Java

Java 中通过类实现链表，无需手动管理内存，自动回收内存。

可定义class ListNode { int val; ListNode next; }，使用new创建节点对象。

class ListNode {int val;          // 节点中保存的整数值ListNode next;    // 指向下一个节点的引用，若为空则表示链表结束// 构造方法：创建节点时只需给定 val，next 默认为 nullListNode(int val) {this.val = val;}
}public class LinkedList {/*** 在链表头部插入新节点* @param head 当前链表头节点* @param val  待插入的新值* @return 插入后的新链表头节点*/public static ListNode addNode(ListNode head, int val) {ListNode newNode = new ListNode(val); // 创建新节点newNode.next = head;                  // 新节点指向原头节点return newNode;                       // 新节点成为新头，返回}/*** 按顺序打印链表中的所有值* @param head 链表头节点*/public static void printList(ListNode head) {ListNode cur = head;while (cur != null) {                 // 遍历直到链表尾System.out.print(cur.val + " ");  // 打印当前节点值cur = cur.next;                   // 移动到下一个节点}System.out.println();}public static void main(String[] args) {ListNode head = null;     // 初始链表为空head = addNode(head, 3);  // 头部插入 3head = addNode(head, 2);  // 头部插入 2head = addNode(head, 1);  // 头部插入 1printList(head);          // 输出：1 2 3}
}

4、栈（Stack）

C/C++

可通过数组或链表实现栈，手动管理元素进出。

如用数组实现时，需定义栈顶指针，通过操作指针来实现压栈和弹栈操作。

//C++代码
#include <iostream>
#include <limits>
using namespace std;const int MAX_SIZE = 5;//栈的最大容量class ArrayStack {
private:int stackArray[MAX_SIZE];//存储栈元素的数组int topPointer;  //栈顶指针（索引位置）
public:ArrayStack() {topPointer = -1;//初始化栈顶指针为-1}//压栈操作void push(int value) {if (topPointer >= MAX_SIZE - 1) { //检查栈是否已满cout << "Stack Overflow! Cannot push " << value << endl;return;}stackArray[++topPointer] = value;//栈顶指针先加1，再将元素存入cout << "Pushed:" << value << endl;}//弹栈操作int pop() {if (isEmpty()) {cout << "Stack Underflow!" << endl;return INT_MIN; //返回错误码}int value = stackArray[topPointer--]; // 先取出栈顶元素，指针再减1cout << "Popped:" << value << endl;return value;}//获取栈顶元素（不弹出）int peek() {if (isEmpty()) {cout << "Stack is empty!" << endl;}return stackArray[topPointer];}//检查栈是否为空bool isEmpty() {return topPointer == -1;}//显示栈状态void display() {if (isEmpty()) {cout << "Stack:[](Empty)" << endl;return;}cout << "Stack:[";for (int i = 0;i <= topPointer;++i) {cout << stackArray[i] << " ";}cout << "]" << endl;}
};int main() {ArrayStack myStack;myStack.push(2025);//压入2025myStack.push(7);//压入7myStack.display();cout << "Top element:" << myStack.peek() << endl;//查看栈顶myStack.pop();myStack.push(13);myStack.push(14);myStack.push(15);myStack.push(16);//栈满myStack.push(17);//溢出错误myStack.display();return 0;
}

Java

Java 有java.util.Stack类，是Vector的子类，提供了push（压栈）、pop（弹栈）等方法。也可使用Deque接口的实现类如LinkedList来模拟栈，addFirst和removeFirst方法可分别实现压栈和弹栈功能。

（1）使用java.util.Stack

（2）使用LinkedList实现Deque接口

import java.util.Stack;
import java.util.LinkedList;
import java.util.Deque;public class StackDemo {public static void main(String[] args) {//方法一：使用java.util.StackSystem.out.println("Using java.util.Stack:");Stack<Integer>jdkStack = new Stack<>();//压栈操作Stack.push()jdkStack.push(2025);jdkStack.push(7);jdkStack.push(14);//弹栈操作Stack.pop()System.out.println("Popped:"+jdkStack.pop());//弹出14//查看栈顶元素，不移除Stack.peek()System.out.println("Top element:"+jdkStack.peek());//显示7//显示当前栈内容System.out.println("Stack contents:"+jdkStack);//方法二：使用LinkedList实现Deque接口System.out.println("Using LinkedList as Deque:");Deque<Integer>dequeStack = new LinkedList<>();//模拟压栈操作（添加到头部）addFirst()dequeStack.addFirst(2025);dequeStack.addFirst(10);dequeStack.addFirst(1);//模拟弹栈操作（移除头部）removeFirst()System.out.println("Popped:"+dequeStack.removeFirst());//弹出1//查看栈顶peekFirst()System.out.println("Top element:"+dequeStack.peekFirst());//显示10//显示当前栈状态System.out.println("DequeStack contents:"+dequeStack);}
}

5、队列（Queue）

C/C++

可以使用数组或链表实现队列结构。数组实现时建议采用循环队列来优化空间利用率，而链表实现则更为直观，只需维护队头和队尾两个指针即可。

（1）数组实现

#include <iostream>
using namespace std;class CircularQueue {
private:int* data;  //动态数组int front;  //队头下标int rear;   //队尾下标（指向即将入队的空位）int capacity; //数组容量int count;//当前元素个数
public://构造函数：申请数组并初始化指针explicit CircularQueue(int cap) :capacity(cap), front(0), rear(0), count(0) {data = new int[capacity];}//析构函数：释放动态数组~CircularQueue() {delete[] data;}//入队，O(1)bool enqueue(int val) {if (count == capacity) {cout << "队列已满，" << val << "无法入队" << endl;return false;}data[rear] = val;  //放入数值rear = (rear + 1) % capacity; //循环后移++count;cout << val << "入队" << endl;return true;}//出队，O(1)bool dequeue(int& out) {if (count == 0) {cout << "队列为空，无法出队" << endl;return false;}out = data[front];front = (front + 1) % capacity;//循环后移--count;return true;}//查看队头，不删除bool peek(int& out)const {if (count == 0) return false;out = data[front];return true;}//当前元素数量int size()const { return count; }};int main() {CircularQueue q(3);q.enqueue(2025);q.enqueue(7);q.enqueue(18);q.enqueue(5);//提示队列已满int val;while (q.size()) {if (q.dequeue(val)) cout << val << "出队" << endl;}q.dequeue(val);return 0;
}

（2）链表实现

//C++代码
#include <iostream>
using namespace std;//链表节点：每个节点保存一个数据与下一个数据的指针
struct Node
{int data;   //存储节点的整数值Node* next; //指向下一个节点的指针Node(int val):data(val),next(nullptr){}//构造函数，接收一个整数参数val，用val初始化data，将next指针置空
};//链式队列，只维护“队头”与“队尾”两个指针即可
class LinkedQueue {
private:Node* front;Node* rear;
public:LinkedQueue():front(nullptr),rear(nullptr){}//初始化front和rear为空指针//入队：尾插法，时间复杂度O(1)void enqueue(int val) {Node* node = new Node(val);//在堆上新建节点if (!rear) {//若rear为空，则队列为空front = rear = node; //空队列时首尾指针都指向新节点}else {rear->next = node; //当前尾结点的next指向新节点rear = node; //更新尾指针，指向新的尾结点}cout << val << "入队" << endl;}//出队：头删法，时间复杂度O(1)bool dequeue(int& out) {  //dequeue函数，通过引用out带出出队值if (!front) {  //如果front为空，说明队列为空cout << "队列已空，无法出队" << endl;return false;}Node* tmp = front;//暂存当前队头节点地址out = tmp->data;  //取出当前队头值，存入outfront = front->next; //头指针后移，指向下一个节点if (!front) rear = nullptr; //若队列变为空，同步尾指针为空delete tmp;return true;}//查看队头但不删除，返回INT_MIN表示空队列int peek() {if (!front) {cout << "队列为空" << endl;return INT_MIN;}return front->data;}
};int main()
{LinkedQueue q;q.enqueue(2025);q.enqueue(7);q.enqueue(16);cout << "队头元素：" << q.peek() << endl; //查看队头元素，不删除int val; //接收 dequeue 弹出的那个队头元素if (q.dequeue(val)) cout << val << "出队" << endl;if (q.dequeue(val)) cout << val << "出队" << endl;if (q.dequeue(val)) cout << val << "出队" << endl;if (q.dequeue(val)) cout << val << "出队" << endl; //此时队已经为空return 0;	
}

Java

Java 有java.util.Queue接口，常用实现类有PriorityQueue和LinkedList。LinkedList实现了Queue接口，提供offer()方法进行入队操作，poll()方法进行出队操作。

（1）使用LinkedList

（先进先出）

import java.util.LinkedList;
import java.util.Queue;//例一：使用LinkedList实现队列（先进先出）
public class QueueDemo1 {public static void main(String[] args) {Queue<String> linkedListQueue = new LinkedList<>();//入队,添加到队尾linkedListQueue.offer("live");linkedListQueue.offer("towards");linkedListQueue.offer("death");System.out.println("LinkedList队列内容："+linkedListQueue);//出队，移除并返回队列头部元素String firstItem = linkedListQueue.poll();System.out.println("出队元素："+firstItem);System.out.println("出队后的队列："+linkedListQueue);//查看队列头部元素，仅查看，不删除String peekItem = linkedListQueue.peek();System.out.println("查看当前队头："+peekItem);}
}

（2）使用PriorityQueue

（按优先级排序，默认为自然序）

默认序：

                数字，按数值升序排列（例如 [1, 2, 3]）。

                字符串，按字典序（Unicode 编码）升序排列（例如 ["apple", "banana", "cherry"]）。

import java.util.PriorityQueue;
import java.util.Queue;//使用PriorityQueue
public class QueueDemo2 {public static void main(String[] args) {Queue<Integer> priorityQueue = new PriorityQueue<>();//乱序入队priorityQueue.offer(2025);priorityQueue.offer(7);priorityQueue.offer(17);System.out.println("PriorityQueue初始队列："+priorityQueue);//按优先级出队（数值由小到大）System.out.println("按优先级出队结果：");while (!priorityQueue.isEmpty()){System.out.print("->"+priorityQueue.poll());}}
}

6、二叉树（Binary Tree）

用前序遍历为例

C/C++

二叉树节点通常定义为struct TreeNode { int val; TreeNode* left; TreeNode* right; };，通过指针连接左右子树，遍历等操作需递归或利用栈等辅助数据结构实现。

#include <iostream>
#include <vector>
using namespace std;struct TreeNode
{int val;  //节点存储的整数值TreeNode* left;  //指向左子节点的指针TreeNode* right; //指向右子节点的指针TreeNode(int x) :val(x), left(nullptr), right(nullptr) {}
};//前序遍历：根->左->右
void preorderTraversal(TreeNode* root, vector<int>& res)
{if (root == nullptr)return;//递归终止条件，当前节点为空res.push_back(root->val);  //访问根节点preorderTraversal(root->left, res); //递归遍历左子树preorderTraversal(root->right, res); //递归遍历右子树
}
int main(){//创建根节点TreeNode* root = new TreeNode(1);//第二层节点root->left = new TreeNode(2);root->right  = new TreeNode(3);//第三层节点root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);vector<int>result; //储存遍历结果的容器preorderTraversal(root, result);//执行前序遍历cout << "前序遍历结果：";for (int val : result) cout << val << " ";//内存释放，自底向上delete root->left->left;delete root->left->right;delete root->left;delete root->right;delete root;return 0;
}

Java

Java中定义二叉树节点类class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } }，遍历方式与C++类似，但无需手动管理内存。

import java.util.ArrayList;
import java.util.List;class TreeNode{int val; //节点存储的整数值TreeNode left;TreeNode right;TreeNode(int val){this.val = val;}//节点构造函数
}public class BinaryTreeTraversal {private static void preorderTraversal(TreeNode root, List<Integer> res){if(root == null) return;//递归终止条件，当前节点为空res.add(root.val); //访问根节点preorderTraversal(root.left, res);  //遍历左子树preorderTraversal(root.right, res); //遍历右子树}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);List<Integer> result = new ArrayList<>(); //存储遍历结果动态数组preorderTraversal(root,result); //执行前序遍历、System.out.println("前序遍历结果：");for(int val:result){System.out.print(val+" ");}//自动回收所有对象}
}

7、堆（Heap/PriorityQueue）

堆是堆是分为大顶堆和小顶堆的完全二叉树。

大顶堆：每个父节点的值大于等于对应的子节点的值

小顶堆：每个父节点的值小于等于对应的子节点的值

C++

std::priority_queue，默认大顶堆

#include <iostream>
#include <queue>
using namespace std;int main() {//默认大顶堆priority_queue<int> maxHeap;maxHeap.push(20);maxHeap.push(7);maxHeap.push(2025);while (!maxHeap.empty()) {cout << maxHeap.top() << " "; //2025 20 7maxHeap.pop();}return 0;
}

Java

java.util.PriorityQueue，默认小顶堆

import java.util.PriorityQueue;public class HeapDemo {public static void main(String[] args) {//默认小顶堆PriorityQueue<Integer> minHeap = new PriorityQueue<>();minHeap.offer(2025);minHeap.offer(7);minHeap.offer(20);while (!minHeap.isEmpty()) {System.out.print(minHeap.poll() + " ");//7 20 2025}}
}

8、排序（Sorting）

C++

<algorithm>里的sort

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;int main()
{vector<int> v = { 2,0,5,7,3 };sort(v.begin(), v.end());  //升序排列for (int n : v) cout << n << " ";//0 2 3 5 7return 0;
}

Java

使用Collection.sort

import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class SortDemo {public static void main(String[] args) {List<Integer> numbers = Arrays.asList(2, 0, 5, 7, 3);Collections.sort(numbers); // 升序排序System.out.println(numbers);//[0, 2, 3, 5, 7]}
}

使用Arrays.sort

import java.util.Arrays;public class SortDemo {public static void main(String[] args) {int[] arr = {2,0,5,7,3};Arrays.sort(arr);  //升序排列for(int n:arr) System.out.print(n+" ");//0 2 3 5 7}
}

9、映射（Map）

键值对（Key-Value Pair）结构，支持快速查找。
键值对本质上就是一个名称（Key）对应一个内容（Value）。名称作为唯一标识，用于快速定位和访问对应的内容。

C++

std::unordered_map（哈希表）/std::map（红黑树）

#include <iostream>
#include <unordered_map>using namespace std;int main() {unordered_map<string, int> score;//哈希表score["Emma"] = 7;score["Ida"] = 25;cout << "Emma:" << score["Emma"] << endl;//Emma:7
}

Java

HashMap（哈希表）/TreeMap（红黑树）

import java.util.HashMap;public class MapDemo {public static void main(String[] args) {HashMap<String,Integer> score = new HashMap<>();score.put("Emma",7);score.put("Ida",25);System.out.println("Emma:"+score.get("Emma"));//Emma:7}
}

10、集合（Set）

只保存唯一元素，支持快速判重。

C++

std::unordered_set（哈希表）/std::set（红黑树）

#include <iostream>
#include <unordered_set>using namespace std;int main() {unordered_set<int> s; //哈希集合s.insert(7);s.insert(25);s.insert(7); //重复的7将会被忽略for (int n : s)cout << n << " "; //7 25return 0;
}

Java

HashSet（哈希表）/TreeSet（红黑树）

import java.util.HashSet;public class SetDemo {public static void main(String[] args) {HashSet<Integer> set = new HashSet<>();set.add(7);set.add(25);set.add(7); //重复的7将会被忽略for(int n:set) System.out.print(n+" "); //7 25}
}