学习Javascript数据结构与算法（第2版）笔记（4）

第 4 章 队列

1. 队列数据结构

• 队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。
  队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

2. 队列的操作

• enqueue(element(s))：向队列尾部添加一个（或多个）新的项。
• dequeue() ：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
• front() ：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与 Stack 类的 peek 方法非常类似）。
• isEmpty() ：如果队列中不包含任何元素，返回 true ，否则返回 false 。
• size() ：返回队列包含的元素个数，与数组的 length 属性类似。

function Queue(){
    //这里是属性和方法
    let items = [];
    
    //向队列添加元素（新的项只能添加到队列末尾）
    this.enqueue = function(element){
        items.push(element);
    };
 
    //从队列移除元素
    this.dequeue = function(){
        return items.shift();  
    };
    
    //查看队列头元素
    this.front = function(){
        return items[0];  
    };
    
    //检查队列是否为空
    this.isEmpty = function(){
        return items.length==0;
    };
    
    //队列元素个数
    this.size = function(){
        return items.length;  
    };
    
    //打印队列元素
    this.print = function(){
        conosle.log(items.toString());
    };
}

let queue = new Queue();
console.lg(queue.isEmpty());//true
queue.enqueue('Apple');
queue.enqueue('Orange');
queue.enqueue('Banana');
queue.print();
console.log(queue.size());//3
console.log(queue.isEmpty());//false
queue.dequeue();
queue.dequeue();
queue.print();

3. 用 ECMAScript 6 语法实现的 Queue 类

let Queue2 = (function(){
    const items = new WeakMap();
    
    class Queue2{
        constructor(){
            items.set(this,[]);
        }
        enqueue(element){
            let q = items.get(this);
            q.push(element);
        }
        dequeue(){
            let q = items.get(this);
            let r = q.shift();
            return r;
        }
        //其他方法
    }
    return Queue2;
})();

function PriorityQueue(){
    let items = [];
    function QueueElement(element,priority){
        this.element = element;
        this.priority = priority;
    }
    this.enqueue = function(element,priority){
        let queueElement = new QueueElement(element,priority);
        
        let added = false;
        for(let i=0;i<items.length;i++){
            if(queueElement.priority < items[i].priority){
                items.splice(i,0,queueElement);
                added = true;
                break;
            }
        }
        if(!added){
            items.push(queueElement);
        }
    };
    this.print = function(){
        for(let i=0;i<items.length;i++){
        console.log(`${items[i].element} - ${items[i].priority}`);
        }
    };
    //
}

let priorityQueue = new PriorityQueue();
priorityQueue.enqueue("apple", 2);
priorityQueue.enqueue("orange", 1);
priorityQueue.enqueue("banana", 1);
priorityQueue.print();