引言

yocto-queue是一個(gè)微型隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，根據(jù)作者的介紹，如果在你一個(gè)數(shù)據(jù)量很大的數(shù)組上，大量的操作Array.push和Array.shift，那么你可以考慮使用yocto-queue來替代Array。

因?yàn)?code>Array.shift的時(shí)間復(fù)雜度是O(n)，而Queue.dequeue的時(shí)間復(fù)雜度是O(1)，這對于大量的數(shù)據(jù)來說，性能上的提升是非常明顯的。

時(shí)間復(fù)雜度和空間復(fù)雜度

學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們經(jīng)常會聽到時(shí)間復(fù)雜度和空間復(fù)雜度，這兩個(gè)概念是什么呢？

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是指一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，它是一個(gè)函數(shù)，這個(gè)函數(shù)的變量是問題規(guī)模的函數(shù)；

通常會使用大O符號來表示時(shí)間復(fù)雜度，比如O(n)，O(n^2)，O(logn)等等，這就是大 O 表示法（Big O notation）。

O代表的是算法的漸進(jìn)時(shí)間復(fù)雜度（asymptotic time complexity），也就是說，隨著問題規(guī)模的增大，算法的執(zhí)行時(shí)間的增長率和O中的函數(shù)相同，稱作漸進(jìn)時(shí)間復(fù)雜度。

O(1)表示算法的執(zhí)行時(shí)間與問題規(guī)模無關(guān)，也就是說，不管問題規(guī)模有多大，算法執(zhí)行所耗費(fèi)的時(shí)間都是一樣的，這種算法稱為時(shí)間復(fù)雜度為常數(shù)階的算法。

O(n)表示算法的執(zhí)行時(shí)間與問題規(guī)模成正比，也就是說，隨著問題規(guī)模的增大，算法執(zhí)行所耗費(fèi)的時(shí)間也隨之增大，這種算法稱為時(shí)間復(fù)雜度為線性階的算法。

O(n^2)表示算法的執(zhí)行時(shí)間與問題規(guī)模成平方比，也就是說，隨著問題規(guī)模的增大，算法執(zhí)行所耗費(fèi)的時(shí)間呈二次方增長，這種算法稱為時(shí)間復(fù)雜度為平方階的算法。

通過上面的介紹，我們可以將O比喻成函數(shù)，O(1)就是一個(gè)常數(shù)函數(shù)，O(n)就是一個(gè)線性函數(shù)，O(n^2)就是一個(gè)平方函數(shù)，O(logn)就是一個(gè)對數(shù)函數(shù)。

說了這么多概念性的問題，不如直接來看看代碼；

例如，我們有一個(gè)數(shù)組，我們要遍歷這個(gè)數(shù)組，然后將數(shù)組中的每個(gè)元素都乘以2，那么我們可以這么寫：

function multiplyBy2(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

這段代碼的時(shí)間復(fù)雜度是O(n)，因?yàn)槲覀儽闅v了數(shù)組，所以時(shí)間復(fù)雜度就是O(n)，O代表這個(gè)函數(shù)，n代表問題規(guī)模，也就是數(shù)組的長度，組合起來就是O(n)。

再直觀一點(diǎn)，我們可以這么理解，當(dāng)數(shù)組的長度為n時(shí)，我們需要執(zhí)行n次循環(huán)，所以時(shí)間復(fù)雜度就是O(n)，用代碼表示就是：

function O(n) {
    for (let i = 0; i < n; i++) {
        // do something
    }
}
O(1); // O(1)
O(2); // O(2)
O(3); // O(3)
O(n); // O(n)

空間復(fù)雜度

空間復(fù)雜度是指一個(gè)算法執(zhí)行所耗費(fèi)的內(nèi)存空間，它是一個(gè)函數(shù)，這個(gè)函數(shù)的變量是問題規(guī)模的函數(shù)；

和時(shí)間復(fù)雜度一樣，空間復(fù)雜度也有O(1)、O(n)、O(n^2)、O(logn)等等，它們的含義和時(shí)間復(fù)雜度一樣，只不過它們是表示算法執(zhí)行所耗費(fèi)的內(nèi)存空間的增長率。

當(dāng)然空間復(fù)雜度計(jì)算的不是內(nèi)存消耗，而是變量的個(gè)數(shù)，例如冒泡排序的空間復(fù)雜度是O(1)，因?yàn)樗恍枰粋€(gè)變量temp：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

而快速排序的空間復(fù)雜度是O(logn)，因?yàn)樗枰粋€(gè)變量pivot，而且它是遞歸的，所以空間復(fù)雜度是O(logn)：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

源碼分析

上面了解了時(shí)間復(fù)雜度和空間復(fù)雜度的概念，那么我們開始正式分析yocto-queue的源碼；

• yocto-queue
• yocto-queue github1s

代碼不多，可以直接通過github1s在線閱讀，然后使用瀏覽器控制臺來查看效果；

代碼分析

先來看一下yocto-queue的使用方式：

• 安裝

npm install yocto-queue

• 使用

import Queue from 'yocto-queue';
const queue = new Queue();
queue.enqueue('??');
queue.enqueue('??');
console.log(queue.size);
//=> 2
console.log(...queue);
//=> '?? ??'
console.log(queue.dequeue());
//=> '??'
console.log(queue.dequeue());
//=> '??'

然后再來看一下yocto-queue的代碼：

/*
How it works:
`this.#head` is an instance of `Node` which keeps track of its current value and nests another instance of `Node` that keeps the value that comes after it. When a value is provided to `.enqueue()`, the code needs to iterate through `this.#head`, going deeper and deeper to find the last value. However, iterating through every single item is slow. This problem is solved by saving a reference to the last value as `this.#tail` so that it can reference it to add a new value.
*/
class Node {
    value;
    next;
    constructor(value) {
        this.value = value;
    }
}
export default class Queue {
    #head;
    #tail;
    #size;
    constructor() {
        this.clear();
    }
    enqueue(value) {
        const node = new Node(value);
        if (this.#head) {
            this.#tail.next = node;
            this.#tail = node;
        } else {
            this.#head = node;
            this.#tail = node;
        }
        this.#size++;
    }
    dequeue() {
        const current = this.#head;
        if (!current) {
            return;
        }
        this.#head = this.#head.next;
        this.#size--;
        return current.value;
    }
    clear() {
        this.#head = undefined;
        this.#tail = undefined;
        this.#size = 0;
    }
    get size() {
        return this.#size;
    }
    * [Symbol.iterator]() {
        let current = this.#head;
        while (current) {
            yield current.value;
            current = current.next;
        }
    }
}

可以直接直接粘貼到瀏覽器控制臺中運(yùn)行

構(gòu)造函數(shù)

首先來看一下Queue的構(gòu)造函數(shù)：

class Queue {
  #head;
  #tail;
  #size;
  constructor() {
    this.clear();
  }
}

一個(gè)Queue類，它有三個(gè)私有屬性：#head、#tail、#size；

在class中，如果屬性名前面加上#，表示這個(gè)屬性是私有屬性，外部是無法訪問的；

• #head：指向隊(duì)列的頭部；
• #tail：指向隊(duì)列的尾部；
• #size：隊(duì)列的長度；

然后在構(gòu)造函數(shù)中調(diào)用了this.clear()方法，這個(gè)方法的作用是清空隊(duì)列，代碼如下：

class Queue {
    clear() {
        this.#head = undefined;
        this.#tail = undefined;
        this.#size = 0;
    }
}

enqueue

接下來看一下enqueue方法：

class Queue {
    enqueue(value) {
        const node = new Node(value);
        if (this.#head) {
            this.#tail.next = node;
            this.#tail = node;
        } else {
            this.#head = node;
            this.#tail = node;
        }
        this.#size++;
    }
}

enqueue方法的作用是向隊(duì)列中添加一個(gè)元素；

首先創(chuàng)建一個(gè)Node實(shí)例，然后判斷this.#head是否存在，如果存在，說明隊(duì)列中已經(jīng)有元素了，那么就把新創(chuàng)建的Node實(shí)例添加到隊(duì)列的尾部；

如果this.#head不存在，說明隊(duì)列中還沒有元素，那么就把新創(chuàng)建的Node實(shí)例添加到隊(duì)列的頭部；

最后，隊(duì)列的長度加一；

這里使用到了一個(gè)Node類，它的作用是用來保存隊(duì)列中的元素的，代碼如下：

class Node {
    value;
    next;
    constructor(value) {
        this.value = value;
    }
}

• value：指向的是隊(duì)列中的元素；
• next：指向下一個(gè)Node實(shí)例；

dequeue

接下來看一下dequeue方法：

class Queue {
    dequeue() {
        const current = this.#head;
        if (!current) {
            return;
        }
        this.#head = this.#head.next;
        this.#size--;
        return current.value;
    }
}

dequeue方法的作用是從隊(duì)列中移除一個(gè)元素；

首先獲取隊(duì)列的頭部元素，然后判斷current是否存在，如果不存在，說明隊(duì)列中沒有元素，那么就直接返回；

如果current存在，說明隊(duì)列中有元素，那么就把隊(duì)列的頭部元素移除，然后把隊(duì)列的長度減一；

最后，返回移除的元素；

圖例

一個(gè)隊(duì)列結(jié)構(gòu)只會有兩個(gè)操作：入隊(duì)和出隊(duì)，下面通過一個(gè)圖例來說明一下；

入隊(duì)時(shí)，會把新的元素添加到隊(duì)列的尾部；

出隊(duì)時(shí)，會把隊(duì)列的頭部元素移除；

上面的圖例中，Node0表示隊(duì)列的頭部元素，Node_n表示隊(duì)列的尾部元素；

Current0表示隊(duì)列中的第一個(gè)元素，Current_n表示隊(duì)列中的最后一個(gè)元素；

在隊(duì)列中，只會關(guān)心頭部和尾部的元素，頭部的元素用于彈出隊(duì)列，尾部的元素用于添加元素；

在上面的圖例中，如果我們執(zhí)行dequeue方法，那么就會把Node0移除，然后把Node1設(shè)置為隊(duì)列的頭部元素；

上面的dequeue方法執(zhí)行完畢后，隊(duì)列的頭部元素就變成了Node1；

Node0因?yàn)闆]有任何引用指向它，所以會被垃圾回收機(jī)制回收；

如果我們執(zhí)行enqueue方法，那么就會把新的元素添加到隊(duì)列的尾部：

上面的enqueue方法執(zhí)行完畢后，隊(duì)列的尾部元素就變成了newNode；

迭代器

yocto-queue到最后還提供了一個(gè)迭代器，用于遍歷隊(duì)列中的元素；

class Queue {
    // ...
    *[Symbol.iterator]() {
        let current = this.#head;
        while (current) {
            yield current.value;
            current = current.next;
        }
    }
}

上面的代碼中，使用了一個(gè)generator函數(shù)，它會返回一個(gè)迭代器；

迭代器中，會從隊(duì)列的頭部元素開始遍歷，然后把每個(gè)元素的值返回出去；

迭代器的使用

迭代器是es6中的一個(gè)新特性，它可以用于遍歷數(shù)據(jù)結(jié)構(gòu)中的元素，使用起來也非常簡單，只需要在數(shù)據(jù)結(jié)構(gòu)上調(diào)用Symbol.iterator方法即可；

const obj = {
    [Symbol.iterator]() {
        let i = 0;
        return {
            next() {
                return {
                    value: i++,
                    done: i > 10
                };
            }
        };
    }
};
for (const item of obj) {
    console.log(item);
}

上面的代碼中，我們定義了一個(gè)對象，它的Symbol.iterator方法返回了一個(gè)迭代器；

一個(gè)迭代器是一個(gè)對象，它有一個(gè)next方法，每次調(diào)用next方法，都會返回一個(gè)對象，這個(gè)對象中包含了當(dāng)前元素的值和一個(gè)done屬性，表示是否已經(jīng)遍歷完畢；

可以使用generator函數(shù)來簡化上面的代碼：

const obj = {
    *[Symbol.iterator]() {
        let i = 0;
        while (i < 10) {
            yield i++;
        }
    }
};
for (const item of obj) {
    console.log(item);
}

上面的代碼中，我們使用了generator函數(shù)來簡化迭代器的定義；

參考：

Symbol.iterator

Generator 函數(shù)

總結(jié)

yocto-queue是一個(gè)非常簡單的隊(duì)列實(shí)現(xiàn)，它的核心是使用了鏈表來存儲數(shù)據(jù)；

鏈表的優(yōu)點(diǎn)是插入和刪除元素的時(shí)間復(fù)雜度是O(1)，但是查找元素的時(shí)間復(fù)雜度是O(n)，不過對于隊(duì)列來說，查找元素的操作是不需要的；

對比于數(shù)組，每次插入和刪除元素都需要移動元素，所以時(shí)間復(fù)雜度是O(n)，但是查找元素的時(shí)間復(fù)雜度是O(1)；

所以正如文章開頭，作者提到的，對于一個(gè)大數(shù)組來實(shí)現(xiàn)隊(duì)列，效率是非常低的，而應(yīng)該使用鏈表來實(shí)現(xiàn)（因?yàn)檫@個(gè)庫的核心實(shí)現(xiàn)就是鏈表，所以肯定優(yōu)先推薦用這個(gè)庫=）；

通過閱讀yocto-queue的源碼，我們學(xué)習(xí)到了很多：

• 時(shí)間復(fù)雜度、空間復(fù)雜度的概念
• 鏈表的實(shí)現(xiàn)
• 如何使用es6的Symbol.iterator來實(shí)現(xiàn)可迭代對象；
• 如何使用es6的generator函數(shù)來實(shí)現(xiàn)迭代器；
• 數(shù)組、隊(duì)列、鏈表的區(qū)別；

以上就是yocto queue微型隊(duì)列數(shù)據(jù)結(jié)構(gòu)源碼解讀的詳細(xì)內(nèi)容，更多關(guān)于yocto queue隊(duì)列數(shù)據(jù)結(jié)構(gòu)的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論