如何在JavaScript中實(shí)現(xiàn)隊(duì)列數(shù)據(jù)結(jié)構(gòu)
在了解編程語(yǔ)言的基礎(chǔ)上，你還必須了解如何組織數(shù)據(jù)，以便根據(jù)任務(wù)輕松有效地操作數(shù)據(jù)。這就是數(shù)據(jù)結(jié)構(gòu)的作用。
在這篇文章中，我將描述隊(duì)列數(shù)據(jù)結(jié)構(gòu)，其具有的操作以及向您展示JavaScript中的隊(duì)列實(shí)現(xiàn)。
1.隊(duì)列數(shù)據(jù)結(jié)構(gòu)
如果你喜歡旅行（像我一樣），很可能你在機(jī)場(chǎng)通過(guò)了辦理登機(jī)手續(xù)。如果有很多旅客愿意辦理登機(jī)手續(xù)，自然就會(huì)在值機(jī)柜臺(tái)前排起長(zhǎng)龍。
剛進(jìn)入機(jī)場(chǎng)并想要辦理登機(jī)手續(xù)的旅客將排隊(duì)進(jìn)入隊(duì)列，而剛剛在服務(wù)臺(tái)辦理了登機(jī)手續(xù)的旅客則可以離開隊(duì)列。
這是隊(duì)列的真實(shí)示例—隊(duì)列數(shù)據(jù)結(jié)構(gòu)以相同的方式工作。
隊(duì)列是一種“先入先出”（FIFO）數(shù)據(jù)結(jié)構(gòu)的類型。入隊(duì)（輸入）的第一項(xiàng)是要出隊(duì)（輸出）的第一項(xiàng)。
從結(jié)構(gòu)上說(shuō)，一個(gè)隊(duì)列有2個(gè)指針。隊(duì)列中最早的排隊(duì)項(xiàng)目位于隊(duì)列的頂部，而最新隊(duì)列的項(xiàng)目位于隊(duì)列的末尾。
2.隊(duì)列中的操作
隊(duì)列主要支持兩種操作：入隊(duì)列（enqueue）和出隊(duì)列（dequeue）。此外，您可能會(huì)發(fā)現(xiàn)使用peek和length操作非常有用。
2.1 入隊(duì)操作
入隊(duì)操作在隊(duì)列尾部插入一個(gè)項(xiàng)目。
上圖中的入隊(duì)操作將項(xiàng)目 8 插入尾部，8 成為隊(duì)列的尾部。
- queue.enqueue(8);
2.2 出隊(duì)操作
出隊(duì)操作提取隊(duì)列頭部的項(xiàng)，隊(duì)列中的下一項(xiàng)成為頭。
在上面的圖片中，出隊(duì)操作從隊(duì)列中返回并刪除項(xiàng)目 7，在退出隊(duì)列后，項(xiàng)目 2 成為新的頭。
- queue.dequeue(); // => 7
2.3 Peek操作
Peek操作讀取隊(duì)列的開頭，而不會(huì)更改隊(duì)列。
項(xiàng)目 7 是上圖中隊(duì)列的頭部，Peek操作只是返回隊(duì)列的頭部——第 7 項(xiàng)，而不修改隊(duì)列。
- queue.peek(); // => 7
2.4 隊(duì)列長(zhǎng)度
長(zhǎng)度操作計(jì)算隊(duì)列包含多少個(gè)項(xiàng)目。
圖片中的隊(duì)列有4個(gè)項(xiàng)目：4、6、2 和 7。因此，隊(duì)列長(zhǎng)度為 4。
- queue.length; // => 4
2.5 隊(duì)列操作時(shí)間復(fù)雜度
關(guān)于所有的隊(duì)列操作--enqueue、dequeue、peek和length——重要的是，所有這些操作必須在恒定的時(shí)間內(nèi) O(1) 執(zhí)行。
恒定的時(shí)間 O(1) 意味著無(wú)論隊(duì)列的大小(它可以有10個(gè)或100萬(wàn)個(gè)項(xiàng)目)：enqueue、dequeue、peek和length操作必須在相對(duì)相同的時(shí)間內(nèi)執(zhí)行。
3.在JavaScript中實(shí)現(xiàn)隊(duì)列
讓我們看一下隊(duì)列數(shù)據(jù)結(jié)構(gòu)的可能實(shí)現(xiàn)，同時(shí)維持所有操作必須在恒定時(shí)間 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)建隊(duì)列實(shí)例的方式。
調(diào)用 queue.enqueue(7) 方法會(huì)將項(xiàng)目7排隊(duì)到隊(duì)列中。
queue.dequeue() 從隊(duì)列中去隊(duì)列一個(gè)頭部的項(xiàng)目，而 queue.peek() 只是Peek頭部的項(xiàng)目。
最后，queue.length 顯示隊(duì)列中還有多少項(xiàng)目。
隊(duì)列方法的復(fù)雜性
Queue類的 queue()、dequeue()、peek() 和 length() 方法僅使用：
屬性訪問(wèn)器（例如 this.items[this.headIndex] ），
或執(zhí)行算術(shù)操作（例如 this.headIndex++ ）
因此，這些方法的時(shí)間復(fù)雜度是恒定時(shí)間 O(1)。
總結(jié)
隊(duì)列數(shù)據(jù)結(jié)構(gòu)是“先入先出”（FIFO）的一種：最早入隊(duì)的項(xiàng)是最早出隊(duì)的項(xiàng)。
隊(duì)列有2個(gè)主要操作：入隊(duì)和出隊(duì)。另外，隊(duì)列可以具有輔助操作，例如Peek和長(zhǎng)度。
所有隊(duì)列操作必須在恒定時(shí)間 O(1) 中執(zhí)行。
原文：https://dmitripavlutin.com/javascript-queue/
作者：Dmitri Pavlutin
