JavaScript 是一种灵活且强大的编程语言，其数据结构在前端开发中扮演着重要角色。理解和正确使用这些数据结构能够大大提高代码的效率和可读性，在不同场景选择正确的数据结构会让代码运行效率更高，逻辑简单，如果选择了不恰当的数据结构，可能会影响所写程序的性能。因此，了解不同数据结构和它们的适用范围十分重要。

JavaScript 基本数据结构包含 Number、BigInt、String、Boolean、Null、Undefined、Symbol、Object。除了基本数据结构之外，还有数组、对象、栈、队列、链表、集合、树、图等复杂数据结构。

一、基本数据类型

JavaScript 共有八种基本数据类型：

• Number：表示数字（包括整数和浮点数）。
• BigInt：表示任意精度的整数。
• String：表示文本数据。
• Boolean：表示真或假。
• Null：表示空值。
• Undefined：表示未定义的值。
• Symbol：表示唯一且不可变的值，通常用于对象属性的唯一标识。
• Object：复杂数据结构，用于存储集合和更复杂的实体。

这些基本数据类型是构建复杂数据类型的基础。

• 数组： 一种用于存储有序数据集合的数据结构。每个元素都有一个对应的索引，可以通过索引快速访问和修改元素。
• 对象： 一种用于存储键值对的无序集合的数据结构。键（属性）可以是字符串或 Symbol，值可以是任意类型。
• 栈：一种遵从先进后出 (LIFO) 原则的有序集合；新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端为栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
• 队列：与上相反，一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项；队列在尾部添加新元素，并从头部移除元素。最新添加的元素必须排在队列的末尾。
• 链表：存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的；每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（指针/链接）组成。
• 集合：由一组无序且唯一（即不能重复）的项组成；这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。
• 树：由 n（n>=1）个有限节点组成一个具有层次关系的集合；把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的，基本呈一对多关系，树也可以看做是图的特殊形式。
• 图：图是网络结构的抽象模型；图是一组由边连接的节点（顶点）；任何二元关系都可以用图来表示，常见的比如：道路图、关系图，呈多对多关系。

这些是复杂数据类型的，下面对上述复杂数据类型进行详解。

二、复杂数据类型

1. 数组（Array）

数组是一种用于存储有序数据集合的数据结构。每个元素都有一个对应的索引，可以通过索引快速访问和修改元素。

示例：

let fruits = ['apple', 'banana', 'cherry'];
console.log(fruits[1]); // 输出：banana

常用方法：

• push()：向数组末尾添加一个或多个元素。
• pop()：移除数组末尾的一个元素。
• shift()：移除数组开头的一个元素。
• unshift()：向数组开头添加一个或多个元素。
• splice()：在任意位置添加/删除元素。
• map()：对数组中的每个元素执行指定操作，返回一个新的数组。
• filter()：筛选出符合条件的元素，返回一个新的数组。
• reduce()：对数组中的每个元素执行累积操作，最终返回一个值。
• concat()：合并两个或多个数组，不改变现有数组，返回新数组。
• join()：将数组的所有元素连接成一个字符串。
• slice()：返回数组的浅拷贝，包含从开始索引到结束索引（不包括结束索引）之间的项。
• indexOf()：返回数组中第一次找到的指定元素的索引，如果不存在则返回 -1。
• lastIndexOf()：返回数组中最后一次找到的指定元素的索引，如果不存在则返回 -1。
• includes()：判断数组是否包含某个值，根据情况返回 true 或 false。
• find()：返回数组中满足提供的测试函数的第一个元素的值，否则返回 undefined。
• findIndex()：返回数组中满足提供的测试函数的第一个元素的索引，否则返回 -1。
• some()：测试数组中的某些元素是否通过由提供的函数实现的测试。
• every()：测试数组中的所有元素是否通过由提供的函数实现的测试。
• flat()：按照指定深度递归地将所有子数组连接到第一个数组中。
• flatMap()：首先使用映射函数映射每个元素，然后将结果压缩成一个新数组。
• sort()：对数组元素进行排序并返回数组。
• reverse()：颠倒数组中元素的顺序并返回数组。

应用场景：

数组适用于需要有序存储和快速访问元素的场景，例如处理列表、队列、栈等。它们常用于存储一组相关数据，例如一系列数字、字符串或对象，便于迭代、排序和过滤操作。

2. 对象（Object）

对象是一种用于存储键值对的无序集合的数据结构。键（属性）可以是字符串或 Symbol，值可以是任意类型。

示例：

let person = {
    name: 'Alice',
    age: 25,
    greet: function() {
        console.log('Hello, ' + this.name);
    }
};
console.log(person.name); // 输出：Alice
person.greet(); // 输出：Hello, Alice

常用方法：

• Object.keys()：获取对象的所有键。
• Object.values()：获取对象的所有值。
• Object.entries()：获取对象的所有键值对。
• hasOwnProperty()：检查对象是否具有某个属性。
• Object.assign()：将一个或多个源对象的所有可枚举属性复制到目标对象，返回目标对象。
• Object.create()：使用指定的原型对象和属性创建一个新对象。
• Object.defineProperty()：直接在对象上定义一个新属性，或修改现有属性，并返回该对象。
• Object.defineProperties()：直接在对象上定义新的属性或修改现有属性，返回该对象。
• Object.freeze()：冻结对象，防止修改现有属性的值和添加新属性。
• Object.isFrozen()：判断对象是否被冻结。
• Object.seal()：密封对象，防止添加新属性和删除现有属性。
• Object.isSealed()：判断对象是否被密封。
• Object.preventExtensions()：防止对象扩展，即无法添加新属性。
• Object.isExtensible()：判断对象是否可扩展。
• Object.getOwnPropertyDescriptor()：返回指定对象上一个自有属性对应的属性描述符。
• Object.getOwnPropertyDescriptors()：返回指定对象所有自身属性的属性描述符。
• Object.entries()：返回一个给定对象自身可枚举属性的键值对数组。
• Object.fromEntries()：将键值对列表转换为对象。
• Object.values()：返回一个给定对象自身可枚举属性值的数组。
• Object.getPrototypeOf()：返回指定对象的原型（内部 [[Prototype]] 属性的值）。
• Object.setPrototypeOf()：设置对象的原型（即内部 [[Prototype]] 属性）。

应用场景：

对象适用于需要描述实体和存储相关属性的场景，例如用户信息、配置选项等。对象提供了一种键值对的结构，方便存储和访问数据，尤其是在处理复杂的数据模型时，例如用户配置、数据库记录等。

3. 集合（Set）

集合是一种用于存储唯一值的数据结构，可以是任何类型的值。

示例：

let uniqueNumbers = new Set([1, 2, 3, 3, 4]);
console.log(uniqueNumbers); // 输出：Set { 1, 2, 3, 4 }

常用方法：

• add()：向集合添加一个元素。
• delete()：从集合删除一个元素。
• has()：检查集合中是否存在某个元素。
• clear()：清空集合。
• entries()：返回一个包含集合中所有元素的键值对的数组。
• forEach()：对集合中的每个元素执行指定操作。
• values()：返回一个包含集合中所有值的数组。
• keys()：返回一个包含集合中所有键的数组（与 values() 方法相同）。

应用场景：

集合适用于需要存储唯一值的场景，例如去重、快速查找元素。它们在需要保证数据唯一性的时候非常有用，比如管理一组唯一标识符或需要进行快速集合操作（如并集、交集）的场合。

4. 映射（Map）

映射是一种用于存储键值对的数据结构，键和值可以是任何类型。

示例：

let map = new Map();
map.set('name', 'Bob');
map.set('age', 30);
console.log(map.get('name')); // 输出：Bob

常用方法：

• set()：设置键值对。
• get()：获取某个键对应的值。
• has()：检查映射中是否存在某个键。
• delete()：删除某个键值对。
• clear()：清空映射。
• entries()：返回一个包含映射中所有键值对的数组。
• forEach()：对映射中的每个键值对执行指定操作。
• keys()：返回一个包含映射中所有键的数组。
• values()：返回一个包含映射中所有值的数组。
• size：返回映射中键值对的数量。

应用场景：

映射适用于需要灵活存储键值对的场景，例如缓存、查找表等。它们提供了高效的键值对存储和检索，适合用于需要动态更新键值对并能快速查找键对应值的情况，如配置管理、数据关联映射等。

5. 堆栈（Stack）

堆栈是一种后进先出（LIFO）的数据结构，主要通过数组、链表来实现。

使用数组实现堆栈：

使用数组实现堆栈非常简单，适用于一般场景，但在进行大量插入和删除操作时可能会导致内存碎片化。

class Stack {
    constructor() {
        this.items = [];
    }

    // 向堆栈添加一个元素
    push(element) {
        this.items.push(element);
    }

    // 从堆栈移除一个元素
    pop() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.items.pop();
    }

    // 查看堆栈顶端的元素
    peek() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.items[this.items.length - 1];
    }

    // 检查堆栈是否为空
    isEmpty() {
        return this.items.length === 0;
    }

    // 返回堆栈的大小
    size() {
        return this.items.length;
    }

    // 清空堆栈
    clear() {
        this.items = [];
    }
}

// 示例使用
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 输出：20
console.log(stack.pop());  // 输出：20
console.log(stack.isEmpty()); // 输出：false

使用链表实现堆栈：

使用链表实现堆栈更为高效，尤其是在需要频繁插入和删除操作的情况下。链表实现的堆栈在内存管理方面更具优势。

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedListStack {
    constructor() {
        this.top = null;
        this.count = 0;
    }

    // 向堆栈添加一个元素
    push(element) {
        const newNode = new Node(element);
        newNode.next = this.top;
        this.top = newNode;
        this.count++;
    }

    // 从堆栈移除一个元素
    pop() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        const poppedNode = this.top;
        this.top = this.top.next;
        this.count--;
        return poppedNode.value;
    }

    // 查看堆栈顶端的元素
    peek() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.top.value;
    }

    // 检查堆栈是否为空
    isEmpty() {
        return this.top === null;
    }

    // 返回堆栈的大小
    size() {
        return this.count;
    }

    // 清空堆栈
    clear() {
        this.top = null;
        this.count = 0;
    }
}

// 示例使用
const linkedStack = new LinkedListStack();
linkedStack.push(10);
linkedStack.push(20);
console.log(linkedStack.peek()); // 输出：20
console.log(linkedStack.pop());  // 输出：20
console.log(linkedStack.isEmpty()); // 输出：false

应用场景：

• 递归调用：堆栈在递归函数调用中扮演重要角色。每次递归调用都会将函数的状态（如变量值、程序计数器等）压入堆栈，递归返回时从堆栈中弹出这些状态进行恢复。编译器和解释器通常使用堆栈来实现递归函数的调用和返回。
• 表达式求值：堆栈用于表达式求值和语法解析。例如，将中缀表达式转换为后缀表达式（逆波兰表达式），以及后缀表达式的计算。堆栈在处理操作符和操作数时非常有效。
• 括号匹配：堆栈可以用来检查括号是否成对出现和匹配。在编译器、解释器和代码编辑器中，堆栈常用于验证源代码中的括号是否正确匹配。
• 浏览器的前进和后退功能：浏览器利用堆栈来实现页面的前进和后退功能。访问新页面时，将当前页面压入后退堆栈，点击后退按钮时，将当前页面压入前进堆栈，并从后退堆栈弹出页面进行显示。
• 函数调用管理：在程序执行过程中，堆栈用于管理函数调用。每当一个函数被调用时，函数的返回地址和局部变量会被压入堆栈，函数执行完毕后，这些信息会从堆栈中弹出，恢复到调用函数的状态。
• 深度优先搜索（DFS）：深度优先搜索算法使用堆栈来记录路径。当遍历到一个新的节点时，将其压入堆栈；当回溯时，将节点从堆栈中弹出。这在图和树的遍历中非常常见。
• 逆序输出：堆栈可以用于逆序输出一系列数据。例如，输入一个字符串，通过将字符逐个压入堆栈，然后逐个弹出，就可以实现字符串的逆序输出。
• 语法解析：编译器和解释器在进行语法解析时常用堆栈来处理不同级别的表达式和语句，特别是在处理中缀表达式和解析程序结构时。
• 内存管理：堆栈用于管理程序的内存。函数调用时，局部变量和参数会被分配在堆栈上。函数返回时，堆栈会自动清理这些变量和参数，这种方式简单高效，适合临时变量的管理。
• 文本编辑器的撤销功能：文本编辑器中的撤销和重做功能通常使用两个堆栈来实现。一个堆栈记录用户的操作以便撤销，另一个堆栈记录撤销的操作以便重做。

6. 队列（Queue）

队列（Queue）是一种先进先出（FIFO，First In First Out）的数据结构，元素的插入发生在队尾（rear），删除发生在队头（front）。可以使用多种方法实现队列，包括数组和链表。

使用数组实现队列

class Queue {
    constructor() {
        this.items = [];
    }

    // 向队列添加一个元素
    enqueue(element) {
        this.items.push(element);
    }

    // 从队列移除一个元素
    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items.shift();
    }

    // 查看队列头部的元素
    front() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items[0];
    }

    // 检查队列是否为空
    isEmpty() {
        return this.items.length === 0;
    }

    // 返回队列的大小
    size() {
        return this.items.length;
    }

    // 清空队列
    clear() {
        this.items = [];
    }
}

// 示例使用
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
console.log(queue.front()); // 输出：10
console.log(queue.dequeue()); // 输出：10
console.log(queue.isEmpty()); // 输出：false

使用链表实现队列

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedListQueue {
    constructor() {
        this.front = null;
        this.rear = null;
        this.count = 0;
    }

    // 向队列添加一个元素
    enqueue(element) {
        const newNode = new Node(element);
        if (this.rear) {
            this.rear.next = newNode;
        } else {
            this.front = newNode;
        }
        this.rear = newNode;
        this.count++;
    }

    // 从队列移除一个元素
    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        const dequeuedNode = this.front;
        this.front = this.front.next;
        if (!this.front) {
            this.rear = null;
        }
        this.count--;
        return dequeuedNode.value;
    }

    // 查看队列头部的元素
    front() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.front.value;
    }

    // 检查队列是否为空
    isEmpty() {
        return this.count === 0;
    }

    // 返回队列的大小
    size() {
        return this.count;
    }

    // 清空队列
    clear() {
        this.front = this.rear = null;
        this.count = 0;
    }
}

// 示例使用
const linkedQueue = new LinkedListQueue();
linkedQueue.enqueue(10);
linkedQueue.enqueue(20);
console.log(linkedQueue.front()); // 输出：10
console.log(linkedQueue.dequeue()); // 输出：10
console.log(linkedQueue.isEmpty()); // 输出：false

应用场景：

• 任务调度： 队列在任务调度系统中非常常见。操作系统中的进程调度、打印队列、任务队列等都使用队列来管理任务的执行顺序。任务按顺序进入队列并依次被处理。
• 消息队列：消息队列用于在分布式系统或异步编程中传递消息。生产者将消息发送到队列，消费者从队列中读取消息进行处理。这种方式可以实现系统的松耦合和异步处理，提高系统的性能和可靠性。
• 线程和进程管理：在多线程或多进程编程中，队列常用于管理线程或进程的任务。例如，线程池中的任务排队等待可用线程处理，任务按顺序进入队列并被线程执行。
• 实时数据流处理：在实时数据流处理系统中，队列用于存储和管理实时到达的数据。数据按顺序进入队列并被处理，这在实时分析、监控系统等领域非常常见。
• 网站爬虫：
• 在网站爬虫中，队列用于存储待抓取的网页 URL。爬虫按顺序从队列中读取 URL 进行抓取，并将新发现的 URL 加入队列，确保按顺序和层次进行爬取。

7. 链表（Linked List）

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和一个指向下一个节点的指针。与数组不同，链表中的元素在内存中不是连续存储的。

示例：

class Node {
    constructor(data) {
        this.data = data; // 节点数据
        this.next = null; // 下一个节点的指针
    }
}

class LinkedList {
    constructor() {
        this.head = null; // 头节点
    }

    append(data) {
        let newNode = new Node(data); // 创建新节点
        if (!this.head) {
            this.head = newNode; // 如果链表为空，将新节点作为头节点
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next; // 遍历到链表末尾
            }
            current.next = newNode; // 在链表末尾插入新节点
        }
    }
}

let list = new LinkedList();
list.append(1);
list.append(2);
console.log(list.head.data); // 输出：1

应用场景：

链表适用于需要频繁插入和删除操作的场景，例如实现栈、队列等。

8. 树（Tree）

树是一种层次结构的数据结构，其中每个节点都有零个或多个子节点。常见的树包括二叉树、二叉搜索树、平衡树等。

示例：

class TreeNode {
    constructor(value) {
        this.value = value; // 节点值
        this.left = null; // 左子节点
        this.right = null; // 右子节点
    }
}

class BinaryTree {
    constructor() {
        this.root = null; // 根节点
    }

    insert(value) {
        const newNode = new TreeNode(value); // 创建新节点
        if (!this.root) {
            this.root = newNode; // 如果树为空，直接将新节点作为根节点
        } else {
            this.insertNode(this.root, newNode); // 否则，递归插入新节点
        }
    }

    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            // 新节点的值小于当前节点，插入到左子树
            if (!node.left) {
                node.left = newNode; // 如果左子树为空，直接插入
            } else {
                this.insertNode(node.left, newNode); // 否则，递归插入到左子树
            }
        } else {
            // 新节点的值大于或等于当前节点，插入到右子树
            if (!node.right) {
                node.right = newNode; // 如果右子树为空，直接插入
            } else {
                this.insertNode(node.right, newNode); // 否则，递归插入到右子树
            }
        }
    }
}

const tree = new BinaryTree();
tree.insert(7);
tree.insert(4);
tree.insert(9);

应用场景：

树结构适用于层次结构的数据表示，如 DOM 树、组织结构图、分类树等。

9. 图（Graph）

图是一种非线性数据结构，由节点（顶点）和连接这些节点的边组成。图可以是有向的或无向的。

示例：

class Graph {
    constructor() {
        this.adjacencyList = {}; // 邻接表
    }

    addVertex(vertex) {

 if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = []; // 添加顶点
        }
    }

    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2); // 添加边
        this.adjacencyList[vertex2].push(vertex1); // 无向图需要双向添加
    }

    depthFirstSearch(start) {
        const result = [];
        const visited = {};
        const adjacencyList = this.adjacencyList;

        (function dfs(vertex) {
            if (!vertex) return null;
            visited[vertex] = true; // 标记为访问过
            result.push(vertex);
            adjacencyList[vertex].forEach(neighbor => {
                if (!visited[neighbor]) {
                    return dfs(neighbor); // 递归访问邻居节点
                }
            });
        })(start);

        return result; // 返回深度优先搜索结果
    }
}

const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
console.log(graph.depthFirstSearch('A')); // 输出：['A', 'B', 'C']

应用场景：

图结构适用于表示复杂关系的数据，如社交网络、路径查找、依赖关系等。