推荐|JavaScript 中实现常见数据结构：栈、队列与树

文章目录

JavaScript 中实现常见数据结构：栈、队列与树
- 引言

JavaScript 中实现常见数据结构：栈、队列与树

引言

在前端开发中，理解和掌握基础数据结构是提升代码质量、优化算法性能和解决复杂问题的关键。本文将通过JavaScript语言，深入浅出地介绍三种常用的数据结构——栈（Stack）、队列（Queue）和树（Tree），并辅以实例代码帮助读者更好地理解和运用它们。

一、栈（Stack）

栈是一种遵循"后进先出"（Last In First Out, LIFO）原则的线性数据结构。在JavaScript中，我们可以使用数组或类来模拟栈的行为。

用一个序列图（sequence diagram）来表示其“后进先出”（LIFO）的操作过程。入栈(push)、查看栈顶元素(peek)和出栈(pop)操作。

下面是一个简单的例子：

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

  // 入栈
  push(element) {
    this.items.push(element);
  }

  // 出栈
  pop() {
    if (this.isEmpty()) {
      return 'Stack is empty';
    }
    return this.items.pop();
  }

  // 查看栈顶元素
  peek() {
    return this.items[this.items.length - 1];
  }

  // 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 获取栈的大小
  size() {
    return this.items.length;
  }
}

// 示例用法：
const myStack = new Stack();
myStack.push(1);
myStack.push(2);
console.log(myStack.pop()); // 输出: 2

栈作为一种“后进先出”（Last In First Out, LIFO）的数据结构，其操作主要包含两个核心方法：push用于将元素添加到栈顶，pop用于从栈顶移除并返回最后一个添加的元素。在JavaScript中，我们可以利用数组的内置方法来方便地模拟栈的行为，或者创建一个自定义类以更好地体现栈的逻辑和功能。

使用JavaScript数组模拟栈

由于JavaScript数组提供了push和pop方法，它们恰好符合栈的操作要求，因此可以直接用数组实现栈的功能：

// 使用数组模拟栈
let stack = [];

// 入栈操作
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack); // 输出: [1, 2, 3]

// 出栈操作
let topElement = stack.pop(); // 从栈顶弹出元素，并赋值给topElement
console.log(topElement); // 输出: 3
console.log(stack); // 输出: [1, 2]

创建自定义栈类

尽管可以简单地使用数组，但为了更清晰地表示栈的语义以及便于扩展功能，我们通常会创建一个自定义栈类：

class Stack {
  constructor() {
    this.items = []; // 内部使用数组存储栈中的元素
  }

  // 入栈方法
  push(element) {
    this.items.push(element);
  }

  // 出栈方法
  pop() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty');
    }
    return this.items.pop();
  }

  // 查看栈顶元素，不改变栈状态
  peek() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty');
    }
    return this.items[this.items.length - 1];
  }

  // 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 获取栈的大小
  size() {
    return this.items.length;
  }
}

// 示例用法：
const myStack = new Stack();
myStack.push('First');
myStack.push('Second');
console.log(myStack.peek()); // 输出: 'Second'
console.log(myStack.pop()); // 输出: 'Second'
console.log(myStack.isEmpty()); // 输出: false

通过这样的自定义栈类，我们不仅能够直观地进行栈操作，还可以增加额外的方法如peek来查看栈顶元素而无需真正移除它，从而满足更多复杂场景的需求。

二、队列（Queue）

队列遵循“先进先出”（First In First Out, FIFO）原则。同样，我们也可以利用数组或者类实现队列功能。

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

  // 入队
  enqueue(element) {
    this.items.push(element);
  }

  // 出队
  dequeue() {
    if (this.isEmpty()) {
      return 'Queue is empty';
    }
    return this.items.shift();
  }

  // 查看队首元素
  front() {
    return this.items[0];
  }

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

  // 获取队列大小
  size() {
    return this.items.length;
  }
}

// 示例用法：
const myQueue = new Queue();
myQueue.enqueue('Front');
myQueue.enqueue('Middle');
console.log(myQueue.dequeue()); // 输出: 'Front'

三、树（Tree）

树是一种非线性的数据结构，它由节点（Node）和边组成，每个节点可以有零个或多个子节点。在JavaScript中，我们可以创建一个表示节点的类，并通过引用的方式构建层级关系。

class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  addChild(childNode) {
    this.children.push(childNode);
  }
}

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

  traverseDFS(node = this.root, callback) { // 深度优先遍历示例
    callback(node);
    for (let child of node.children) {
      this.traverseDFS(child, callback);
    }
  }

  traverseBFS() { // 广度优先遍历示例，使用队列
    let queue = [this.root];
    while(queue.length > 0) {
      let current = queue.shift();
      console.log(current.data); // 打印节点值
      queue = [...queue, ...current.children];
    }
  }
}

// 示例用法：
const tree = new Tree('Root');
const child1 = new Node('Child1');
const child2 = new Node('Child2');
tree.root.addChild(child1);
tree.root.addChild(child2);
tree.traverseDFS(); // 深度优先遍历
tree.traverseBFS(); // 广度优先遍历

结语与祝福代码

理解并掌握这些基础数据结构就像是拥有了强大的工具箱，使我们在前端编程世界中游刃有余。让我们一起成长，就如同栈中的元素不断积累，如同队列中的任务逐个完成，如同树般枝繁叶茂，向着技术的高峰攀登！

下面是一个结合栈和字符串的小彩蛋，生成一句祝福：

class ReverseWordsInSentence {
  reverseWords(sentence) {
    const stack = new Stack();
    sentence.split(' ').forEach(word => stack.push(word));
    
    let reversedSentence = '';
    while (!stack.isEmpty()) {
      reversedSentence += stack.pop() + ' ';
    }
    return reversedSentence.trim();
  }
}

const revWords = new ReverseWordsInSentence();
console.log(revWords.reverseWords("Happy learning, fellow developers!")); 
// 输出："developers! fellow learning, Happy"

愿每位开发者都能在学习过程中收获满满的快乐！