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

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

隊列的數(shù)據(jù)元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一端插入，在另一端刪除，所以只有最早進(jìn)入隊列的元素才能最先從隊列中刪除，故隊列又稱為先進(jìn)先出（FIFO—first in first out）線性表

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

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

export default class MyCircularQueue {
    constructor(k) {
        // 用來保存數(shù)據(jù)長度為k的數(shù)據(jù)結(jié)構(gòu)
        this.list = new Array(k);
        // 隊首指針
        this.front = 0;
        // 隊尾指針
        this.rear = 0;
        // 隊列長度
        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ù)分類任務(wù)
• 然后按次數(shù)從大到小找到n+1個任務(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)沒有任務(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;
}