首页 > 其他分享 >队列结构(Queue)

队列结构(Queue)

时间:2022-10-26 14:33:30浏览次数:61  
标签:queue return 队列 items Queue enqueue length 结构

队列结构(Queue)

队列也是一种受限的线性表,他的特点是先进先出

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

image-20221026101345775

队列的常见操作:

  • enqueue(element):向队列尾部添加一个新的项;
  • dequeue():移除队列的第一(即排在队列最前面的)项,并返回被移除的元素;
  • front():返回队列中的第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息与Stack类的peek方法非常类似);
  • isEmpty():如果队列中不包含任何元素,返回true,否则返回false;
  • size():返回队列包含的元素个数,与数组的length属性类似;
  • toString():将队列中的内容,转成字符串形式;

代码封装实现

// 封装队列类
class Queue {
    constructor() {
        // 属性
        this.items = []
    }
    // 相关操作
    enqueue(el) {
        // 向队列尾部添加一个新的项
        this.items.push(el)
    }
    dequeue() {
        // 移除队列的第一 并返回被移除的元素
        return this.items.shift()
    }
    front() {
        // 返回队列中最先被添加的元素,队列不做任何变动
        return this.items[0]
    }
    isEmpty() {
        // 如果队列中不包含任何元素,返回true,否则返回false
        return this.items.length === 0
    }
    size() {
        // 返回队列包含的元素个数
        return this.items.length
    }
    toString() {
        // 将队列中的内容,转成字符串形式
        let res = ''
        for (let i = 0; i < this.items.length; i++) {
            res += this.items[i] + ''
        }
        return res
    }
}
const queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
console.log(queue);

image-20221026103148041

队列应用

击鼓传花是一个常见的面试算法题,使用队列可以非常方便的实现最终的结果

游戏规则(修改过):

  • 几个朋友一起玩一个游戏,围成一圈,开始数数,数到某个数字的人自动淘汰
  • 最后剩下的这个人会获得胜利,请问最后剩下的是原来在哪一个位置的人?

封装一个基于队列的函数:

  • 参数:所有参与人的姓名,基于的数字
  • 结果:最终剩下的那个人的姓名

代码实现

// 面试题:击鼓传花
function passGame(nameList, num) {
    // 1.创建队列结构
    const queue = new Queue()
    // 2.将所有人依次加入到队列中
    for (let i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])
    }
    // 3.开始数数字
    while (queue.size() > 1) {
        // 不是num的时候,重新加入到队列的末尾
        // 是num的时候,从队列中删除
        // num数字之前的人重新放到队列末尾
        for (let i = 0; i < num - 1; i++) {
            queue.enqueue(queue.dequeue())
        }
        // num对应的人直接删除掉
        queue.dequeue()
    }
    // 4.获取剩下的人
    return queue.front()
}
console.log(passGame([1,2,3,4,5], 2)); // 3

优先级队列

优先级队列主要考虑的问题为:

  • 每个元素不再只是一个数据,还包含数据的优先级
  • 在添加数据过程中,根据优先级放入到正确位置

优先级队列封装:

class QueueElement {
    constructor(element, priority) {
        this.element = element
        this.priority = priority
    }
}

class PriorityQueue {
    constructor() {
        // 属性
        this.items = []
    }
    enqueue(element, priority) {
        // 1.创建QueueElement对象
        let queueElement = new QueueElement(element, priority)

        // 判断队列是否为空
        if (!this.items.length) {
            this.items.push(queueElement)
        } else {
            // 判断优先级是不是最小的,如果是最小的,那么就没必要去比较了
            if (queueElement.priority >= this.items[this.items.length - 1].priority) {
                this.items.push(queueElement)
                return
            }
            // 比较优先级,插入
            for (let i = 0; i < this.items.length; i++) {
                if (queueElement.priority < this.items[i].priority) {
                    this.items.splice(i, 0, queueElement)
                    break
                }
            }
        }
    }
    // 删除优先级最高的并返回
    dequeue() {
        return this.items.shift()
    }
    // 返回优先级最高的
    front() {
        return this.items[0]
    }
    // 队列是否为空
    isEmpty() {
        return this.items.length === 0
    }
    // 队列长度
    size() {
        return this.items.length
    }
    // 返回队列的字符串形态
    toString() {
        let res = ''
        for (let i = 0; i < this.items.length; i++) {
            res += this.items[i].element + ' '
        }
        return res
    }
}

const qp = new PriorityQueue()

// enqueue
qp.enqueue('star', 10)
qp.enqueue('tom', 11)
qp.enqueue('jack', 2)
qp.enqueue('gg', 22)
console.log(qp);

image-20221026141145143

标签:queue,return,队列,items,Queue,enqueue,length,结构
From: https://www.cnblogs.com/codehaoran/p/16828272.html

相关文章