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"
愿每位开发者都能在学习过程中收获满满的快乐！
