上一篇筆記學習了棧這一數據結構,與棧很相似的另一種數據結構叫做隊列。與棧的LIFO(后進先出)原則不同的是,隊列遵循的是FIFO(先進先出)原則。這篇筆記就來學習隊列這一數據結構。

隊列數據結構

FIFO原則的規則是,在尾部添加新元素,并從頂部移除元素。最新添加的元素必須在隊列末尾。以生活中的排隊為例,來理解FIFO原則。排在第一位的人會先接受服務。

創建隊列

還是先列出來隊列需要實現的幾種方法:

enqueue(element):添加一個新元素到隊尾
dequeue:移除隊首的元素,并返回被移除的元素
peek:返回隊首的元素,不對隊列進行任何修改
isEmpty:如果隊列里沒有任何元素,就返回true,否則返回false
clear:清空棧里的所有元素
size:返回棧里的元素個數
toString: 返回隊列

先從最基礎的聲明開始,我們來實現一個隊列。既然隊列也是從尾部添加元素,那么跟棧的添加方式就一樣了,我們來試著寫一下:

class Queue{
 constructor() {
  this.count = 0
  this.items = {}
 }

 enqueue(element) {
  this.items[this.count] = element
  this.count++
 }
}

既然隊列是從頭部移除元素,我們肯定需要另一個變量來當做移除時的鍵,新建一個lowestCount,編寫刪除元素的方法,利用lowestCount來執行刪除,并把刪除的元素彈出隊列:

class Queue{
 constructor() {
  this.count = 0
  this.lowestCount = 0
  this.items = {}
 }

 dequeue() {
  let result = this.items[this.lowestCount]
  delete this.items[this.lowestCount]
  this.lowestCount++
  return result
 }
}

需要注意的是,刪除元素后,我們需要把lowestCount遞增來對應執行完刪除操作后的隊列的第一個元素。

增加和刪除方法完成后,我們來完成size、isEmpty、clear方法,有了count和lowestCount變量,我們遍可以計算出隊列的長度,剩下的isEmpty、clear就簡單的多了:

size() {
 return this.count - this.lowestCount
},
isEmpty() {
 return this.size() === 0
},
clear() {
 this.count = 0
 this.lowestCount = 0
 this.items = {}
}

是不是發現越寫越有感覺了?趁熱打鐵,我們來完成peek方法,并利用isEmpty完善dequeue方法,最后剩下的toString方法,我們只需要將上篇筆記中棧的toString方法稍加改造即可實現:

peek() {
 if(this.isEmpty()){
  return undefined
 }
 retrun this.items[this.lowestCount]
},
dequeue() {
 if(this.isEmpty()){
  return undefined
 }
 let result = this.items[this.lowestCount]
 delete this.items[this.lowestCount]
 this.lowestCount++
 return result
},
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
}

到這里,我們就實現了一個隊列,老樣子,寫完之后還是要驗證一下是否正確:

const queue = new Queue(); 
console.log(queue.isEmpty()); // true

queue.enqueue('John'); 
queue.enqueue('Jack'); 
console.log(queue.toString()); // John,Jack

queue.enqueue('Camila');
console.log(queue.toString()); // John, Jack, Camila 
console.log(queue.size()); // 3 
console.log(queue.isEmpty()); // false

下圖展示了目前為止執行的所有入列操作,以及隊列當前的狀態。

我們再進行一些操作:

queue.dequeue(); // 移除 John 
queue.dequeue(); // 移除 Jack 
console.log(queue.toString()); // Camila

調用兩次dequeue方法的過程如下:

通過觀察,我們實現的隊列確實遵循了先進先出原則。

使用隊列實現擊鼓傳花小游戲

上學的時候,我們都玩過擊鼓傳花的游戲,在這個游戲中,大家會圍成一個圓圈,把花盡快地傳遞給旁邊的人。某一時刻傳花停止,這個時候花在誰手里,誰就退出圓圈、結束游戲。重復這個過程,直到只剩一個人(勝者)。

如果用隊列來模擬過程,大概是:出列->(鼓聲未?!救肓小?、鼓聲停止【淘汰】)-> 循環過程,直到隊列只剩一個元素。實際上擊鼓傳花就是對隊列的一個循環操作過程,也叫循環隊列。

function hotPotato(elementsList, num) {
 const queue = new Queue()
 const elimitatedList = []

 for(let i = 0; i < elementsList.length; i++) {
  queue.enqueue(elementsList[i])
 }

 while(queue.size() > 1) {
  for(let i = 0; i < num; i++) {
   queue.enqueue(queue.dequeue())
  }
  elimitatedList.push(queue.dequeue())
 }
 return {
  eliminated: elimitatedList,
  winner: queue.dequeue()
 }
}

首先算法接受兩個參數,一個是游戲參與者列表elementsList,一個是模擬鼓聲停止的num,在方法內部初始化一個隊列和一個被淘汰者的集合。之后把所有參與者放入隊列中。接著,只要隊列的元素數量大于1,就進行出列->入列的操作。當遇到鼓聲停止(代碼里是i=num)時,將出列的元素放入到淘汰者列表。最后返回勝利者與被淘汰者的集合。

我們來測試一下:

const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
const result = hotPotato(names, 7);
result.eliminated.forEach(name => {
 console.log(`${name}在擊鼓傳花游戲中被淘汰。`);
});
console.log(`勝利者: ${result.winner}`);

以上算法的輸出為:

Camila 在擊鼓傳花游戲中被淘汰。
Jack 在擊鼓傳花游戲中被淘汰。
Carl 在擊鼓傳花游戲中被淘汰。
Ingrid 在擊鼓傳花游戲中被淘汰。
勝利者:John

下圖模擬了這個輸出過程:

除了隊列的變種循環隊列外,我們還可以將棧與隊列進行結合,實現一種允許我們同時從前端和后端添加和移除的特殊隊列——雙端隊列。

雙端隊列數據結構

還是以買票為例,一個剛買了票的人如果只是還需要再問一些簡單的信息,就可以直接回到隊伍的頭部。另外,在隊伍末尾的人如果趕時間,他可以直接離開隊伍。

創建雙端隊列

既然雙端隊列是一種特殊的隊列,所以雙端隊列的一些操作其實跟隊列是一樣的,那么我們只需要對隊列進行改造升級即可。先列下雙端隊列要實現的方法:

addFront(element):該方法在雙端隊列前端添加新的元素。
addBack(element):該方法在雙端隊列后端添加新的元素(實現方法和 Queue 類中的enqueue 方法相同)。
removeFront():該方法會從雙端隊列前端移除第一個元素(實現方法和 Queue 類中的dequeue 方法相同)。
removeBack():該方法會從雙端隊列后端移除第一個元素(實現方法和 Stack 類中的pop 方法一樣)。
peekFront():該方法返回雙端隊列前端的第一個元素(實現方法和 Queue 類中的 peek方法一樣)。
peekBack():該方法返回雙端隊列后端的第一個元素(實現方法和 Stack 類中的 peek方法一樣)。

除了上面列出來的方法外,雙端隊列還有size、isEmpty、clear、toString方法,這幾個方法與Queue中的方法相同。除此之外,我們發現實際上除了addFront以外,其他方法我們之前都已經在棧或隊列中實現過。所以我們只需要實現addFront方法即可:

class Deque{
 constructor() {
  this.count = 0;
    this.lowestCount = 0;
    this.items = {}
 }
 ...
 addFront(element){
  if(this.isEmpty()){
   this.addBack(element)
  } else {
   for(let i = this.count; i > 0; i--){
    this.items[i] = this.items[i - 1]
   }
   this.count++
   this.lowestCount = 0
   this.items[0] = element
  }
 }
}

當隊列為空時,從前端增加元素與從后端增加元素實際上是一樣的,所以我們可以通過條件判斷來直接調用addBack方法。如果隊列不為空,那么我們只需要把每個元素向后移一位,并對count遞增,然后將lowestCount初始化,并把元素添加到第一個位置即可。

除了這兩種情況以外,我們還需要考慮一點,如果我們的隊列不為空,并且已經從前端刪除過一個元素(lowestCount大于等于1),這種情況下,我們只需要將lowestCount 屬性減 1 并將新元素的值放在這個鍵的位置上即可。我們來完善addFront方法:

addFront(element){
 if(this.isEmpty()){
  this.addBack(element)
 } else if (this.lowestCount > 0) {
  this.lowestCount--
    this.items[this.lowestCount] = element
 } else {
  for(let i = this.count; i > 0; i--){
   this.items[i] = this.items[i - 1]
  }
  this.count++
  this.lowestCount = 0
  this.items[0] = element
 }
}

我們來測試一下寫好的雙端隊列:

const deque = new Deque(); 
console.log(deque.isEmpty()); // 輸出 true 
deque.addBack('John'); 
deque.addBack('Jack'); 
console.log(deque.toString()); // John, Jack 
deque.addBack('Camila'); 
console.log(deque.toString()); // John, Jack, Camila 
console.log(deque.size()); // 輸出 3 
console.log(deque.isEmpty()); // 輸出 false 
deque.removeFront(); // 移除 John 
console.log(deque.toString()); // Jack, Camila 
deque.removeBack(); // Camila 決定離開
console.log(deque.toString()); // Jack 
deque.addFront('John'); // John 回來詢問一些信息
console.log(deque.toString()); // John, Jack

使用雙端隊列來實現回文檢查器

回文是正反都能讀通的單詞、詞組、數或一系列字符的序列,例如 madam或 racecar??贍芐』鋨槊竊諉媸怨討幸燦齙焦庋謀適蘊?。在JavaScript中有很多算法來檢測一個字符串是否為回文,比如利用數組的倒序方法。如果用數據結構來實現它的話,最簡單的就是我們剛剛實現的雙端隊列了。

function palindromeChecker(aString) {
 if (aString === undefined || aString === null || (aString !== null && aString.length === 0)) {
  return false; 
 }
 const deque = new Deque();
 const lowerString = aString.toLocaleLowerCase().split(' ').join('');
 let isEqual = true;
 let firstChar, lastChar;

 for (let i = 0; i < lowerString.length; i++) {
  deque.addBack(lowerString.charAt(i));
 }

 while(deque.size() > 1 && isEqual) {
  firstChar = deque.removeFront();
  lastChar = deque.removeBack();
  if (firstChar !== lastChar) {
   isEqual = false;
  }
 return isEqual
}

首先我們先檢查輸入的字符串是否合法,如果不合法,返回false。其次,我們創建一個雙端隊列,并將字符串轉換為小寫,同時移除所有空格。然后我們把字符串按照順序放入到雙端隊列當中。接著我們聲明一個狀態變量isEqual。同時聲明兩個變量(用來存放首位元素)。然后我們只需要利用雙端隊列的removeFront和removeBack方法,循環的取出首位兩個元素進行對比,同時改變isEqual狀態。就可以知道該字符串是否為回文字符串了。

總結

這篇筆記學習了隊列這一數據結構,并用對象的方式實現了隊列算法。同時學習了兩種隊列的變種,循環隊列以及雙端隊列。然后我們還利用隊列實現了擊鼓傳花小游戲和回文檢查器算法。

參考書籍《學習JavaScript數據結構與算法》