目录
三. 栈结构
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. 队列的应用-击鼓传花
-
击鼓传花的故事情境:类似于一个朋友圈或班级中的游戏,一群朋友或同学围成一个圆圈,开始传递一朵花。当音乐开始时,花会从一个人传递到另一个人,当音乐停止时,持有花的人将被淘汰。这个过程会不断重复,直到只剩下最后一个人。
-
实现思路:使用队列数据结构来模拟人围成的圆圈,将人按顺序排列,然后通过不断循环传递花的方式来模拟击鼓传花的过程。当音乐停止时,从队列或链表中移除当前持有花的人,并将花传递给下一个人,然后继续播放音乐,直到最后只剩下一个人。
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
}