JavaScript实现 栈 和 队列

栈 和 队列

数组

• 我们知道数组是一种线性结构，并且可以在数组的任意位置插入和删除数据
• 但是有时候，我们需要实现某些功能，必须要对这种任意性加以限制
• 而栈和队列 就是比较常见的 受限的线性结构

栈 Stack

栈（stack）、是一种 受限 的线性表， 后进先出(LIFO)

• 其限制是仅允许在 表的一端 进行插入和删除运算。 这一端被称为 栈顶， 相对地，另一端称为 栈底
• LIFO(last in first out) 表示 后进入的元素，第一个弹出占空间，类似于 往手枪的弹夹里装子弹。
• 向一个栈插入新元素又称作 进栈 、 入栈或压栈 ，它是把新元素放到栈顶元素的上面，使之称为新的栈顶元素。
• 从一个栈删除元素又称作 出栈或退栈， 它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈结构面试题

选项C不是合法的出栈序列 解析：

• 选项A： 6、5进栈，5出栈，4进栈出栈，3进栈出栈，6出栈，2、1进栈，1进栈，2出栈
• 选项B： 6、5、4进栈，4出栈，5出栈，3进栈出栈，2进栈出栈，1进栈出栈，6出栈
• 选项D： 6、5、4、3、2进栈，2出栈，3出栈，4出栈，1进栈出栈，5出栈，6出栈

栈结构常见操作的实现

栈常见的操作：

1. 向栈里压入元素（push）
2. 移除栈顶元素，同时返回被移除的元素（pop）
3. 返回栈顶元素（peek）
4. 判断栈是否为空（isEmpty）
5. 返回栈中的元素个数（size）
6. 将栈结构的内容以字符形式返回（toString）

基于数组来实现栈的操作（JS代码）：

// 基于数组实现栈的操作
class Stack{
  // 栈中的属性
  items = []
  
  // 栈的相关操作
  // 1.将元素压入栈 push
  push(element){
    this.items.push(element)
  }
  // 2.从栈中取出元素  pop
  pop(){
    return this.items.pop()
  }
  // 3.查看栈顶元素
  peek(){
    return this.items[this.items.length -1]
  }
  // 4. 判断栈是否为空
  isEmpty() {
    return this.items.length === 0
  }
  // 5. 获取栈中元素的个数
  size() {
    return this.items.length
  }
  // 6. toString方法
  toString() {
    return this.items.join(" ")
  }
}

const s = new Stack()
s.push(10)
s.push(20)
s.push(30)
console.log(s);
s.pop()
console.log(s);
console.log(s.peek());
console.log(s.isEmpty());
console.log(s.size());
console.log(s.toString());

使用栈结构来实现 十进制转二进制

十进制转二进制逻辑如下图：

十进制转二进制代码：

// 将十进制转为二进制
function dec2Bin(decNumber) {
  //  1.定义栈对象
  const stack = new Stack()

  // 2.循环操作
  while (decNumber > 0) {
    // 获取余数，并且放入栈中
    stack.push(decNumber % 2)
    // 获取整除后的结果，作为一下次运行的数字
    decNumber = Math.floor(decNumber / 2)
  }

  // return stack.items.reverse().join("")  // 这样体现不出 栈的特点
  // 3.从栈中取出0和1
  let binaryString = ''
  while (!stack.isEmpty()) {
    binaryString += stack.pop()
  }
  return binaryString
}

console.log(dec2Bin(100)); // 1100100
console.log(dec2Bin(10));  // 1010
console.log(dec2Bin(1000)); // 001111101000

队列 Queue

队列（Queue），它是一种受限的线性表，先进先出（FIFO First In First Out）

• 受限之处在于它只允许在表的前端（front） 进行删除操作
• 而在表的后端（rear） 进行插入操作

队列的应用场景

打印队列：

• 有五分文档需要打印，这些文档会按照次序放入到打印队列中
• 打印机会依次从队列中取出文档，优先放入的文档，会优先被取出，并且对该文档进行打印。
• 以此类推，直到队列中不再有新的文档。

线程队列：

• 在开发中，为了让任务可以进行并行处理，通常会开启多个线程。
• 但是，我们不能让大量的线程同时运行处理任务，（占用过多的资源）
• 这个时候，如果有需要开启的线程处理任务的情况，我们就会使用线程队列。
• 线程队列会依照次序来启动线程，并且处理对应的任务。

队列的常见操作的实现

队列的常见操作：

• enqueue(element):向队列尾部添加一个（或多个）新的项。
• dequeue(): 移除队列的第一项（即排在队列最前面的那个），并返回被移除的元素。
• front(): 返回队列中第一个元素--最先被添加的，也即将是最先被移除的元素。队列不做任何变动（不移除只返回元素信息---与Stack类的peek方法类似）
• isEmpty(): 如果队列中不包含任务元素，返回true，反之
• size(): 返回队列包含的元素个数。
• toString(): 将队列中的内容，转成字符串形式。

队列常见操作的代码实现：

class Queue {
  items = []

  // 1. 将元素加入队列中
  enqueue(element) {
    this.items.push(element)
  }
  // 2. 从队列中删除前端元素
  dequeue() {
    return this.items.shift()
  }
  // 3.查看前端的元素
  front() {
    if (this.items.length === 0) return null
    return this.items[0]
  }
  // 4. 查看队列是否为空
  isEmpty() {
    return this.items.length === 0
  }
  // 5. 查看队列中的元素的个数
  size() {
    return this.items.length
  }

}

const q = new Queue()
q.enqueue('a')
q.enqueue('b')
q.enqueue('c')
q.enqueue('d')
console.log(q);
q.dequeue()
q.dequeue()
console.log(q);
console.log(q.front());
console.log(q.isEmpty());
console.log(q.size());

击鼓传花

// 击鼓传花
function passGame(nameList,num) {
  // 1. 创建一个队列结构
  const queue = new Queue()
  // 2. 将所有人依次加入到队列中
  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i])
  }
  while (queue.size() > 1) {
  // 3.开始数数字
    for (let i = 0; i < num - 1; i++) {
      // num数字之前的人重新放入到队列的末尾
      queue.enqueue(queue.dequeue())
    }
      // num对应这个人，直接从队列中删除
      queue.dequeue()
  }

  // / 4. 获取剩下的那个人
  console.log("最后剩下人数："+queue.size());
  const endName = queue.front()
  console.log('最终剩下的人是：' + endName);

  return nameList.indexOf(endName) // 返回最后剩下的下标值

}

names = ["朱元璋", "朱棣", "朱高炽", "朱瞻基", "朱祁镇"]
console.log(passGame(names, 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)

    // 2.考虑如何插入新的元素
    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('a',10)
queue.enqueue('b',20)
queue.enqueue('c',5)
queue.enqueue('d', 8)

queue.items.forEach(item => {
  console.log(item.element,item.priority);
})