JS数据结构|JS数据结构栈队列 JS数据结构栈队列

栈结构

栈是一种遵从先进后出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫做栈底，新元素都靠近栈顶，旧元素都靠近栈底。

栈的一些方法

push(element(s))：添加一个或几个新元素到栈顶
pop()：移除栈顶的元素，同时返回被移除的元素
peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶元素，仅仅返回它）
isEmpty()：如果栈里没有任何元素就返回true，否则返回false
clear()：移除栈里的所有元素
size()：返回栈里的元素个数。该方法和数组的length类似

创建类来表示栈并且声明这些方法

class Stack { constructor() { this.items = [] } // push添加一个新元素到栈顶 push(element) { this.items.push(element) } // 移除栈顶的元素，同时返回被移除的元素 pop() { return this.items.pop() } // peek 返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它） peek() { return this.items[this.items.length - 1] } // isEmpty 如果栈里没有任何元素就返回true，否则就返回false isEmpty() { return this.items.length === 0 } // size 返回栈里元素的个数，这个方法和数组的length属性类似 size() { return this.items.length } //clea用来移除栈里的所有的元素，把栈清空 clear() { return this.items = [] } }

使用Stack类首先需要初始化Stack类，并进行添加元素，因为此时栈内元素为空，调用isEmpty方法会返回ture

const stack = new Stack()stack.push('孙悟空') stack.push('美猴王') stack.push('猪八戒') stack.push('沙和尚')console.log(stack.items) //打印栈内有几个元素 console.log(stack.pop()) //移除栈顶元素（LIFO 先进后出，所以将沙和尚移除） console.log(stack.items) //此时执行完上一步操作后栈内元素为三个 console.log(stack.peek()) //查看栈顶元素此时为猪八戒 console.log(stack.isEmpty())//false console.log(stack.size())//3 console.log(stack.clear())//0

使用栈来解决实际问题（十进制转二进制）

// 进制转换 function dec2bin(num) { const stack = new Stack() // 不确定循环次数就用while循环，当num大于0就一直进行while循环 while (num > 0) { let remainder = num % 2 //拿到余数 num = Math.floor(num / 2) //用Math.floor向下取整 stack.push(remainder); //将取到的数压栈 } // console.log(stack.items)//将此栈内元素依次弹栈就是想要获取到的结果 let binString = "" while (!stack.isEmpty()) { binString += stack.pop() }return binString } console.log(dec2bin(100)) //1100100

队列结构

队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的向。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾

队列的一些方法

enqueue(element(s))：向队列尾部添加一个（或多个）新的项。
dequeue()：移除队列的第一项（既排在队列最前面的项）并返回被移除的元素。
peek()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与stack类的peek方法非常类似）。该方法在其他语言中也可以叫做front方法。
isEmpty()：如果队列中不包含任何元素，返回true，否则返回false
size()：返回队列包含的元素个数，与数组的length属性类似

创建类来表示队列并且声明这些方法

class Queue { constructor() { this.items = [] } enqueue(element) { this.items.push(element) } dequeue() { return this.items.shift() } peek() { if (this.items.length === 0) return null return this.items[0] } isEmpty() { return this.items.length === 0 } size() { return this.items.length } }

使用queue类

const queue = new Queue() queue.enqueue("孙悟空") queue.enqueue("猪八戒") queue.enqueue("沙和尚") queue.enqueue("小傻瓜") console.log(queue.items) console.log(queue.dequeue())//移除队列第一名孙悟空 console.log(queue.items)//此时剩下三个 console.log(queue.peek())//此时队列顶部是猪八戒

使用队列来解决实际问题击鼓传花
围成一圈，开始叔叔，数到某个数字的人自动淘汰
最后剩下的这人会获得胜利，这个人是谁

// 击鼓传花 function passGame(nameList, num) { // 创建队列 const queue = new Queue() for (let i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i])//nameList进入队列 } // 循环进入队列 while (queue.size() > 1) { for (let i = 0; i < num - 1; i++) { queue.enqueue(queue.dequeue())//数字不是3的入队列 } queue.dequeue()//数字是3的出队列，不入 }return queue.peek() } console.log(passGame(["孙悟空", "猪八戒", "沙和尚", "小傻瓜"], 3))//孙悟空

优先级队列

简单来讲就是会员插队
【JS数据结构|JS数据结构栈队列】医院急诊

class QueueElement { constructor(element, priority) { this.element = element this.priority = priority } } class PriorityQueue extends Queue { enqueue(element, priority) { // 1.创建QueueElement对象 const queueElement = new QueueElement(element, priority) // 考虑如何插入新元素 if (this.isEmpty()) { this.items.push(queueElement) } else { let added = false for (let i = 0; i < this.items.length; i++) { if (this.items[i].priority > queueElement.priority) { this.items.splice(i, 0, queueElement) added = true break } } if (!added) { this.items.push(queueElement) } } } } const queue = new PriorityQueue(); queue.enqueue("aaa", 100) queue.enqueue("bbb", 150) queue.enqueue("ccc", 120) queue.enqueue("ddd", 99) queue.items.forEach(item => { console.log(item.element, item.priority) //序号小的先输出 })