JS-----数据结构与算法（2）

目录

三. 栈结构

1.认识栈结构

2. 封装栈结构 

3. 应用

3-1 十进制转二进制

3-2 进制转换法

四. 队列

1.队列是什么？

2.队列的封装 

3. 队列的应用-击鼓传花

4. 双端队列

5.判断是否为回文

---

三. 栈结构

1.认识栈结构

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

特点：后进先出即Last in First Out（LIFO）。 

 函数调用栈

2. 封装栈结构 

class Stack {#items = []push(data) {this.#items.push(data)}pop() {return this.#items.pop()}peek() {return this.#items[this.#items.length - 1]}isEmpty() {return this.#items.length === 0}size() {return this.#items.length}clear() {this.#items = []}toString() {return this.#items.join("")}
}

3. 应用

商数是一个整数除法的运算结果，表示一个数被另一个数除后所得的整数部分。例如，当12被3除时，商数为4。余数是一个整数除法的运算结果，表示一个数被另一个数除后所得的余数。例如，当12被3除时，余数为0。

3-1 十进制转二进制

function convert(decNumber) {let remStack = new Stack()let number = decNumberlet remlet string = ""while (number > 0) {rem = number % 2remStack.push(rem)// 向下取整number = Math.floor(number / 2)}while (!remStack.isEmpty()) {string += remStack.pop()}return string
}
console.log(convert(50));

3-2 进制转换法

function convert(decNumber, base) {let remStack = new Stack()let number = decNumberlet remlet string = ""let baseStr = "0123456789ABCDEF"while (number > 0) {rem = number % baseremStack.push(rem)number = Math.floor(number / base)}while (!remStack.isEmpty()) {string += baseStr[remStack.pop()]}return string
}
console.log(convert(500, 16));

四. 队列

1.队列是什么？

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

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

2.队列的封装 

class Queue {#items = {}#count = 0//记录队列尾#lowCount = 0 //记录队列头 enqueue(data) {this.#items[this.#count] = datathis.#count++}dequeue() {if (this.isEmpty()) {return undefined}let res = this.#items[this.#lowCount]delete this.#items[this.#lowCount]this.#lowCount++return res}isEmpty() {return this.size() === 0}size() {return this.#count - this.#lowCount}clear() {this.#items = {}this.#count = 0;this.#lowCount = 0}front() {return this.#items[this.#lowCount]}toString() {let str = ""for (let i = this.#lowCount; i < this.#count; i++) {str += `${this.#items[i]} `}return str}
}

3. 队列的应用-击鼓传花

1. 击鼓传花的故事情境：类似于一个朋友圈或班级中的游戏，一群朋友或同学围成一个圆圈，开始传递一朵花。当音乐开始时，花会从一个人传递到另一个人，当音乐停止时，持有花的人将被淘汰。这个过程会不断重复，直到只剩下最后一个人。

2. 实现思路：使用队列数据结构来模拟人围成的圆圈，将人按顺序排列，然后通过不断循环传递花的方式来模拟击鼓传花的过程。当音乐停止时，从队列或链表中移除当前持有花的人，并将花传递给下一个人，然后继续播放音乐，直到最后只剩下一个人。

function game(list, num) {// 1. 创建一个队列结构let queue = new Queue()// 2.将所有人依次加入到队列中for (let i = 0; i < list.length; i++) {queue.enqueue(list[i])}while (queue.size() > 1) {// 3.开始数数，不是num的时候，重新加入到队列的末尾for (let i = 0; i < num; i++) {queue.enqueue(queue.dequeue())}//4.删除队列头console.log(queue.dequeue(), "淘汰了")}// 5.获胜者return {winner: queue.dequeue()}
}let winner = game(["张三", "李四", "王五", "丽萨", "韩梅梅"], 7)
console.log(winner);

4. 双端队列

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}// 从对列头添加addFront(data) {// 如果为空if (this.isEmpty()) {this.addBack(data)} else {// 代表如果删除过元素if (this.#lowCount > 0) {this.#lowCount --this.#items[this.#lowCount] = data} else {// 没有删除过元素 lowCount===0for (let i = this.#count; i > 0; i--) {// 假设队列中有一个元素{0:1}; this.#count=1; 下面这步骤:1(undefined) = {0:1} this.#items[i] = this.#items[i - 1]}// 赋值后 {0:1,1:1} 所有数据往前挪动一位 队列头插入this.#items[0] = data// 长度增长this.#count++}}}// 查找对头元素peekFront() {return this.#items[this.#lowCount]}// 从队尾加入addBack(data) {this.#items[this.#count] = datathis.#count++}// 从对尾删除removeBack() {if (this.isEmpty()) {return undefined}this.#count--let res = this.#items[this.#count]delete this.#items[this.#count]return res}// 查找队尾元素peekBack() {return this.#items[this.#count - 1]}isEmpty() {return this.size() === 0}size() {return this.#count - this.#lowCount}clear() {this.#items = {}this.#count = 0this.#lowCount = 0}toString() {let str = ""for (let i = this.#lowCount; i < this.#count; i++) {str += `${this.#items[i]} `}return str}
}

5.判断是否为回文

function test(params) {const lowStr = params.toLocaleLowerCase().split(' ').join('')let dequeue = new DeQueue()for (let index = 0; index < lowStr.length; index++) {dequeue.addBack(lowStr[index])}let isEqual = truewhile (dequeue.size() > 1) {if (dequeue.removeFront() != dequeue.removeBack()) {isEqual = falsebreak;}}return isEqual
}