aboss.top
JavaScript数据结构与算法
编辑
2026-04-01
undefined
00

目录

数组结构
栈结构
pop() {
队列结构
封装与应用
双端队列
链表
单链表
双链表
循环链表

数组结构

参考：http://8.129.6.198/post/173/

栈结构

栈(stack)又名堆栈，是一种运算受限的线性表，限定仅在表尾进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈，从一个栈删除元素称作出栈。

特点：后进先出，即 Last in First out (LIFO)。

class Stack {
  #items = [] //# 符号声明私有属性，ES13 新特性
pop() {
return this.#items.pop() //出栈
}
push(data) {
return this.#items.push(data) //进栈
}
peek() {
return this.#items.at(-1) //栈顶
}
isEmpty() {
return this.#items.length === 0
}
size() {
return this.#items.length
}
clear() {
this.#items = []
}
toString() {
return this.#items.join(" ")
}
}
// 十进制转 2 8 16 进制
function convert(decNumber, base) {
let remStack = new Stack()
let number = decNumber
let string = ""
let baseString = "0123456789ABCDEF"
while (number > 0) {
remStack.push(number % base)
number = Math.floor(number / base)
}
while (!remStack.isEmpty()) {
string += baseString[remStack.pop()]
}
return string
}
convert(500, 16)

队列结构

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾（入队），进行删除操作的端称为队头（出队）。队列中没有元素时，称为空队列。

特点：先进先出，即 First in First out(FIFO)。

封装与应用

class Queue {
#items = {}
#lowCount = 0
#count = 0
dequeue() {
if (this.isEmpty()) {
return undefined
}
let res = this.#items[this.#lowCount]
delete this.#items[this.#lowCount]
this.#lowCount++
return res //出队

}
enqueue(data) {
this.#items[this.#count] = data //入队
this.#count++
}
front() {
return this.#items[this.#lowCount] //队头
}
isEmpty() {
return this.size() === 0
}
size() {
return this.#count - this.#lowCount
}
clear() {
this.#items = {}
this.#count = 0
this.#lowCount = 0
}
toString() {
let str = ""
for (let i = this.#lowCount; i < this.#count; i++) {
str += ${this.#items[i]} 
}
return str

}
}
// 击鼓传花游戏
function game(list, num) {
let queue = new Queue()
for (let i = 0; i < list.length; i++) {
queue.enqueue(list[i])
}
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue())
}
console.log(queue.dequeue(), &quot;淘汰了&quot;)

}
return queue.dequeue() + " 获胜"
}
game(["张三", "李四", "王五", "赵六", "孙七"], 7)

双端队列

class DeQueue {
#items = {}
#lowCount = 0 //队头索引
#count = 0
removeFront() {
if (this.isEmpty()) {
return undefined
}
let res = this.#items[this.#lowCount]
delete this.#items[this.#lowCount]
this.#lowCount++

return res

}
removeBack() {
if (this.isEmpty()) {
return
}
this.#count--
const res = this.#items[this.#count]
delete this.#items[this.#count]

return res

}
addFront(data) {
if (this.isEmpty()) {
this.addBack(data)
} else {
if (this.#lowCount > 0) {
this.#lowCount--
this.#items[this.#lowCount] = data
} else {
// #lowCount=0
for (let i = this.#count; i > 0; i--) {
this.#items[i] = this.#items[i - 1]
}
}
}
}
addBack(data) {
this.#items[this.#count] = data
this.#count++
}
peekFront() {
return this.#items[this.#lowCount]
}
peekBack() {
return this.#items[this.#count - 1]
}
isEmpty() {
return this.size() === 0
}
size() {
return this.#count - this.#lowCount
}
clear() {
this.#items = {}
this.#count = 0
this.#lowCount = 0
}
toString() {
let str = ""
for (let i = this.#lowCount; i < this.#count; i++) {
str += ${this.#items[i]} 
}
return str

}
}
// 回文字符串检查
function test(str) {
const lowstr = str.toLocaleLowerCase().split(" ").join("")
let dequeue = new DeQueue()
for (let i = 0; i < lowstr.length; i++) {
dequeue.addBack(lowstr[i])
}
let isEqual = true
while (dequeue.size() > 1) {
if (dequeue.removeFront() != dequeue.removeBack()) {
isEqual = false
break
}
}
return isEqual
}
test("上海自来水来自海上")

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的特点

  1. 插入、删除数据效率高O(1)级别(只需更改指针指向即可)，随机访问效率低O(n)级别(需要从链头至链尾进行遍历)
  2. 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

单链表

每个节点只包含一个指针，即后继指针。

class Node {
constructor(element) {
this.element = element
this.next = null
}
}
class LinkedList {
constructor() {
this.count = 0
this.head = null
}
push(element) {
const node = new Node(element)
if (this.head === null) {
  this.head = node
} else {
  let current = this.head

  while (current.next !== null) {
    current = current.next
  }

  current.next = node
}

this.count++

}
getNodeAt(index) {
if (index >= 0 && index < this.count) {
let node = this.head
for (let i = 0; i < index; i++) {
node = node.next
}
  return node
}

return

}
// 指定位置删除
removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head
if (index === 0) {
this.head = this.head.next
} else {
let previous = this.getNodeAt(index - 1)
current = previous.next
previous.next = current.next
}
  this.count--
  return current.element
}

return

}
equalFn(a, b) {
return JSON.stringify(a) === JSON.stringify(b)
}
indexOf(element) {
let current = this.head
for (let i = 0; i < index; i++) {
if (this.equalFn(element, current.element)) {
return i
}
current = current.next
}
return -1

}
// 指定元素删除
remove(element) {
const index = this.indexOf(element)
return this.removeAt(index)
}
insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new Node(element)
if (index === 0) {
const current = this.head
node.next = current
this.head = node
} else {
const previous = this.getNodeAt(index - 1)
const current = previous.next
    node.next = current
    previous.next = node
  }

  this.count++
  return true
}

return false

}
isEmpty() {
return this.size() === 0
}
size() {
return this.count
}
getHead() {
return this.head
}
}
// 回文字符串检查
function test(str) {
const lowstr = str.toLocaleLowerCase().split(" ").join("")
let sll = new LinkedList()
for (let i = 0; i < lowstr.length; i++) {
sll.push(lowstr[i])
}
let isEqual = true
while (sll.size() > 1) {
if (sll.removeAt(0) !== sll.removeAt(sll.size() - 1)) {
isEqual = false
break
}
}
return isEqual
}
test("上海自来水来自海上")

击鼓传花游戏使用单链表：

// 击鼓传花游戏
function game(list, num) {
let queue = new LinkedList()
for (let i = 0; i < list.length; i++) {
queue.push(list[i])
}
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.push(queue.removeAt(0))
}
console.log(queue.removeAt(0), &quot;淘汰了&quot;)

}
return queue.removeAt(0) + " 获胜"
}
game(["张三", "李四", "王五", "赵六", "孙七"], 7)

十进制转 2 8 16 进制：

// 十进制转 2 8 16 进制
function convert(decNumber, base) {
let remStack = new LinkedList()
let number = decNumber
let string = ""
let baseString = "0123456789ABCDEF"
while (number > 0) {
remStack.push(number % base)
number = Math.floor(number / base)
}
while (!remStack.isEmpty()) {
string += baseString[remStack.removeAt(remStack.size() - 1)]
}
return string
}
convert(500, 16)

双链表

class DoublyNode extends Node {
constructor(element) {
super(element)
this.prev = null
}
}
class DoublyLinkedList extends LinkedList {
constructor() {
super()
this.tail = null
}
push(element) {
const node = new DoublyNode(element)
if (this.head === null) {
this.head = node
this.tail = node
} else {
this.tail.next = node
node.prev = this.tail
this.tail = node
}
this.count++

}
remove(element) {
const index = this.indexOf(element)
return this.removeAt(index)
}
insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new DoublyNode(element)
let current = this.head
if (index === 0) {
if (this.head === null) {
this.head = node
this.tail = node
} else {
node.next = this.head
this.head.prev = node
this.head = node
}
} else if (index === this.count) {
current = this.tail
current.next = node
node.prev = current
this.tail = node
} else {
const previous = this.getNodeAt(index - 1)
current = previous.next
    node.next = current
    current.prev = node
    previous.next = node
    node.prev = previous
  }

  this.count++
  return true
}

return false

}
removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head
if (index === 0) {
this.head = current.next
if (this.count === 1) {
this.tail = null
} else {
this.head.prev = null
}
} else if (index === this.count - 1) {
current = this.tail
this.tail = current.prev
this.tail.next = null
} else {
let previous = this.getNodeAt(index - 1)
current = previous.next
previous.next = current.next
current.next.prev = previous
}
  this.count--
  return current.element
}

return

}
getHead() {
return this.head
}
getTail() {
return this.tail
}
}

循环链表

循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针(tail.next)不是undefined，而是指向第一个元素(head)。

class CircularLinkedList extends LinkedList {
constructor() {
super()
}
push(element) {
const node = new Node(element)
let current
if (this.head === null) {
this.head = node
} else {
current = this.getNodeAt(this.size() - 1)
current.next = node
}
node.next = this.head
this.count++

}
insert() {
if (index >= 0 && index <= this.count) {
const node = new Node(element)
let current = this.head
if (index === 0) {
if (this.head === null) {
this.head = node
node.next = this.head
} else {
node.next = current
this.head = node
      current = this.getNodeAt(this.size() - 1)
      current.next = this.head
    }
  } else {
    const previous = this.getNodeAt(index - 1)
    node.next = previous.next
    previous.next = node
  }

  this.count++
  return true
}

return false

}
removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head
if (index === 0) {
if (this.size() === 1) {
this.head = null
} else {
let last = this.getNodeAt(this.size() - 1)
this.head = this.head.next
last.next = this.head
}
} else {
const previous = this.getNodeAt(index - 1)
current = previous.next
previous.next = current.next
}
  this.count--
  return current.element
}

return

}
}

本文作者:a

本文链接:

版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！