JS數據結構與演算法-隊列結構

来源:https://www.cnblogs.com/atrox493/archive/2022/11/07/16864951.html
-Advertisement-
Play Games

隊列結構 一.認識隊列 受限的線性結構: 我們已經學習了一種受限的線性結構:棧結構. 並且已經知道這種受限的數據結構對於解決某些特定問題,會有特別的 效果. 下麵,我們再來學習另外一個受限的數據結構:隊列. 隊列(Queue),它是一種受限的線性表,先進先出(FIFO First ln First ...


隊列結構

一.認識隊列

  • 受限的線性結構:
    • 我們已經學習了一種受限的線性結構:棧結構.
    • 並且已經知道這種受限的數據結構對於解決某些特定問題,會有特別的
      效果.
    • 下麵,我們再來學習另外一個受限的數據結構:隊列.
  • 隊列(Queue),它是一種受限的線性表,先進先出(FIFO First ln First Out)
    • 受限之處在於它只允許在表的前端( front )進行刪除操作
    • 而在表的後端(rear)進行插入操作
  • 生活中類似的隊列結構
    • 生活中類似隊列的場景就是非常多了
    • 比如在電影院,商場,甚至是廁所排隊.
    • 優先排隊的人,優先處理.(買票,結賬, WC)

二.隊列的應用

  • 列印隊列:
    • 有五份文檔需要列印,這些文檔會按照次序放入到列印隊列中.
    • 印表機會依次從隊列中取出文檔,優先放入的文檔,優先被取出,並且對該文檔進行列印.
    • 以此類推,直到隊列中不再有新的文檔.
  • 線程隊列:
    • 在開發中,為了讓任務可以並行處理,通常會開啟多個線程.
    • 但是,我們不能讓大量的線程同時運行處理任務.(占用過多的資源)
    • 這個時候,如果有需要開啟線程處理任務的情況,我們就會使用線程隊列.
    • 線程隊列會依照次序來啟動線程,並且處理對應的任務.
  • 隊列如何實現呢?
    • 我們一起來研究一下隊列的實現.

三.隊列類的創建

  • 隊列的實現和棧一樣,有兩種方案:
    • 基於數組實現
    • 基於鏈表實現
function Queue() {
    //屬性
    this.items = []
}

四.隊列的常見操作

  • 隊列有哪些常見的操作呢?
    • enqueue(element):向隊列尾部添加一個(或多個)新的項。
    • dequeue()∶移除隊列的第一(即排在隊列最前面的)項,並返回被移除的元素。
    • front():返回隊列中第一個元素——最先被添加,也將是最先被移除的元素。隊列不做任何變動(不移除元素,只返回元素信息——與Stack類的peek方法非常類似)。
    • isEmpty):如果隊列中不包含任何元素,返回true,否則返回false。
    • size():返回隊列包含的元素個數,與數組的length屬性類似。
    • toString():將隊列中的內容,轉成字元串形式
  • 現在,,我們來實現這些方法.
    • 其實很棧中方法的實現非常相似.因為我們的隊列也是基於數組的
//1.將元素加入到隊列中
    Queue.prototype.enqueue = function (element) {
        this.items.push(element)
    }

    //2.從隊列中刪除前端元素
    Queue.prototype.dequeue = function () {
        return this.items.shift()
    }

    //3.查看前端元素
    Queue.prototype.front = function () {
        return this.items[0]
    }

    //4.查看隊列是否為空
    Queue.prototype.isEmpty = function () {
        return this.items.length === 0
    }

    //5.查看隊列中元素的個數
    Queue.prototype.size = function () {
        return this.items.length
    }

    //6.toString方法
    Queue.prototype.toString = function () {
        let resultString = ''
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i] + ''
        }
        return resultString
    }

五.擊鼓傳花

  • 擊鼓傳花是一個常見的面試演算法題.使用隊列可以非常方便的實現最終的結果.

  • 原游戲規則:

    • 班級中玩一個游戲。所有學生圍成一圈,從某位同學手裡開始向旁邊的同學傳一束花.- 這個時候某個人(比如班長),在擊鼓,鼓聲停下的一顆,花落在誰手裡,誰就出來表演節目.
  • 修改游戲規則:

    • 我們來修改一下這個游戲規則.
    • 幾個朋友一起玩一個游戲,圍成一圈,開始數數,數到某個數字的人自動淘汰.
    • 最後剩下的這個人會獲得勝利,請問最後剩下的是原來在哪一個位置上的人?
  • 封裝一個基於隊列的函數

    • 參數:所有參與人的姓名,基於的數字
    • 結果:最終剩下的一人的姓名
//擊鼓傳花
function paseGame(nameList, num) {
    //創建一個隊列
    let queue = new Queue()

    //將所有人依次加入隊列
    for (let i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])
    }

    //開始數數字
    while (queue.size() > 1) {
        //不是num的時候嗎,重新加入到隊列的末尾
        //num數字之前的人重新放入到隊列的末尾
        for (let i = 0; i < num - 1; i++) {
            queue.enqueue(queue.dequeue())
        }
        //num對應的這個人直接從隊列中刪除 
        queue.dequeue()
    }
    //獲取剩下的結果
    let endName = queue.front()
    console.log(endName);
    return nameList.indexOf(endName)
}

paseGame(['lisi', 'zhangsan', 'fgbfd', 'tom', 'jack', 'lisa', 'ez', 'laoshu', 'jikdf', 'dsada', 'poru', 'fjds'], 6)//fgbfd

六.優先順序隊列

優先順序隊列的特點:

  • 我們知道,普通的隊列插入一個元素,數據會被放在後端.並且需要前面所有的元素都處理完成後才會處理前面的數據.
  • 但是優先順序隊列,在插入一個元素的時候會考慮該數
    據的優先順序.
  • 和其他數據優先順序進行比較.
  • 比較完成後,可以得出這個元素在隊列中正確的位置
  • 其他處理方式,和基本隊列的處理方式一樣.

優先順序隊列主要考慮的問題:

  • 每個元素不再只是一個數據,而且包含數據的優先順序
  • 在添加方式中,根據優先順序放入正確的位置.

優先順序隊列的應用:

  • 一個現實的例子就是機場登機的順序
    • 頭等艙和商務艙乘客的優先順序要高於經濟艙乘客。
    • 在有些國家,老年人和孕婦(或帶小孩的婦女)登機時也享有高於其他乘客的優先順序。
  • 另一個現實中的例子是醫院的(急診科)候診室。
    • 醫生會優先處理病情比較嚴重的患者。
    • 當然,一般情況下是按照排號的順序。
  • 電腦中,我們也可以通過優先順序隊列來重新排序隊列中任務的順序
    • 比如每個線程處理的任務重要性不同,我們可以通過優先順序的大小,來決定該線程在隊列中被處理的次序.

七.優先順序隊列的實現

  • 現優先順序隊列相對隊列主要有兩方面需要考慮:
    • 1)封裝元素和優先順序放在一起(可以封裝一個新的構造函數)
    • 2)添加元素時,將新插入元素的優先順序和隊列中已經存在的元素優先順序進行比較,以獲得自己正確的位置.
//封裝優先順序隊列
function PriorityQueue() {
    //在PriorityQueue重新創建了一個類
    function QueueElemnt(element, priority) {
        this.element = element
        this.priority = priority
    }

    //封裝屬性
    this.items = []

    //1.實現插入方法
    PriorityQueue.prototype.enqueue = function (element, priority) {
        //創建QueueElement對象
        let queueElemnt = new QueueElemnt(element, priority)

        //判斷隊列是否為空
        if (this.items.length === 0) {
            this.items.push(queueElemnt)
        } else {
            let added = false
            for (let i = 0; i < this.items.length; i++) {
                if (queueElemnt.priority < this.items[i].priority) {
                    this.items.splice(i, 0, queueElemnt)
                    added = true
                    break
                }
            }
            if (!added) {
                this.items.push(queueElemnt)
            }
        }
    }

    //2.從隊列中刪除前端元素
    PriorityQueue.prototype.dequeue = function () {
        return this.items.shift()
    }

    //3.查看前端元素
    PriorityQueue.prototype.front = function () {
        return this.items[0]
    }

    //4.查看隊列是否為空
    PriorityQueue.prototype.isEmpty = function () {
        return this.items.length === 0
    }

    //5.查看隊列中元素的個數
    PriorityQueue.prototype.size = function () {
        return this.items.length
    }

    //6.toString方法
    PriorityQueue.prototype.toString = function () {
        let resultString = ''
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i] + ''
        }
        return resultString
    }
}

// 測試代碼
let pq = new PriorityQueue()
pq.enqueue('abc', 111)
pq.enqueue('cba', 151)
pq.enqueue('nba', 66)
pq.enqueue('wba', 856)
console.log(pq);

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • OmniPlan Pro 4 for Mac是應用在Mac上的最好用的項目流程管理工具,以拖放支持為特點,對您日常工作想法做記錄,幫助我們創建合乎邏輯的項目計劃管理,OmniPlan 4 Mac版全新設計,拖放支持更加簡單,但卻更加先進強大,它還能被用來優化資源、精簡預算快速共用或添加任務。 詳情: ...
  • 記在Linux系統源碼包安裝MySQL實驗環境:系統版本:CentOS 7MySQL版本:5.7.39(https://downloads.mysql.com/archives/get/p/23/file/mysql-5.7.39-el7-x86_64.tar.gz)實驗開始步驟一安裝依賴yum - ...
  • 作者:小牛呼嚕嚕 | https://xiaoniuhululu.com 電腦內功、JAVA底層、面試相關資料等更多精彩文章在公眾號「小牛呼嚕嚕 」 前言 大家好,國慶馬上就要過去了,這不偷偷地進來學習了一波。之前小牛學過一點深度學習的知識,做了幾個項目,發現CPU來訓練就很慢,但是後來用裝有GP ...
  • 今天跟大家分享一些優化神技,當你面試或者工作中你遇到如下問題,那就使出今天學到的絕招,一招定乾坤! 如何用更少的記憶體保存更多的數據? 我們應該從 Redis 是如何保存數據的原理展開,分析鍵值對的存儲結構和原理。 從而繼續延展出每種數據類型底層的數據結構,針對不同場景使用更恰當的數據結構和編碼實現更 ...
  • 在經濟面臨下行壓力、疫情反覆等不確定因素之下,推動數字化轉型就成為了許多企業的“救命稻草”。然而,較高的數字化轉型門檻、不成系統的數據服務,以及缺乏規範的行業標準等都成了企業數字化轉型路上的“絆腳石”。 2015年,袋鼠雲成立並毅然投身於具有巨大想象力的數字經濟發展浪潮,經過7年努力實踐,不斷完善自 ...
  • 摘要:本文介紹了9個GaussDB常用的對象語句,希望對大家有幫助。 本文分享自華為雲社區《GaussDB對象相關語句》,作者:酷哥。 1. 常用函數 pg_database_size() -- 資料庫使用的磁碟空間。 pg_table_size() -- 表使用的磁碟空間。 pg_total_re ...
  • 故障檢測(Failure Detection)是 Group Replication 的一個核心功能模塊,通過它可以及時識別集群中的故障節點,並將故障節點從集群中剔除掉。如果不將故障節點及時剔除的話,一方面會影響集群的性能,另一方面還會阻止集群拓撲的變更。 下麵結合一個具體的案例,分析 Group ...
  • 這裡給大家分享我在網上總結出來的一些知識,希望對大家有所幫助 在AndroidManifest.xml註冊ACTION事件 <activity android:name="com.test.app.MainActivity" android:configChanges="orientation|ke ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...