队列

作者: yuzhiyi_宇 | 来源:发表于2019-01-13 14:35 被阅读0次

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

    队列是一种先进先出的线性表,简称 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));
    

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

    相关文章

      网友评论

          本文标题:队列

          本文链接:https://www.haomeiwen.com/subject/dalcdqtx.html