??我們之前已經(jīng)學(xué)習(xí)過(guò)了一種受限的線性結(jié)構(gòu)：棧結(jié)構(gòu)窒典，并且我們已經(jīng)知道這種受限的數(shù)據(jù)結(jié)構(gòu)對(duì)于解決某些特定問(wèn)題，會(huì)有特別的效果阿趁，下面我們來(lái)學(xué)習(xí)另外一種受限的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列
??之前說(shuō)過(guò)的棧結(jié)構(gòu)是一種遵循先進(jìn)后出規(guī)則的數(shù)據(jù)結(jié)構(gòu)膜蛔，它只允許在棧頂插入或刪除元素，而隊(duì)列則是遵循先進(jìn)先出規(guī)則的數(shù)據(jù)結(jié)構(gòu)脖阵，類似于現(xiàn)實(shí)生活中人們排隊(duì)買(mǎi)火車票皂股，先排隊(duì)的先買(mǎi)票，先到先得命黔，也就是它只允許在隊(duì)列前端進(jìn)行刪除操作（買(mǎi)票）呜呐，而在隊(duì)列的后端進(jìn)行插入操作（排隊(duì)）
生活中隊(duì)列
- 打印隊(duì)列：有五份文檔需要打印，這些文檔會(huì)按照次序放入到打印隊(duì)列中悍募，打印機(jī)會(huì)依次從隊(duì)列中取出文檔蘑辑，優(yōu)先放入的文檔，優(yōu)先會(huì)被取出并打印坠宴，依次類推直到隊(duì)列中沒(méi)有文檔為止
- 線程隊(duì)列：在開(kāi)發(fā)中洋魂，為了讓任務(wù)可以并行處理，通常會(huì)開(kāi)啟多個(gè)線程，但是副砍，我們不能讓大量的線程衔肢，同時(shí)運(yùn)行處理任務(wù)（占用過(guò)多的資源）這個(gè)時(shí)候，如果有需要開(kāi)啟線程處理任務(wù)的情況址晕，我們就會(huì)使用線程隊(duì)列膀懈。線程隊(duì)列會(huì)依照次序來(lái)啟動(dòng)線程，并且處理對(duì)應(yīng)的任務(wù)谨垃，
隊(duì)列結(jié)構(gòu)的實(shí)現(xiàn)以及應(yīng)用
下面代碼中我們創(chuàng)建了一個(gè)隊(duì)列類启搂，并實(shí)現(xiàn)了隊(duì)列常用的相關(guān)的方法。其實(shí)也比較簡(jiǎn)單刘陶，主要也是基于數(shù)組進(jìn)行實(shí)現(xiàn)
// 簡(jiǎn)單的隊(duì)列實(shí)現(xiàn)（基于數(shù)組胳赌，其實(shí)最好的方式是基于鏈表實(shí)現(xiàn)，性能會(huì)高一些）
let Queue = (function(){
let items = [];
return class {
// 向隊(duì)列尾部添加一項(xiàng)
// 存
enqueue(element) {
items.push(element);
}
// 移除隊(duì)列的第一項(xiàng)匙隔，并返回被移除項(xiàng)
// 取
dequeue() {
return items.shift();
}
// 返回隊(duì)列中的第一個(gè)元素
// 查看
front() {
return items[0];
}
// 查看隊(duì)列是否為空
isEmpty() {
return items.length === 0;
}
// 查看大小
size() {
return items.length;
}
// 將隊(duì)列中的內(nèi)容轉(zhuǎn)換為字符串疑苫，并返回
toString() {
let resultString = "";
for (let i in items) {
resultString += items[i];
}
return resultString;
}
}
})()
下面介紹一個(gè)關(guān)于隊(duì)列面試題：擊鼓傳花
??游戲規(guī)則：隨意人數(shù)的同學(xué)圍成一圈，由某個(gè)人開(kāi)始數(shù)數(shù)纷责，比如從班長(zhǎng)（隨機(jī)的）開(kāi)始捍掺，班長(zhǎng)數(shù)1，然后旁邊的人就數(shù)2再膳，依次往后挺勿，當(dāng)數(shù)到某個(gè)人數(shù)到特定數(shù)字之后(事先約定好這個(gè)數(shù)字),那么這個(gè)人將會(huì)被淘汰，此時(shí)下一個(gè)人從頭開(kāi)始數(shù)1喂柒。依次類推不瓶，當(dāng)所有人被淘汰只留一個(gè)人的時(shí)候，即游戲結(jié)束這個(gè)人為勝者
// 擊鼓傳花游戲應(yīng)用
function passGame(nameList, num) {
// 定義一個(gè)隊(duì)列
let queue = new Queue();
// 循環(huán)角色
// 以此添加到隊(duì)列中
for (let i in nameList) {
queue.enqueue(nameList[i]);
}
// 隊(duì)列人數(shù)為1之前一直循環(huán)
while (queue.size() > 1) {
// 根據(jù)數(shù)字進(jìn)行循環(huán)
for (let i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue());
}
// 移除數(shù)到的人
queue.dequeue();
}
return queue.front()
}
console.log(passGame(["小明","小紅","小呂","張三","李四","十五"],7))
優(yōu)先級(jí)隊(duì)列
??優(yōu)先級(jí)隊(duì)列的特點(diǎn)灾杰，我們知道普通的隊(duì)列插入一個(gè)元素蚊丐，數(shù)據(jù)會(huì)直接被放在隊(duì)尾，但是優(yōu)先級(jí)隊(duì)列在插入一個(gè)新元素前會(huì)考慮該數(shù)據(jù)的優(yōu)先級(jí)艳吠，就是即將插入的數(shù)據(jù)會(huì)和隊(duì)列中其他數(shù)據(jù)的優(yōu)先級(jí)進(jìn)行比較麦备，比較完成后，才可以得出這個(gè)元素在隊(duì)列中的正確位置昭娩，除此之外其他處理方式和普通隊(duì)列的處理方式一樣泥兰，那么我們?cè)撊绾螌?shí)現(xiàn)，其實(shí)要實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列主要就是需要修改 enqueue 方法就可以實(shí)現(xiàn)
let PriorityQueue = (function() {
// 基于數(shù)組
let items = [];
// 內(nèi)部類,用于創(chuàng)建元素節(jié)點(diǎn)
let _createQueuElement = class {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
};
return class {
// 向隊(duì)列尾部添加一項(xiàng)
// 存
enqueue(element, priority) {
// 創(chuàng)建
let queuelement = new _createQueuElement(element, priority);
// 如果為空
if (items.length === 0) {
// 直接添加
items.push(queuelement);
return;
} else {
// 如果插入元素题禀，
if (queuelement.priority <= items[0].priority) {
items.unshift(queuelement);
return;
} else if (
queuelement.priority > items[items.length - 1].priority
) {
items.push(queuelement);
return;
}
// 預(yù)先定義 index 值
let index;
items.forEach((v, i) => {
if (
queuelement.priority > items[i].priority &&
queuelement.priority <= items[i + 1].priority
) {
index = i + 1;
}
});
items.splice(index, 0, queuelement);
return index;
}
}
// 移除隊(duì)列的第一項(xiàng)，并返回被移除項(xiàng)
// 取
dequeue() {
return items.shift();
}
// 返回隊(duì)列中的第一個(gè)元素
// 查看
front() {
return items[0];
}
// 查看隊(duì)列是否為空
isEmpty() {
return items.length === 0;
}
// 查看大小
size() {
return items.length;
}
// 將隊(duì)列中的內(nèi)容轉(zhuǎn)換為字符串膀捷，并返回
toString() {
let resultString = "";
for (let i in items) {
resultString += JSON.stringify(items[i]);
}
return resultString;
}
};
})();
let pq = new PriorityQueue();
pq.enqueue("哥哥", 30);
pq.enqueue("小紅", 10);
pq.enqueue("小呂", 20);
pq.enqueue("銀時(shí)", 40);
pq.enqueue("神樂(lè)", 50);
pq.enqueue("神樂(lè)2號(hào)", 15);
pq.enqueue("神樂(lè)3號(hào)", 15);
pq.enqueue("神樂(lè)2號(hào)", 16);
pq.enqueue("神樂(lè)2號(hào)", 17);
console.log(pq.toString());
