JavaScript 实现队列、栈、链表

队列

队列就是先进先出

// queue.js
class Queue {
  constructor() {
    this.data = []
  }
  enqueue(element) { // 入队列
    this.data.push(element)
  }
  dequeue() { // 出队列
    this.data.shift()
  }
  clear() { // 清空队列
    this.data.length = 0
  }
  getLength() { // 队列长度
    return this.data.length
  }
}
复制代码

栈

栈就是后进先出

// stack.js
class Stack {
  constructor() {
    this.data = []
  }
  push(element) { // 入栈
    this.data.push(element)
  }
  pop() { // 出栈
    this.data.pop()
  }
  clear() { // 清空栈
    this.data.length = 0
  }
  getLength() { // 获取栈的长度
    return this.data.length
  }
}
复制代码

单向链表

链表让我们删除数据和新增数据更加方便！head指针指向第一个存入的元素节点，每个节点都有next属性指向一下一个元素节点，最后一个元素的指针指向null

class Node {
  constructor(element) {
    this.element = element // 节点保存的内容
    this.next = null // 指针，指向下一个节点
  }
}

class LinkList {
  constructor() {
    this.head = null // 表头，默认指向第一个节点，没有则为null
    this.length = 0
  }
  append(element) { // 新增节点
    const node = new Node(element)
    if (this.head === null)
      this.head = node
    else {
      let current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = node // 找到最后一个节点，将next指向新的节点
    }
    this.length++
  }
  insert(position, elememt) { // 插入节点
    if (position >= 0 && position <= this.length) {
      const node = new Node(elememt)
      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.length++
    }
  }
  remove(position) { // 移除节点
    if (position > -1 && position < this.length) {
      if (position === 0) {
        this.head = this.head.next
      } else {
        let current = this.head
        let previous = null,
          index = 0
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      this.length--
    }
  }
  update(position, element) { // 更新节点内容
    if (position > -1 && position < this.length) {
      let index = 0
      let current = this.head
      while (index++ < position) {
        current = current.next
      }
      current.element = element
    }
  }
}
复制代码