隊(duì)列結(jié)構(gòu)

一.認(rèn)識(shí)隊(duì)列

• 受限的線性結(jié)構(gòu):
  • 我們已經(jīng)學(xué)習(xí)了一種受限的線性結(jié)構(gòu):棧結(jié)構(gòu).
  • 并且已經(jīng)知道這種受限的數(shù)據(jù)結(jié)構(gòu)對于解決某些特定問題,會(huì)有特別的
    效果.
  • 下面,我們再來學(xué)習(xí)另外一個(gè)受限的數(shù)據(jù)結(jié)構(gòu):隊(duì)列.
• 隊(duì)列(Queue)，它是一種受限的線性表,先進(jìn)先出(FIFO First ln First Out)
  • 受限之處在于它只允許在表的前端( front ）進(jìn)行刪除操作
  • 而在表的后端(rear)進(jìn)行插入操作
• 生活中類似的隊(duì)列結(jié)構(gòu)
  • 生活中類似隊(duì)列的場景就是非常多了
  • 比如在電影院,商場,甚至是廁所排隊(duì).
  • 優(yōu)先排隊(duì)的人,優(yōu)先處理.(買票,結(jié)賬, WC)

二.隊(duì)列的應(yīng)用

• 打印隊(duì)列:
  • 有五份文檔需要打印,這些文檔會(huì)按照次序放入到打印隊(duì)列中.
  • 打印機(jī)會(huì)依次從隊(duì)列中取出文檔,優(yōu)先放入的文檔，優(yōu)先被取出，并且對該文檔進(jìn)行打印.
  • 以此類推,直到隊(duì)列中不再有新的文檔.
• 線程隊(duì)列:
  • 在開發(fā)中,為了讓任務(wù)可以并行處理,通常會(huì)開啟多個(gè)線程.
  • 但是,我們不能讓大量的線程同時(shí)運(yùn)行處理任務(wù).(占用過多的資源)
  • 這個(gè)時(shí)候,如果有需要開啟線程處理任務(wù)的情況,我們就會(huì)使用線程隊(duì)列.
  • 線程隊(duì)列會(huì)依照次序來啟動(dòng)線程,并且處理對應(yīng)的任務(wù).
• 隊(duì)列如何實(shí)現(xiàn)呢?
  • 我們一起來研究一下隊(duì)列的實(shí)現(xiàn).

三.隊(duì)列類的創(chuàng)建

• 隊(duì)列的實(shí)現(xiàn)和棧一樣,有兩種方案:
  • 基于數(shù)組實(shí)現(xiàn)
  • 基于鏈表實(shí)現(xiàn)

function Queue() {
    //屬性
    this.items = []
}

四.隊(duì)列的常見操作

• 隊(duì)列有哪些常見的操作呢?
  • enqueue(element):向隊(duì)列尾部添加一個(gè)(或多個(gè))新的項(xiàng)。
  • dequeue()∶移除隊(duì)列的第一(即排在隊(duì)列最前面的)項(xiàng)，并返回被移除的元素。
  • front():返回隊(duì)列中第一個(gè)元素——最先被添加，也將是最先被移除的元素。隊(duì)列不做任何變動(dòng)（不移除元素，只返回元素信息——與Stack類的peek方法非常類似)。
  • isEmpty):如果隊(duì)列中不包含任何元素，返回true，否則返回false。
  • size():返回隊(duì)列包含的元素個(gè)數(shù)，與數(shù)組的length屬性類似。
  • toString():將隊(duì)列中的內(nèi)容,轉(zhuǎn)成字符串形式
• 現(xiàn)在，,我們來實(shí)現(xiàn)這些方法.
  • 其實(shí)很棧中方法的實(shí)現(xiàn)非常相似.因?yàn)槲覀兊年?duì)列也是基于數(shù)組的

//1.將元素加入到隊(duì)列中
    Queue.prototype.enqueue = function (element) {
        this.items.push(element)
    }

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

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

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

    //5.查看隊(duì)列中元素的個(gè)數(shù)
    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
    }

五.擊鼓傳花

• 擊鼓傳花是一個(gè)常見的面試算法題.使用隊(duì)列可以非常方便的實(shí)現(xiàn)最終的結(jié)果.

  

  成都創(chuàng)新互聯(lián)公司長期為上千多家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為舒蘭企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)，舒蘭網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

• 原游戲規(guī)則:

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

• 修改游戲規(guī)則:

  • 我們來修改一下這個(gè)游戲規(guī)則.
  • 幾個(gè)朋友一起玩一個(gè)游戲,圍成一圈，開始數(shù)數(shù),數(shù)到某個(gè)數(shù)字的人自動(dòng)淘汰.
  • 最后剩下的這個(gè)人會(huì)獲得勝利,請問最后剩下的是原來在哪一個(gè)位置上的人?

• 封裝一個(gè)基于隊(duì)列的函數(shù)

  • 參數(shù):所有參與人的姓名,基于的數(shù)字
  • 結(jié)果:最終剩下的一人的姓名

//擊鼓傳花
function paseGame(nameList, num) {
    //創(chuàng)建一個(gè)隊(duì)列
    let queue = new Queue()

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

    //開始數(shù)數(shù)字
    while (queue.size() > 1) {
        //不是num的時(shí)候嗎，重新加入到隊(duì)列的末尾
        //num數(shù)字之前的人重新放入到隊(duì)列的末尾
        for (let i = 0; i < num - 1; i++) {
            queue.enqueue(queue.dequeue())
        }
        //num對應(yīng)的這個(gè)人直接從隊(duì)列中刪除 
        queue.dequeue()
    }
    //獲取剩下的結(jié)果
    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

六.優(yōu)先級隊(duì)列

優(yōu)先級隊(duì)列的特點(diǎn):

• 我們知道,普通的隊(duì)列插入一個(gè)元素,數(shù)據(jù)會(huì)被放在后端.并且需要前面所有的元素都處理完成后才會(huì)處理前面的數(shù)據(jù).
• 但是優(yōu)先級隊(duì)列,在插入一個(gè)元素的時(shí)候會(huì)考慮該數(shù)
  據(jù)的優(yōu)先級.
• 和其他數(shù)據(jù)優(yōu)先級進(jìn)行比較.
• 比較完成后,可以得出這個(gè)元素在隊(duì)列中正確的位置
• 其他處理方式,和基本隊(duì)列的處理方式一樣.

優(yōu)先級隊(duì)列主要考慮的問題:

• 每個(gè)元素不再只是一個(gè)數(shù)據(jù),而且包含數(shù)據(jù)的優(yōu)先級
• 在添加方式中,根據(jù)優(yōu)先級放入正確的位置.

優(yōu)先級隊(duì)列的應(yīng)用:

• 一個(gè)現(xiàn)實(shí)的例子就是機(jī)場登機(jī)的順序
  • 頭等艙和商務(wù)艙乘客的優(yōu)先級要高于經(jīng)濟(jì)艙乘客。
  • 在有些國家，老年人和孕婦（或帶小孩的婦女）登機(jī)時(shí)也享有高于其他乘客的優(yōu)先級。
• 另一個(gè)現(xiàn)實(shí)中的例子是醫(yī)院的（急診科)候診室。
  • 醫(yī)生會(huì)優(yōu)先處理病情比較嚴(yán)重的患者。
  • 當(dāng)然,一般情況下是按照排號的順序。
• 計(jì)算機(jī)中,我們也可以通過優(yōu)先級隊(duì)列來重新排序隊(duì)列中任務(wù)的順序
  • 比如每個(gè)線程處理的任務(wù)重要性不同,我們可以通過優(yōu)先級的大小,來決定該線程在隊(duì)列中被處理的次序.

七.優(yōu)先級隊(duì)列的實(shí)現(xiàn)

• 現(xiàn)優(yōu)先級隊(duì)列相對隊(duì)列主要有兩方面需要考慮:
  • 1)封裝元素和優(yōu)先級放在一起(可以封裝一個(gè)新的構(gòu)造函數(shù))
  • 2)添加元素時(shí),將新插入元素的優(yōu)先級和隊(duì)列中已經(jīng)存在的元素優(yōu)先級進(jìn)行比較,以獲得自己正確的位置.

//封裝優(yōu)先級隊(duì)列
function PriorityQueue() {
    //在PriorityQueue重新創(chuàng)建了一個(gè)類
    function QueueElemnt(element, priority) {
        this.element = element
        this.priority = priority
    }

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

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

        //判斷隊(duì)列是否為空
        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.從隊(duì)列中刪除前端元素
    PriorityQueue.prototype.dequeue = function () {
        return this.items.shift()
    }

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

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

    //5.查看隊(duì)列中元素的個(gè)數(shù)
    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);