一、隊(duì)列簡(jiǎn)介

隊(duì)列是是一種受限的線性表，特點(diǎn)為先進(jìn)先出（FIFO：first in first out）。

受限之處在于它只允許在表的前端（front）進(jìn)行刪除操作；在表的后端（rear）進(jìn)行插入操作；

相當(dāng)于排隊(duì)買票，先來(lái)的先買票，后來(lái)的后買票。

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

打印隊(duì)列：計(jì)算機(jī)打印多個(gè)文件的時(shí)候，需要排隊(duì)打印；線程隊(duì)列：當(dāng)開(kāi)啟多線程時(shí)，當(dāng)新開(kāi)啟的線程所需的資源不足時(shí)就先放入線程隊(duì)列，等待CPU處理；

隊(duì)列類的實(shí)現(xiàn)：

隊(duì)列的實(shí)現(xiàn)和棧一樣，有兩種方案：

基于數(shù)組實(shí)現(xiàn)；基于鏈表實(shí)現(xiàn)；

隊(duì)列的常見(jiàn)操作：

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)成字符串形式；

二、封裝隊(duì)列類

2.1.代碼實(shí)現(xiàn)

// 基于數(shù)組封裝隊(duì)列類 function Queue() { // 屬性 this.items = [] // 方法 // 1.enqueue():將元素加入到隊(duì)列中 Queue.prototype.enqueue = element => { this.items.push(element) } // 2.dequeue():從隊(duì)列中刪除前端元素 Queue.prototype.dequeue = () => { return this.items.shift() } // 3.front():查看前端的元素 Queue.prototype.front = () => { return this.items[0] } // 4.isEmpty:查看隊(duì)列是否為空 Queue.prototype.isEmpty = () => { return this.items.length == 0; } // 5.size():查看隊(duì)列中元素的個(gè)數(shù) Queue.prototype.size = () => { return this.items.length } // 6.toString():將隊(duì)列中元素以字符串形式輸出 Queue.prototype.toString = () => { let resultString = ’’ for (let i of this.items){ resultString += i + ’ ’ } return resultString } }

測(cè)試代碼：

// 創(chuàng)建隊(duì)列 let queue = new Queue() // 將元素加入到隊(duì)列中 queue.enqueue(’a’) queue.enqueue(’b’) queue.enqueue(’c’) queue.enqueue(’d’) console.log(queue); //58 // 從隊(duì)列中刪除元素 queue.dequeue() console.log(queue); //62 queue.dequeue() console.log(queue); //64 //front console.log(queue.front()); //67 // 驗(yàn)證其他方法 console.log(queue.isEmpty()); //70 console.log(queue.size()); //71 console.log(queue.toString()); //72

測(cè)試結(jié)果：

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

使用隊(duì)列實(shí)現(xiàn)小游戲：擊鼓傳花，傳入一組數(shù)據(jù)和設(shè)定的數(shù)字num，循環(huán)遍歷數(shù)組內(nèi)元素，遍歷到的元素為指定數(shù)字num時(shí)將該元素刪除，直至數(shù)組剩下一個(gè)元素。

代碼實(shí)現(xiàn)：

// 隊(duì)列應(yīng)用：面試題：擊鼓傳花 let passGame = (nameList, num) => { //1.創(chuàng)建隊(duì)列結(jié)構(gòu) let queue = new Queue() //2.將所有人依次加入隊(duì)列 // 這是ES6的for循環(huán)寫法，i相當(dāng)于nameList[i] for(let i of nameList){ queue.enqueue(i) } // 3.開(kāi)始數(shù)數(shù) while(queue.size() > 1){//隊(duì)列中只剩1個(gè)人就停止數(shù)數(shù) // 不是num的時(shí)候，重新加入隊(duì)列末尾 // 是num的時(shí)候，將其從隊(duì)列中刪除 // 3.1.num數(shù)字之前的人重新放入隊(duì)列的末尾(把隊(duì)列前面刪除的加到隊(duì)列最后) for(let i = 0; i< num-1; i++ ){ queue.enqueue(queue.dequeue()) } // 3.2.num對(duì)應(yīng)這個(gè)人，直接從隊(duì)列中刪除 /* 思路是這樣的，由于隊(duì)列沒(méi)有像數(shù)組一樣的下標(biāo)值不能直接取到某一元素，所以采用，把num前面的num-1個(gè)元素先刪除后添加到隊(duì)列末尾，這樣第num個(gè)元素就排到了隊(duì)列的最前面，可以直接使用dequeue方法進(jìn)行刪除 */ queue.dequeue() } //4.獲取剩下的那個(gè)人 console.log(queue.size()); //104 let endName = queue.front() console.log(’最終剩下的人：’ + endName); //106return nameList.indexOf(endName); } //5.測(cè)試擊鼓傳花 let names = [’lily’, ’lucy’, ’Tom’, ’Lilei’, ’Tony’] console.log(passGame(names, 3));//113

測(cè)試結(jié)果：

三、優(yōu)先隊(duì)列

優(yōu)先級(jí)隊(duì)列主要考慮的問(wèn)題為：

每個(gè)元素不再只是一個(gè)數(shù)據(jù)，還包含數(shù)據(jù)的優(yōu)先級(jí)；在添加數(shù)據(jù)過(guò)程中，根據(jù)優(yōu)先級(jí)放入到正確位置；3.1.優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)

代碼實(shí)現(xiàn)：

// 封裝優(yōu)先級(jí)隊(duì)列 function PriorityQueue() { //內(nèi)部類：在類里面再封裝一個(gè)類;表示帶優(yōu)先級(jí)的數(shù)據(jù) function QueueElement(element, priority) { this.element = element; this.priority = priority; } // 封裝屬性 this.items = [] // 1.實(shí)現(xiàn)按照優(yōu)先級(jí)插入方法 PriorityQueue.prototype.enqueue = (element, priority) => { // 1.1.創(chuàng)建QueueElement對(duì)象 let queueElement = new QueueElement(element, priority) // 1.2.判斷隊(duì)列是否為空 if(this.items.length == 0){ this.items.push(queueElement) }else{ // 定義一個(gè)變量記錄是否成功添加了新元素 let added = false for(let i of this.items){ // 讓新插入的元素與原有元素進(jìn)行優(yōu)先級(jí)比較(priority越小，優(yōu)先級(jí)越大) if(queueElement.priority < i.priority){ this.items.splice(i, 0, queueElement) added = true // 新元素已經(jīng)找到插入位置了可以使用break停止循環(huán) break } } // 新元素沒(méi)有成功插入，就把它放在隊(duì)列的最前面 if(!added){ this.items.push(queueElement) } } } // 2.dequeue():從隊(duì)列中刪除前端元素 PriorityQueue.prototype.dequeue = () => { return this.items.shift() } // 3.front():查看前端的元素 PriorityQueue.prototype.front = () => { return this.items[0] } // 4.isEmpty():查看隊(duì)列是否為空 PriorityQueue.prototype.isEmpty = () => { return this.items.length == 0; } // 5.size():查看隊(duì)列中元素的個(gè)數(shù) PriorityQueue.prototype.size = () => { return this.items.length } // 6.toString():以字符串形式輸出隊(duì)列中的元素 PriorityQueue.prototype.toString = () => { let resultString = ’’ for (let i of this.items){ resultString += i.element + ’-’ + i.priority + ’ ’ } return resultString } }

測(cè)試代碼：

// 測(cè)試代碼 let pq = new PriorityQueue(); pq.enqueue(’Tom’,111); pq.enqueue(’Hellen’,200); pq.enqueue(’Mary’,30); pq.enqueue(’Gogo’,27); // 打印修改過(guò)后的優(yōu)先隊(duì)列對(duì)象 console.log(pq);

測(cè)試結(jié)果：

3.2.注意點(diǎn)

關(guān)于數(shù)組方法splice用法：

splice（1，0，’Tom’）：表示在索引為1的元素前面插入元素’Tom‘（也可以理解為從索引為1的元素開(kāi)始刪除，刪除0個(gè)元素，再在索引為1的元素前面添加元素’Tom’）；

splice（1，1，’Tom’）：表示從索引為1的元素開(kāi)始刪除（包括索引為1的元素），共刪除1個(gè)元素，并添加元素’Tom’。即把索引為1的元素替換為元素’Tom’。

數(shù)組的push方法在數(shù)組、棧和隊(duì)列中的形式：

數(shù)組：在數(shù)組[0，1，2]中，pop(3)，結(jié)果為[0，1，2，3]； 棧：執(zhí)行pop(0)，pop(1)，pop(2)，pop(3)，從棧底到棧頂?shù)脑胤謩e為：0，1，2，3；如果看成數(shù)組，可寫為[0，1，2，3]，但是索引為3的元素3其實(shí)是棧頂元素；所以說(shuō)棧的push方法是向棧頂添加元素（但在數(shù)組的視角下為向數(shù)組尾部添加元素）； 隊(duì)列：enqueue方法可以由數(shù)組的push方法實(shí)現(xiàn)，與數(shù)組相同，相當(dāng)于在數(shù)組尾部添加元素。

可以這樣想：棧結(jié)構(gòu)是頭朝下（索引值由下往上增大）的數(shù)組結(jié)構(gòu)。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持好吧啦網(wǎng)。