第 4 章 隊(duì)列

1. 隊(duì)列數(shù)據(jù)結(jié)構(gòu)

• 隊(duì)列是遵循FIFO（First In First Out忧饭，先進(jìn)先出攻谁，也稱(chēng)為先來(lái)先服務(wù)）原則的一組有序的項(xiàng)掂榔。
  隊(duì)列在尾部添加新元素禁添，并從頂部移除元素早像。最新添加的元素必須排在隊(duì)列的末尾。

2. 隊(duì)列的操作

• enqueue(element(s))：向隊(duì)列尾部添加一個(gè)（或多個(gè)）新的項(xiàng)掠归。
• dequeue() ：移除隊(duì)列的第一（即排在隊(duì)列最前面的）項(xiàng)缅叠，并返回被移除的元素。
• front() ：返回隊(duì)列中第一個(gè)元素——最先被添加虏冻，也將是最先被移除的元素肤粱。隊(duì)列不做任何變動(dòng)（不移除元素，只返回元素信息——與 Stack 類(lèi)的 peek 方法非常類(lèi)似）厨相。
• isEmpty() ：如果隊(duì)列中不包含任何元素领曼，返回 true ，否則返回 false 蛮穿。
• size() ：返回隊(duì)列包含的元素個(gè)數(shù)庶骄，與數(shù)組的 length 屬性類(lèi)似。

function Queue(){
    //這里是屬性和方法
    let items = [];
    
    //向隊(duì)列添加元素（新的項(xiàng)只能添加到隊(duì)列末尾）
    this.enqueue = function(element){
        items.push(element);
    };
 
    //從隊(duì)列移除元素
    this.dequeue = function(){
        return items.shift();  
    };
    
    //查看隊(duì)列頭元素
    this.front = function(){
        return items[0];  
    };
    
    //檢查隊(duì)列是否為空
    this.isEmpty = function(){
        return items.length==0;
    };
    
    //隊(duì)列元素個(gè)數(shù)
    this.size = function(){
        return items.length;  
    };
    
    //打印隊(duì)列元素
    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 語(yǔ)法實(shí)現(xiàn)的 Queue 類(lèi)

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();