隊(duì)列 （常用數(shù)據(jù)結(jié)構(gòu)之一）

隊(duì)列是一種特殊的線(xiàn)性表吴菠，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作者填，而在表的后端（rear）進(jìn)行插入操作，和棧一樣做葵，隊(duì)列是一種操作受限制的線(xiàn)性表占哟。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭。隊(duì)列中沒(méi)有元素時(shí)榨乎，稱(chēng)為空隊(duì)列怎燥。

隊(duì)列的數(shù)據(jù)元素又稱(chēng)為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱(chēng)為入隊(duì)蜜暑，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱(chēng)為出隊(duì)铐姚。因?yàn)殛?duì)列只允許在一端插入，在另一端刪除肛捍，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除谦屑，故隊(duì)列又稱(chēng)為先進(jìn)先出（FIFO—first in first out）線(xiàn)性表

題目：622. 設(shè)計(jì)循環(huán)隊(duì)列

思路：用數(shù)組實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)，當(dāng)隊(duì)列全滿(mǎn)的時(shí)候篇梭，把尾指針指向隊(duì)首

export default class MyCircularQueue {
    constructor(k) {
        // 用來(lái)保存數(shù)據(jù)長(zhǎng)度為k的數(shù)據(jù)結(jié)構(gòu)
        this.list = new Array(k);
        // 隊(duì)首指針
        this.front = 0;
        // 隊(duì)尾指針
        this.rear = 0;
        // 隊(duì)列長(zhǎng)度
        this.max = k;
    }
    enQueue(num) {
        if (this.isFull()) {
            return false;
        } else {
            this.list[this.rear] = num;
            this.rear = (this.rear + 1) % this.max;
            return true;
        }
    }

    deQueue() {
        let v = this.list[this.front];
        this.list[this.front] = '';
        this.front = (this.front + 1) % this.max;
        return v;
    }

    isEmpty() {
        return this.front === this.rear && !this.list[this.front];
    }

    isFull() {
        return this.front === this.rear && !!this.list[this.front];
    }

    Front() {
        return this.list[this.front];
    }

    Rear() {
        let rear = this.rear - 1;
        return this.list[rear < 0 ? this.max - 1 : rear];
    }
}

題目： 621. 任務(wù)調(diào)度器

• 先按次數(shù)分類(lèi)任務(wù)
• 然后按次數(shù)從大到小找到n+1個(gè)任務(wù)氢橙，循環(huán)做這步，直到任務(wù)找完

function leastInterval(tasks, n) {
    let q = '';
    let Q = tasks.reduce((Q, item) => {
        if (Q[item]) {
            Q[item]++;
        } else {
            Q[item] = 1;
        }
        return Q;
    }, {});

    while (1) {
        // 獲取不同的任務(wù)列表
        let keys = Object.keys(Q);
        // 如果已經(jīng)沒(méi)有任務(wù)恬偷，就退出循環(huán)處理
        if (!keys[0]) {
            break;
        }

        // 處理一組數(shù)據(jù)
        let tmp = [];
        for (let i = 0; i <= n; i++) {
            let max = 0;
            let key;
            let pos;

            // 從所有的任務(wù)中找到未處理數(shù)最大的優(yōu)先安排
            keys.forEach((item, idx) => {
                if (Q[item] > max) {
                    max = Q[item];
                    key = item;
                    pos = idx;
                }
            })

            // 找到可以就放進(jìn)tmp數(shù)組中悍手，否則跳出while循環(huán)
            if (key) {
                tmp.push(key);
                keys.splice(pos, 1);
                Q[key]--;
                if (Q[key] < 1) {
                    delete Q[key];
                }
            } else {
                break;
            }
        }
        q += tmp.join('').padEnd(n + 1, '-');
    }
    q = q.replace(/-+$/g, '');
    return q.length;
}