国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JS 隊列-優先隊列、循環隊列

ctriptech / 3100人閱讀

摘要:隊列是遵行先進先出原則的一組有序的項。優先隊列是默認隊列的變種,它的元素的添加和移除是基于優先級的。如此循環,直至隊列的長度等于,返回勝者行。同時,還掌握了很著名的優先隊列循環隊列這兩種結構。

《學習JavaScript數據結構與算法》讀書筆記。

隊列是遵行FIFO(First In First Out, 先進先出)原則的一組有序的項。隊列再尾部添加新元素,并從頂部移除元素。

在現實中,最常見的隊列的例子就是排隊。

1.創建隊列

現在,我們來創建一個類來表示一個隊列。先從最基本的聲明類開始:

function Queue(){
    // 這里是屬性和方法
}

首先,需要一個用戶存儲隊列中元素的數據結構,我們可以使用數組。

var items = [];

接下來,聲明一些隊列可用的方法:

enqueue(element(s)):進隊,向隊列尾部添加一個(或多個)新項。

dequeue():移除隊列的第一項,并返回被移除的元素。

front():返回隊列中第一個元素-最先被添加,也會是最先被移除的元素。(只返回,不移除)。

isEmpty():如果隊列為空,返回true,否則,返回false。

size():返回隊列的長度。

首先,我們來實現enqueue的方法,這個方法負責向隊列中添加新元素。只能是添加到隊列的尾部。

    this.enqueue = function(element) {
        items.push(element);
    }

接下來要實現的是dequeue方法,這個方法負責從隊列移除項。由于隊列遵循的是先進先出原則,所以最先移除的就是最先添加的,元素是排在數組的第一位。

    this.dequeue = function() {
        return items.shift();
    }

只有enqueue方法和dequeue方法可以添加和移除元素,這樣就確保了Queue類遵循先進先出原則。
現在來為我們的類實現一些額外的輔助方法:

    // front():返回隊列中第一個元素
    this.front = function() {
        return items[0];
    }
    
    // isEmpty():如果隊列為空,返回true,否則,返回false
    this.isEmpty = function() {
        return items.length === 0;
    }
    
    // size():返回隊列的長度
    this.size = function() {
        return items.length;
    }

完成,我們的Queue類實現好了,現在來看看Queue完整的實現是怎么樣的:

function Queue() {
    var 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.clear = function() {
        items = [];
    }
    
    this.size = function() {
        return items.length;
    }
    
    this.print = function() {
        console.log(items.toString());
    }
}

2.使用Queue類

var queue = new Queue();
console.log(queue.isEmpty()); // 輸出 true
queue.enqueue("John");        // 添加元素 John
queue.enqueue("Jam");         // 添加元素 Jam
queue.enqueue("Camila");      // 添加元素 Camila
queue.print();
console.log(queue.size);      // 輸出 3
console.log(queue.isEmpty);   // 輸出 false
queue.dequeue();              // 移除元素
queue.dequeue();            
queue.print();

運行上面的代碼,我們可以看出,我們已經實現了隊列,遵循了先入先出原則。

3.優先隊列

上面我們已經實現了一個隊列,現在,逐步深入,我們來看看什么是優先隊列。

優先隊列是默認隊列的變種,它的元素的添加和移除是基于優先級的。一個現實的例子就是醫院的(急診科)候診室。醫生會優先處理病情比較嚴重的患者。

實現一個優先隊列,有兩種選擇:設置優先級,然后在正確的位置添加元素;或者用默認入列操作添加元素,任何按照優先級移除它們。下面,我們將會在正確的位置添加元素,任何用默認你的出列操作。

    function PriorityQueue() {
        var items = [];
        
        // {1}
        function QueueElement(element, priority) {
            this.element = element;
            this.priority = priority;
        }
        
        this.enqueue = function(element, priority) {
            var queueElement = new QueueElement(element, priority);
            
            if(this.isEmpty()) {
                items.push(queueElement);  // {2}
            } else {
                var added = false;
                for(var i = 0; i < items.length; i++) {
                    if(queueElement.priority < items.[i].priority) {
                        items.splice(i, 0, queueElement);    // {3}
                        added = true;
                        break;
                    }
                }
                if(!added) {    // {4}
                    items.push(queueElement);
                }
            }
        }
        
        // 其他方法與默認隊列一樣
    }

我們創建了一個特殊的元素(行{1}),這個元素包含了要添加到隊列的元素及其優先級。

如果隊列為空,則直接將元素入列(行{2})。否則,就要進行比較。當找到一個比要添加的元素的priority值更大(優先級更低)時,就將元素插入到它之前(行{3})。

如果要添加的元素的priority指大于任何已有的元素,則直接將其添加到隊列的末尾(行{4})。

var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jam", 1);
priorityQueue.enqueue("Sam", 1);
priorityQueue.print();

至此,我們已經實現了優先隊列,下面,將再介紹一種隊列——循環隊列

4.循環隊列——擊鼓傳花

循環隊列是默認隊列的另一種修改版,什么是循環隊列呢?舉個現實中的例子,記得小時候玩過的傳花游戲嗎?
幾個孩子圍成一圈,開始擊鼓了,孩子就把花盡快地傳遞給旁邊的人,某一時刻鼓聲停止了,傳花也就停止了,這個時候花落在誰手上,誰就被淘汰。鼓聲響起,繼續傳花,如此循環,直至只剩下一個孩子,即勝者。

function hotPotato(namelist, num) {
    var queue = new Queue();
    for (var i = 0; i < namelist.length; i++) {     // {1}
        queue.enqueue(namelist[i]);
    }
    var eliminated = "";
    while (queue.size() > 1) {                 // {2}
        for (var i = 0; i < num; i++) {
            queue.enqueue(queue.dequeue());    // {3}
        }
        eliminated = queue.dequeue();    // {4}
        console.log(eliminated + "在擊鼓傳花游戲中被淘汰");
    }
    return queue.dequeue();    // {5}
}
var names = ["john", "jack", "camila", "ingrid", "carl"];
var winner = hotPotato(names, 7);
console.log("勝利者: " + winner);      //john

首先,先把名單添加到隊列里面(行{1})。

當隊列的的長度大于1的時候(行{2}),根據指定的一個數字(num)迭代隊列,將隊列的頭一個移除并將其添加到隊尾(行{3})。

一旦傳遞次數達到給定的數字,則刪除此時的隊列第一項(行{4}),即拿著花的那個人,他將被淘汰。

如此循環,直至隊列的長度等于1,返回勝者(行{5})。

5.小結

通過這篇文章的介紹,我們學會了如何用數組構造出隊列的類。同時,還掌握了很著名的優先隊列、循環隊列這兩種結構。

附:
JavaScript數據結構和算法系列:
JS 棧

JavaScript設計模式系列:
JavaScript設計模式之策略模式
JavaScript設計模式之發布-訂閱模式(觀察者模式)-Part1

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/88037.html

相關文章

  • js 事件循環中的job queue和message queue

    摘要:等到主任務隊列執行完成時此時已打印,執行存在隊列中的函數,任務隊列中引入了任務隊列來執行的回調函數。在這個的回調函數中使用創建一個的任務,同時在中調用函數創建一個任務。 本文討論的事件循環均是基于瀏覽器環境上的,類似nodejs環境下的事件循環與此并不相同。 讀者首先要對js單線程事件循環機制以及Promise有基本理解;如果這兩個概念不是很清楚,建議先閱讀下面兩篇文章: THE JA...

    songze 評論0 收藏0
  • JS數據結構學習:隊列

    隊列的定義 隊列是遵循先進先出原則的一組有序的項,與棧的不同的是,棧不管是入棧還是出棧操作都是在棧頂操作,隊列則是在隊尾添加元素,隊頂移除,用一個圖來表示大概是這樣事的:showImg(https://segmentfault.com/img/remote/1460000018133039?w=584&h=294);用一個更形象的例子就是:排隊服務,總是先排隊的人會先接受服務,當然不考慮插隊的情況...

    OpenDigg 評論0 收藏0
  • 數據結構知否知否系列之 — 隊列

    摘要:初始化隊列初始化一個存儲隊列中元素的數據結構,如果未傳入默認賦值空數組,傳入需先校驗類型是否正確。頭等艙和商務艙乘客的優先級要高于經濟艙乘客。在有些國家,老年人和孕婦或帶小孩的婦女登機時也享有高于其他乘客的優先級。 有一天,當回顧自己走過的路時,你會發現這些奮斗不息的歲月,才是最美好的人生。——弗洛伊德 隊列,英文 First In First Out 簡稱 FIFO,遵從先進先出的原...

    galois 評論0 收藏0
  • [ JavaScript ] 數據結構與算法 —— 隊列

    摘要:而且目前大部分編程語言的高級應用都會用到數據結構與算法以及設計模式。隊列在尾部添加新元素,并從頂部移除元素。最新添加的元素必須排在隊列的末尾。 前言 JavaScript是當下最流行的編程語言之一,它可以做很多事情: 數據可視化(D3.js,Three.js,Chart.js); 移動端應用(React Native,Weex,AppCan,Flutter,Hybrid App,小程...

    Yi_Zhi_Yu 評論0 收藏0
  • 我對JS隊列的學習

    摘要:我對隊列的學習什么是隊列隊列是遵循先進先出原則的一組有序的項。最新添加的元素必須排在隊列的末尾。隊列的學習隊列的操作其實是和棧是差不多的,但是隊列只允許新數據在后端進行添加。這里是最小優先隊列,優先值較小的元素被放置在隊列最前面。 我對JS隊列的學習 什么是隊列 隊列是遵循FIFO(先進先出)原則的一組有序的項。隊列在尾部添加新元素,并從頂部移除元素。最新添加的元素必須排在隊列的末尾。...

    Cristic 評論0 收藏0

發表評論

0條評論

ctriptech

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<