队列

队列是只允许在一段进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的顺序存储结构

队列头尾相接的顺序存储结构称为循环队列。

js 实现代码

class Queue {

    constructor() {
        this.data = [];
        this.rear = 0;
        this.next = 0;
    }
}

function enQueue(queue, e) {
    queue.data.push(e);
}

function deQueue(queue) {
    if (queue.data.length === 0) {
        throw new Error('队列已空');
    }
    return queue.data.shift();
}

队列的链式存储结构

js 实现代码

class QueueNode {

    constructor(data, next) {
        this.data = data;
        this.next = next;
    }
}

class Queue {

    constructor() {
        this.front = null;
        this.rear = null;
    }
}

function createQueue() {
    let queue = new Queue();
    return queue;
}

function enQueue(queue, e) {
    let newNode = new QueueNode(e);
    if (queue.front === null) {
        queue.front = newNode;
    }
    if (queue.rear === null) {
        queue.rear = newNode;
    } else {
        queue.rear.next = newNode;
        queue.rear = newNode;
    }
}

function deQueue(queue) {
    if (queue.front === null || queue.rear === null) {
        throw new Error('队列为空');
    }
    let q = queue.front;
    queue.front = q.next;
    return q.data;
}

let queue = new createQueue();

enQueue(queue, 10);
enQueue(queue, 12);
enQueue(queue, 13);
console.log(deQueue(queue));
console.log(deQueue(queue));
console.log(deQueue(queue));

在可以确定队列长度最大值的情况下，建议使用循环队列，无法预估队列的长度，则用链队列。