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

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

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

引言

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

一、栈(Stack)

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

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

image.png

image.png

下面是一个简单的例子:

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数组提供了pushpop方法,它们恰好符合栈的操作要求,因此可以直接用数组实现栈的功能:

// 使用数组模拟栈
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"

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

相关文章
|
4天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
12 3
|
1天前
数据结构 树(第10-14天)
数据结构 树(第10-14天)
|
1天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
1天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
|
1天前
数据结构——栈和队列
数据结构——栈和队列
|
2天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
3天前
|
存储 NoSQL 大数据
【大数据】LSM树,专为海量数据读写而生的数据结构
【大数据】LSM树,专为海量数据读写而生的数据结构
16 0
|
4天前
|
算法 调度 Python
数据结构与算法-队列篇
数据结构与算法-队列篇
11 3
|
4天前
数据结构初阶 队列
数据结构初阶 队列
4 0
|
4天前
数据结构初阶 栈
数据结构初阶 栈
8 1