一、先遣了解和回顧

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}
}