JavaScript 数据结构实现

1. 栈（Stack）

栈是一种遵从后进先出（LIFO）原则的有序集合。

class Stack {
  constructor() {
    this.items = [];
  }
  
  // 入栈
  push(element) {
    this.items.push(element);
  }
  
  // 出栈
  pop() {
    if(this.isEmpty()) return undefined;
    return this.items.pop();
  }
  
  // 查看栈顶元素
  peek() {
    if(this.isEmpty()) return undefined;
    return this.items[this.items.length - 1];
  }
  
  // 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }
  
  // 清空栈
  clear() {
    this.items = [];
  }
  
  // 获取栈的大小
  size() {
    return this.items.length;
  }
}

2. 队列（Queue）

队列是遵循先进先出（FIFO）原则的一组有序的项。

class Queue {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }
  
  // 入队
  enqueue(element) {
    this.items[this.backIndex] = element;
    this.backIndex++;
  }
  
  // 出队
  dequeue() {
    if(this.isEmpty()) return undefined;
    const result = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return result;
  }
  
  // 查看队首元素
  front() {
    if(this.isEmpty()) return undefined;
    return this.items[this.frontIndex];
  }
  
  // 判断队列是否为空
  isEmpty() {
    return this.backIndex - this.frontIndex === 0;
  }
  
  // 获取队列大小
  size() {
    return this.backIndex - this.frontIndex;
  }
  
  // 清空队列
  clear() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }
}

3. 链表（LinkedList）

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。

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

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  
  // 添加元素到链表尾部
  append(element) {
    const node = new Node(element);
    if(!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while(current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }
  
  // 在指定位置插入元素
  insert(element, position) {
    if(position < 0 || position > this.size) return false;
    
    const node = new Node(element);
    if(position === 0) {
      node.next = this.head;
      this.head = node;
    } else {
      let current = this.head;
      let previous = null;
      let index = 0;
      
      while(index++ < position) {
        previous = current;
        current = current.next;
      }
      node.next = current;
      previous.next = node;
    }
    this.size++;
    return true;
  }
  
  // 删除指定位置的元素
  removeAt(position) {
    if(position < 0 || position >= this.size) return null;
    
    let current = this.head;
    if(position === 0) {
      this.head = current.next;
    } else {
      let previous = null;
      let index = 0;
      
      while(index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    this.size--;
    return current.element;
  }
  
  // 获取元素的索引
  indexOf(element) {
    let current = this.head;
    let index = 0;
    
    while(current) {
      if(current.element === element) return index;
      current = current.next;
      index++;
    }
    return -1;
  }
  
  // 判断链表是否为空
  isEmpty() {
    return this.size === 0;
  }
  
  // 获取链表大小
  getSize() {
    return this.size;
  }
  
  // 获取链表的头部元素
  getHead() {
    return this.head;
  }
}

4. 二叉搜索树（Binary Search Tree）

二叉搜索树是二叉树的一种，它只允许你在左侧节点存储比父节点小的值，在右侧节点存储比父节点大的值。

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  // 插入节点
  insert(key) {
    const newNode = new Node(key);
    if(!this.root) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }
  
  insertNode(node, newNode) {
    if(newNode.key < node.key) {
      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);
      }
    }
  }
  
  // 中序遍历
  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }
  
  inOrderTraverseNode(node, callback) {
    if(node) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }
  
  // 查找最小值
  min() {
    return this.minNode(this.root);
  }
  
  minNode(node) {
    let current = node;
    while(current && current.left) {
      current = current.left;
    }
    return current;
  }
  
  // 查找最大值
  max() {
    return this.maxNode(this.root);
  }
  
  maxNode(node) {
    let current = node;
    while(current && current.right) {
      current = current.right;
    }
    return current;
  }
  
  // 查找特定值
  search(key) {
    return this.searchNode(this.root, key);
  }
  
  searchNode(node, key) {
    if(!node) return false;
    if(key < node.key) {
      return this.searchNode(node.left, key);
    } else if(key > node.key) {
      return this.searchNode(node.right, key);
    } else {
      return true;
    }
  }
}

5. 树（Tree）

树是一种分层数据的抽象模型。除了二叉树，一个节点也可以有多个子节点的树结构。

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
    this.parent = null;
  }

  // 添加子节点
  addChild(childNode) {
    childNode.parent = this;
    this.children.push(childNode);
    return childNode;
  }

  // 移除子节点
  removeChild(childNode) {
    const index = this.children.indexOf(childNode);
    if (index !== -1) {
      childNode.parent = null;
      this.children.splice(index, 1);
    }
  }

  // 是否是叶子节点
  isLeaf() {
    return this.children.length === 0;
  }

  // 是否是根节点
  isRoot() {
    return this.parent === null;
  }

  // 获取节点深度
  getDepth() {
    let depth = 0;
    let current = this;
    while (current.parent) {
      depth++;
      current = current.parent;
    }
    return depth;
  }
}

class Tree {
  constructor(rootValue) {
    this.root = new TreeNode(rootValue);
  }

  // 广度优先遍历
  traverseBFS(callback) {
    const queue = [this.root];
    while (queue.length) {
      const node = queue.shift();
      callback(node);
      for (const child of node.children) {
        queue.push(child);
      }
    }
  }

  // 深度优先遍历
  traverseDFS(callback) {
    function traverse(node) {
      callback(node);
      for (const child of node.children) {
        traverse(child);
      }
    }
    traverse(this.root);
  }

  // 查找节点
  find(value) {
    let result = null;
    this.traverseBFS((node) => {
      if (node.value === value) {
        result = node;
      }
    });
    return result;
  }

  // 获取树的高度
  getHeight() {
    let maxDepth = 0;
    this.traverseDFS((node) => {
      const depth = node.getDepth();
      if (depth > maxDepth) {
        maxDepth = depth;
      }
    });
    return maxDepth + 1; // +1 是因为深度从0开始计数
  }
}

使用示例：

// 创建一个树结构
const tree = new Tree('root');

// 添加子节点
const node1 = new TreeNode('node1');
const node2 = new TreeNode('node2');
const node3 = new TreeNode('node3');
const node4 = new TreeNode('node4');

tree.root.addChild(node1);
tree.root.addChild(node2);
node1.addChild(node3);
node2.addChild(node4);

// 广度优先遍历
tree.traverseBFS(node => console.log(node.value));
// 输出: root, node1, node2, node3, node4

// 深度优先遍历
tree.traverseDFS(node => console.log(node.value));
// 输出: root, node1, node3, node2, node4

// 查找节点
const foundNode = tree.find('node3');
console.log(foundNode.value); // 输出: node3

// 获取树的高度
console.log(tree.getHeight()); // 输出: 3

这个树结构实现提供了以下功能：

1. 可以创建具有任意数量子节点的树
2. 支持添加和删除子节点
3. 可以判断节点是否为叶子节点或根节点
4. 支持获取节点深度
5. 提供广度优先(BFS)和深度优先(DFS)两种遍历方式
6. 可以根据值查找节点
7. 支持获取树的总高度

这种树结构适用于表示文件系统、组织架构等层级关系数据。

每个数据结构都包含了最基本和最常用的操作，并附带详细的注释说明。这些实现都是基于 JavaScript 的特性来完成的，可以直接在浏览器或 Node.js 环境中使用。