[ JavaScript ] 資料結構與演算法 —— 佇列
摘要：
前言
JavaScript是當下最流行的程式語言之一，它可以做很多事情：
資料視覺化（D3.js，Three.js，Chart.js）;
移動端應用(React Native,Weex,AppCan,Flutter,Hybrid App,小程式);
服務端(Expr...
前言
JavaScript是當下最流行的程式語言之一，它可以做很多事情：
- 資料視覺化（D3.js，Three.js，Chart.js）;
- 移動端應用(React Native,Weex,AppCan,Flutter,Hybrid App,小程式);
- 服務端(Express.js,Koa2)；
- 桌面應用(Electron,nw.js);
- 遊戲,VR，AR(LayaAir,Egret,Turbulenz,PlayCanvas);
- 等等。。。
而且目前大部分程式語言的高階應用都會用到資料結構與演算法以及設計模式。
本篇主要有三部分
- 什麼是佇列
- 佇列的實現
- 佇列的變種
什麼是佇列
較官方解釋
佇列是遵循FIFO（First In First Out，先進先出，也稱為先來先服務）原則的一組有序的項。
佇列在尾部新增新元素，並從頂部移除元素。最新新增的元素必須排在佇列的末尾 。
注：出隊入隊是自己加的，不知道是不是這麼叫
個人理解
我看有很多文件都是說佇列就像買什麼東西排隊，我認為這個比喻用在標準佇列上不恰當。
我覺得標準佇列像是一段管道，每次都只能放一個球進去，上邊只用來放球（入隊），由於地球引力，球會從下邊的口出去（出隊）。
佇列：這段可以放球的管道就是佇列
元素：管道里的球
隊首：在當前管道里的球最早放進去的那個球的位置，同時也是第一個掉出去的球
隊尾：在當前管道里的球最後放進去的那個球的位置，同時也是最後一個掉出去的球
佇列的實現
- 新增佇列成員
- 刪除佇列成員
- 返回隊首的成員
- 佇列是否為空
- 清空佇列
- 佇列長度
- 返回字串形式的佇列成員
class Queue {
constructor() {
this.count = 0; // 整個佇列下一成員的位置
this.lowestCount = 0; // 在第一位的成員位置
this.items = {}; // 用來存放的佇列
}
enqueue(element) {
// 新增佇列成員 進入佇列
}
dequeue() {
// 刪除佇列成員 離開佇列
}
peek() {
// 返回隊首的成員
}
isEmpty() {
// 判斷佇列是否為空
}
clear() {
// 將所有的資料初始化
}
size() {
// 佇列長度
}
toString() {
// 返回字串形式的佇列成員
}
}
新增佇列成員
enqueue(element) {
this.items[this.count] = element; // 將元素放入佇列
this.count++; // 將計數器加一
}
刪除佇列成員
dequeue() {
if (this.isEmpty()) { // 如果是空
return undefined; // 返回未定義 undefined
}
const result = this.items[this.lowestCount]; // 將隊首的成員儲存下
delete this.items[this.lowestCount]; // 將隊首的成員刪除掉 刪除物件屬性
this.lowestCount++; // 將佇列提前一位 指向隊首的指標後移一位
return result; // 返回被刪除的成員
}
返回隊首的成員
peek() {
if (this.isEmpty()) { // 非空才能繼續處理
return undefined;
}
return this.items[this.lowestCount];
}
佇列是否為空
isEmpty() { // 判斷長度是不是 0
return this.size() === 0;
}
清空佇列
clear() {
this.count = 0; // 恢復初始值
this.lowestCount = 0;// 恢復初始值
this.items = {};// 重新賦值空物件
}
佇列長度
size() { // 佇列長度 等於 整個佇列下一成員的位置 減去 在第一位的成員位置
return this.count - this.lowestCount;
}
返回字串形式的佇列成員
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[this.lowestCount]}`;
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
佇列的變種
- 優先佇列
類似去醫院看病，急診，會優先一般的門診
- 迴圈佇列
類似搶凳子游戲，佇列首位相連
優先佇列
在新增成員時會判斷優先順序，
class QueueElement (element, priority){ // 佇列成員類
this.element = element; // 存放成員
this.priority = priority;// 存放優先順序
}
enqueue(element, priority){
let queueElement = new QueueElement(element, priority);// 新增成員
let added = false;// 是否已新增到佇列
for (let i = 0; i < this.size(); i++){// 遍歷佇列
if (queueElement.priority < items[i].priority){ // 尋找優先順序低的成員，並插入到其之前
// splice start
for(let j = this.size(); j > i; j--){
items[j] = items[j-1];
}
items[i] = queueElement;
// splice end
added = true;// 識別符號置為真，表示已經新增
break; // 跳出迴圈
}
}
if (!added){// 如果沒有找到優先順序比新新增的成員低的，那麼將其新增到隊尾
items.push(queueElement);
}
};
迴圈佇列
在操作時每刪除一個佇列成員就將刪除的這個佇列成員重新新增到佇列中
for (let i = 0; i < number; i++){
queue.enqueue(queue.dequeue());
}