关于javascript: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))// 孙悟空

优先级队列

• 简略来讲就是会员插队

• 医院急诊

  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) // 序号小的先输入
  })