数据结构 —— 队列和优先队列的实现_Java

队列

队列：允许在队头删除元素，队尾添加元素。队列遵循先进先出原则。它与栈的不同点就在于栈只能在栈顶操作元素，而队列是在队列的两头操作元素，一头添加一头删除。
队列在日常生活中也非常常见，就好比我们排队取火车票，当然是先来的先取，后来的在后面排队，前面的人取完了就走了，后面的人接着。取完走的人就是队头删除元素，后来加入队列排队的人就是队尾添加元素。

今天实现封装队列的函数，同样是基于数组的封装。

// 队列 ：先进先出 FIFO
// 基于数组实现
function Queue() {
    this.item = [];
    Queue.prototype.enterQueue = function (ele) {
        return this.item.push(ele);
    }

    // 2.2 出队列
    Queue.prototype.outQueue = function () {
        // 返回队列第一个元素
        return this.item.shift();
    }
    // 2.3 查看队列顶部元素
    Queue.prototype.topQueue = function () {
        return this.item[0];
    }
    // 2.4 判断队列是否为空
    Queue.prototype.isEmpty = function () {
        return this.item.length == 0;
    }
    // 2.5 查看队列中的元素
    Queue.prototype.showAll = function () {
        return this.item.join(" ");
    }
    // 2.6 查看栈中的元素个数
    Queue.prototype.size = function () {
        return this.item.length;
    }
}

控制台测试一下：
在这里插入图片描述

队列 — 击鼓传花

击鼓传花：有n个同学，按照顺时针站位，从第一位同学开始，听到鼓声开始传递花，鼓声停下时，拿到花的同学出局，出局的同学把花给他的下一位同学并从此开始，依次类推，直到剩下最后一位同学即获胜。
修改后的版本：给一个数组和一个数字，原理同击鼓传花的游戏，这里是从第一位开始数数字，数到给定的数字的人出局，从出局人下一个开始，以此类推，直到剩下最后一个同学获胜。同时返回该同学的位置。
文字可能有点晦涩，这是我自己的描述。
用代码实现，看一下：

        // 问题描述：
        // 一组人，按顺序数数字，数到给定的那个数的人退出，后面的人接着从头开始数，再次数到规定数的人退出
        // 依次类推，直到最后留下的那个人胜出，同时求出胜出的人的索引值

        function passGame(personList, num) {
            let queue = new Queue();
            // 把数据放到队列中
            for (let i = 0; i < personList.length; i++) {
                queue.enterQueue(personList[i]);
            }

            // 开始数数
            // 到num删除，不到num则放到队列的最后 eg:num=3
            while (queue.size() > 1) {
                // 把num-1个元素依次放到队列的后面  前两个
                for (let i = 0; i < num - 1; i++) {
                    // 先删除没有数到规定数字的元素，在把删除的元素重新加入到队列的后面
                    queue.enterQueue(queue.outQueue());
                }
                // 删除数到num这个数对应的元素
                // 此时数到num这个数的元素 刚好在队列顶部队头的位置 直接出队列即可
                var delName = queue.outQueue();
            }
            console.log(queue); // 剩余的元素
            console.log(personList.indexOf(queue.topQueue())); // 元素对应的索引
            return queue.topQueue() + ': ' + personList.indexOf(queue.topQueue());

        }
        let game = passGame(['a', 'b', 'c', 'd', 'e', 'f'], 6);
        console.log(game);

分析过程：
第一次数到数字6 —— f；f出局，删除。从a开始
第二次数到数字6 —— a；a出局，删除，从b开始
第三次数到数字6 —— c；c出局，删除，从d开始
第四次数到数字6 —— b；b出局，删除，从d开始
第五次数到数字6 —— e；e出局，删除，从d开始，此时只剩一个元素e，即e获胜。
在这里插入图片描述

优先队列

优先队列的意思：就是在添加元素时，有优先级的问题，优先级越高插入的元素越靠前。
联系现实生活，头等舱和商务舱优先登机，经济舱最后。
在封装时，主要是对进队列方法进行改良，需要一个内部函数，来记录元素和元素对应的优先级，在添加的时候通过判断优先级，来插入到指定的位置。

// 优先队列排序
function priorityQueue() {
    // 内部类
    // 给一个数，同时给一个优先级，数组越小优先级越高，插入时越靠前
    function queueElement(element, priority) {
        this.element = element;
        this.priority = priority;
    }
    this.item = [];

    priorityQueue.prototype.enterQueue = function (element, priority) {
        let que = new queueElement(element, priority);
        let flag = false; // 默认没有数据
        // 原始数据中有数据时，循环判断优先级
        for (let i = 0; i < this.item.length; i++) {
            // 如果当前插入的数据的优先级大，插入到前面
            if (que.priority < this.item[i].priority) {
                this.item.splice(i, 0, que);
                flag = true; // 插入时，元数据有数据存在
                break;
            }
        }
        // 数据中没有数据时，之间放入队列
        if (!flag) {
            this.item.push(que);
        }
    }

    // 2.2 出队列
    priorityQueue.prototype.outQueue = function () {
        // 返回队列第一个元素
        return this.item.shift();
    }
    // 2.3 查看队列顶部元素
    priorityQueue.prototype.topQueue = function () {
        return this.item[0];
    }
    // 2.4 判断队列是否为空
    priorityQueue.prototype.isEmpty = function () {
        return this.item.length == 0;
    }
    // 2.5 查看队列中的元素
    priorityQueue.prototype.showAll = function () {
        return this.item.forEach(ele => {
            console.log(ele.element + ': ' + ele.priority);
        });
    }
    // 2.6 查看栈中的元素个数
    priorityQueue.prototype.size = function () {
        return this.item.length;
    }
}