数组结构
参考:https://aboss.top/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(), "淘汰了")
}
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("上海自来水来自海上")
链表
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
链表的特点
- 插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)
- 和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。
单链表
每个节点只包含一个指针,即后继指针。
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), "淘汰了")
}
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
}
}