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

• 2022 年 11 月 7 日
• 筆記
• javascript, 數據結構與演算法

隊列結構

一.認識隊列

• 受限的線性結構:
  • 我們已經學習了一種受限的線性結構:棧結構.
  • 並且已經知道這種受限的數據結構對於解決某些特定問題,會有特別的
    效果.
  • 下面,我們再來學習另外一個受限的數據結構:隊列.
• 隊列(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);