[ JavaScript ] 數據結構與算法 —— 隊列

Yi_Zhi_Yu 發布于2019-08-23 15:05 / 2323人閱讀

摘要：而且目前大部分編程語言的高級應用都會用到數據結構與算法以及設計模式。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的末尾。

前言

JavaScript是當下最流行的編程語言之一，它可以做很多事情：

數據可視化（D3.js，Three.js，Chart.js）;

移動端應用(React Native,Weex,AppCan,Flutter,Hybrid App,小程序);

服務端(Express.js,Koa2)；

桌面應用(Electron,nw.js);

游戲,VR，AR(LayaAir,Egret,Turbulenz,PlayCanvas);

等等。。。

而且目前大部分編程語言的高級應用都會用到數據結構與算法以及設計模式。

本篇主要有三部分

什么是隊列

隊列的實現

隊列的變種

什么是隊列 較官方解釋

隊列是遵循FIFO（First In First Out，先進先出，也稱為先來先服務）原則的一組有序的項。
隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的末尾。

注：出隊入隊是自己加的，不知道是不是這么叫

個人理解

我看有很多文檔都是說隊列就像買什么東西排隊，我認為這個比喻用在標準隊列上不恰當。

我覺得標準隊列像是一段管道，每次都只能放一個球進去，上邊只用來放球（入隊），由于地球引力，球會從下邊的口出去（出隊）。

隊列：這段可以放球的管道就是隊列
元素：管道里的球
隊首：在當前管道里的球最早放進去的那個球的位置，同時也是第一個掉出去的球
隊尾：在當前管道里的球最后放進去的那個球的位置，同時也是最后一個掉出去的球

隊列的實現

添加隊列成員

刪除隊列成員

返回隊首的成員

隊列是否為空

清空隊列

隊列長度

返回字符串形式的隊列成員

class Queue {
    constructor() {
        this.count = 0; // 整個隊列下一成員的位置
        this.lowestCount = 0; // 在第一位的成員位置
        this.items = {}; // 用來存放的隊列
    }

    enqueue(element) { 
        // 添加隊列成員 進入隊列
    }

    dequeue() { 
        // 刪除隊列成員 離開隊列
    }

    peek() { 
        // 返回隊首的成員
    }

    isEmpty() { 
        // 判斷隊列是否為空
    }

    clear() { 
        // 將所有的數據初始化
    }

    size() { 
        // 隊列長度 
    }

    toString() {
        // 返回字符串形式的隊列成員
    }
}

添加隊列成員

enqueue(element) {
    this.items[this.count] = element; // 將元素放入隊列
    this.count++; // 將計數器加一
}

刪除隊列成員

dequeue() {
    if (this.isEmpty()) { // 如果是空 
        return undefined; // 返回未定義 undefined
    }
    const result = this.items[this.lowestCount]; // 將隊首的成員保存下
    delete this.items[this.lowestCount]; // 將隊首的成員刪除掉 刪除對象屬性
    this.lowestCount++; // 將隊列提前一位 指向隊首的指針后移一位
    return result; // 返回被刪除的成員
}

返回隊首的成員

peek() {
    if (this.isEmpty()) { // 非空才能繼續處理
        return undefined;
    }
    return this.items[this.lowestCount];
}

隊列是否為空

isEmpty() { // 判斷長度是不是 0 
    return this.size() === 0;
}

清空隊列

clear() {
    this.count = 0; // 恢復初始值 
    this.lowestCount = 0;  // 恢復初始值
    this.items = {};  // 重新賦值空對象
}

隊列長度

size() { // 隊列長度 等于 整個隊列下一成員的位置 減去 在第一位的成員位置
    return this.count - this.lowestCount;
}

返回字符串形式的隊列成員

toString() {
    if (this.isEmpty()) {
        return "";
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
        objString = `${objString},${this.items[i]}`;
    }
    return objString;
}

隊列的變種

優先隊列

類似去醫院看病，急診，會優先一般的門診

循環隊列

類似搶凳子游戲，隊列首位相連

優先隊列

在添加成員時會判斷優先級，

class QueueElement (element, priority){ // 隊列成員類
    this.element = element; // 存放成員
    this.priority = priority;  // 存放優先級 
} 

enqueue(element, priority){ 
    let queueElement = new QueueElement(element, priority);  // 添加成員
    let added = false;  // 是否已添加到隊列
    for (let i = 0; i < this.size(); i++){  // 遍歷隊列
        if (queueElement.priority < items[i].priority){ // 尋找優先級低的成員，并插入到其之前
        // splice start
            for(let j = this.size(); j > i; j--){
                items[j] = items[j-1];
            }
            items[i] = queueElement;
        // splice end
            added = true;  // 標識符置為真，表示已經添加
            break; // 跳出循環
        } 
    } 
    if (!added){  // 如果沒有找到優先級比新添加的成員低的，那么將其添加到隊尾
        items.push(queueElement);
    } 
};

循環隊列

在操作時每刪除一個隊列成員就將刪除的這個隊列成員重新添加到隊列中

for (let i = 0; i < number; i++){ 
    queue.enqueue(queue.dequeue());
}

云服務器 GPU云服務器算法與數據結構數據結構與算法數據結構與算法教程數據結構與算法答案

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

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

學習JavaScript數據結構與算法（一）：棧與隊列

摘要：之數組操作接下來就是數據結構的第一部分，棧。以字符串顯示棧中所有內容方法的實現說明需要往棧中添加新元素，元素位置在隊列的末尾。的前端樂園原文鏈接寒假前端學習學習數據結構與算法，棧與隊列本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第...

Flink_China 2019-08-19 17:23 評論0 收藏0
JavaScript的數據結構與算法（二） —— 隊列

摘要：簡介隊列遵循的是先進先出的原則的一組有序的項。隊列從尾部添加新元素，并從頂部移除元素，最新添加的元素必須排列在隊列的末尾。它的想法來自于生活中排隊的策略。隊列不做任何變動。簡介隊列遵循的是FIFO（先進先出）的原則的一組有序的項。隊列從尾部添加新元素，并從頂部移除元素，最新添加的元素必須排列在隊列的末尾。它的想法來自于生活中排隊的策略。顧客在付款結賬的時候，按照到來的先后順序排...

xingqiba 2019-08-21 17:12 評論0 收藏0
JavaScript數據結構與算法——隊列

摘要：隊列數據結構隊列遵循先進先出，也稱先來先服務原則的一組有序的項。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的的末尾。隊列和棧非常類似，但是使用了不同的原則，而非后進先出，是先進先出。 1.隊列數據結構隊列遵循FIFO（先進先出，也稱先來先服務）原則的一組有序的項。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的的末尾。隊列示意圖如下： s...

silenceboy 2019-08-23 15:12 評論0 收藏0
《JavaScript數據結構與算法》筆記——第4章隊列

摘要：隊列遵循原則的一組有序的項向隊列尾部添加一個項移除隊列的第一項返回隊列中第一項，對隊列本身不做修改判斷隊列是否為空返回隊列包含的元素個數優先隊列根據優先級添加項最小優先隊列移除隊列的第一項返回隊列中第一項，對隊列本身不做修改判斷隊列是否隊列遵循FIFO（First In First Out）原則的一組有序的項 let Queue = (function () { let it...

callmewhy 2019-08-26 13:28 評論0 收藏0
學習數據結構與算法之棧與隊列

摘要：于是翻出了機房里的這本學習數據結構與算法開始學習程序員的基礎知識。這本書用了我最熟悉的來實現各種數據結構和算法，而且書很薄，可以說是一本不錯的入門教程。隊列在頭部刪除元素，尾部添加元素。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算...

pingan8787 2019-08-20 18:37 評論0 收藏0