[[390111]]

在了解編程語言的基礎(chǔ)上，你還必須了解如何組織數(shù)據(jù)，以便根據(jù)任務(wù)輕松有效地操作數(shù)據(jù)。這就是數(shù)據(jù)結(jié)構(gòu)的作用。

在這篇文章中，我將描述隊列數(shù)據(jù)結(jié)構(gòu)，其具有的操作以及向您展示JavaScript中的隊列實現(xiàn)。

1.隊列數(shù)據(jù)結(jié)構(gòu)

如果你喜歡旅行（像我一樣），很可能你在機(jī)場通過了辦理登機(jī)手續(xù)。如果有很多旅客愿意辦理登機(jī)手續(xù)，自然就會在值機(jī)柜臺前排起長龍。

剛進(jìn)入機(jī)場并想要辦理登機(jī)手續(xù)的旅客將排隊進(jìn)入隊列，而剛剛在服務(wù)臺辦理了登機(jī)手續(xù)的旅客則可以離開隊列。

這是隊列的真實示例—隊列數(shù)據(jù)結(jié)構(gòu)以相同的方式工作。

隊列是一種“先入先出”（FIFO）數(shù)據(jù)結(jié)構(gòu)的類型。入隊（輸入）的第一項是要出隊（輸出）的第一項。

從結(jié)構(gòu)上說，一個隊列有2個指針。隊列中最早的排隊項目位于隊列的頂部，而最新隊列的項目位于隊列的末尾。

2.隊列中的操作

隊列主要支持兩種操作：入隊列（enqueue）和出隊列（dequeue）。此外，您可能會發(fā)現(xiàn)使用peek和length操作非常有用。

2.1 入隊操作

入隊操作在隊列尾部插入一個項目。

上圖中的入隊操作將項目 8 插入尾部，8 成為隊列的尾部。

queue.enqueue(8); 

2.2 出隊操作

出隊操作提取隊列頭部的項，隊列中的下一項成為頭。

在上面的圖片中，出隊操作從隊列中返回并刪除項目 7，在退出隊列后，項目 2 成為新的頭。

queue.dequeue(); // => 7 

2.3 Peek操作

Peek操作讀取隊列的開頭，而不會更改隊列。

項目 7 是上圖中隊列的頭部，Peek操作只是返回隊列的頭部——第 7 項，而不修改隊列。

queue.peek(); // => 7 

2.4 隊列長度

長度操作計算隊列包含多少個項目。

圖片中的隊列有4個項目：4、6、2 和 7。因此，隊列長度為 4。

queue.length; // => 4 

2.5 隊列操作時間復(fù)雜度

關(guān)于所有的隊列操作--enqueue、dequeue、peek和length——重要的是，所有這些操作必須在恒定的時間內(nèi) O(1) 執(zhí)行。

恒定的時間 O(1) 意味著無論隊列的大小(它可以有10個或100萬個項目)：enqueue、dequeue、peek和length操作必須在相對相同的時間內(nèi)執(zhí)行。

3.在JavaScript中實現(xiàn)隊列

讓我們看一下隊列數(shù)據(jù)結(jié)構(gòu)的可能實現(xiàn)，同時維持所有操作必須在恒定時間 O(1) 中執(zhí)行的要求。

class Queue { 
  constructor() { 
    this.items = {}; 
    this.headIndex = 0; 
    this.tailIndex = 0; 
  } 
 
  enqueue(item) { 
    this.items[this.tailIndex] = item; 
    this.tailIndex++; 
  } 
 
  dequeue() { 
    const item = this.items[this.headIndex]; 
    delete this.items[this.headIndex]; 
    this.headIndex++; 
    return item; 
  } 
 
  peek() { 
    return this.items[this.headIndex]; 
  } 
 
  get length() { 
    return this.tailIndex - this.headIndex; 
  } 
} 
 
const queue = new Queue(); 
 
queue.enqueue(7); 
queue.enqueue(2); 
queue.enqueue(6); 
queue.enqueue(4); 
 
queue.dequeue(); // => 7 
 
queue.peek();    // => 2 
 
queue.length;    // => 3 

Try the demo.

const queue = new Queue() 是創(chuàng)建隊列實例的方式。

調(diào)用 queue.enqueue(7) 方法會將項目7排隊到隊列中。

queue.dequeue() 從隊列中去隊列一個頭部的項目，而 queue.peek() 只是Peek頭部的項目。

最后，queue.length 顯示隊列中還有多少項目。

隊列方法的復(fù)雜性

Queue類的 queue()、dequeue()、peek() 和 length() 方法僅使用：

屬性訪問器（例如 this.items[this.headIndex] ），

或執(zhí)行算術(shù)操作（例如 this.headIndex++ ）

因此，這些方法的時間復(fù)雜度是恒定時間 O(1)。

總結(jié)

隊列數(shù)據(jù)結(jié)構(gòu)是“先入先出”（FIFO）的一種：最早入隊的項是最早出隊的項。

隊列有2個主要操作：入隊和出隊。另外，隊列可以具有輔助操作，例如Peek和長度。

所有隊列操作必須在恒定時間 O(1) 中執(zhí)行。

原文：https://dmitripavlutin.com/javascript-queue/

作者：Dmitri Pavlutin