Js 數據結構全面講解

一、數組

1、定義：數組是一種數據結構，用於存儲有序的元素集合。

2、操作：

//創建一個空數組
let arr = [];

//添加元素
arr.push(1);
arr.push(2);

//獲取元素
console.log(arr[0]); //1

//獲取數組長度
console.log(arr.length); //2

//刪除元素
arr.splice(0, 1); //從下標0開始刪除1個元素

//遍曆數組
for(let i = 0; i < arr.length; i++){
    console.log(arr[i]);
}

3、應用：

使用數組存儲多個元素，實現數據的批量操作，如購物車中存儲多個商品，網頁中存儲多個評論等。

二、棧

1、定義：棧是一種特殊的數據結構，只能在數組的末尾添加或刪除元素。

2、操作：

//創建一個棧
let stack = [];

//添加元素
stack.push(1);
stack.push(2);

//刪除元素
stack.pop();

//獲取棧頂元素
console.log(stack[stack.length - 1]);

//判斷棧是否為空
console.log(stack.length === 0);

3、應用：

在計算機程序中，棧常用於配合遞歸實現函數調用、括弧匹配等操作。

三、隊列

1、定義：隊列是一種特殊的數據結構，只能在數組的末尾添加元素，在數組的開頭刪除元素。

2、操作：

//創建一個隊列
let queue = [];

//添加元素
queue.push(1);
queue.push(2);

//刪除元素
queue.shift();

//獲取隊列頭部元素
console.log(queue[0]);

//判斷隊列是否為空
console.log(queue.length === 0);

3、應用：

隊列常用於實現廣度優先搜索演算法，並且在計算機中還有很多其他的應用場景，如操作系統中的任務隊列、印表機中的列印隊列等。

四、鏈表

1、定義：鏈表是一種數據結構，由節點組成，每個節點保存數據和指向下一個節點的指針。

2、操作：

//定義一個節點
class Node {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

//創建一個鏈表
let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

//遍歷鏈表
let cur = head;
while(cur){
    console.log(cur.val);
    cur = cur.next;
}

//在鏈表中插入節點
let newNode = new Node(4);
newNode.next = head.next;
head.next = newNode;

//在鏈表中刪除節點
head.next = head.next.next;

3、應用：

鏈表常用於實現LRU緩存、哈希表中的拉鏈法等。

五、樹

1、定義：樹是一種數據結構，由節點和邊組成，每個節點保存數據，並指向零或多個子節點。

2、操作：

//定義一個節點
class Node {
    constructor(val, children = []) {
        this.val = val;
        this.children = children;
    }
}

//創建一個樹
let root = new Node(1);
root.children = [new Node(2), new Node(3)];

//遍歷樹-深度優先搜索
function DFS(root) {
    console.log(root.val);
    for(let child of root.children){
        DFS(child);
    }
}
DFS(root);

//遍歷樹-廣度優先搜索
function BFS(root) {
    let queue = [root];
    while(queue.length){
        let node = queue.shift();
        console.log(node.val);
        for(let child of node.children){
            queue.push(child);
        }
    }
}
BFS(root);

3、應用：

樹的應用廣泛，如在頁面中渲染組件、文件系統中的目錄結構、計算機網路中的路由表等。

六、圖

1、定義：圖是一種數據結構，由點和邊組成，每個點可以與其他點直接相連。

2、操作：

//定義一個點
class Node {
    constructor(val, neighbors = []) {
        this.val = val;
        this.neighbors = neighbors;
    }
}

//創建一個圖
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(4);
node1.neighbors = [node2, node4];
node2.neighbors = [node1, node3];
node3.neighbors = [node2, node4];
node4.neighbors = [node1, node3];

//遍歷圖-深度優先搜索
let visited = new Set();
function DFS(node) {
    visited.add(node);
    console.log(node.val);
    for(let neighbor of node.neighbors){
        if(!visited.has(neighbor)){
            DFS(neighbor);
        }
    }
}
DFS(node1);

//遍歷圖-廣度優先搜索
function BFS(node) {
    let queue = [node];
    visited.add(node);
    while(queue.length){
        let curr = queue.shift();
        console.log(curr.val);
        for(let neighbor of curr.neighbors){
            if(!visited.has(neighbor)){
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}
BFS(node1);

3、應用：

在現實生活中，圖的應用非常多，如社交網路中的人際關係、地圖中的路徑規劃、路網中的交通流等。