數據結構之Queue | 讓我們一塊來學習數據結構

前面的兩篇文章分別介紹了List和Stack，下面讓我們一起來學習Queue

隊列的概況

隊列是一種列表，不同的是隊列只能在隊尾插入元素，在隊首刪除元素。隊列用於存儲按順序排列的數據，先進先出，這點和棧不一樣，在棧中，最後入棧的元素反而被優先處理。可以將隊列想像成在銀行前排隊的人群，排在最前面的人第一個辦理業務，新來的人只能在後面排隊，直到輪到他們為止。

隊列是一種先進先出（First-In-First-Out，FIFO）的數據結構。隊列被用在很多地方，比如提交作業系統執行的一系列進程、列印任務池等，一些模擬系統用隊列來模擬銀行或雜貨店裡排隊的顧客。

基礎隊列

隊列的兩種主要操作是：向隊列中插入新元素和刪除隊列中的元素。插入操作也叫做入隊，刪除操作也叫做出隊。入隊操作在隊尾插入新元素，出隊操作刪除隊頭的元素。下圖演示了這兩個操作。

queue.png
隊列的另外一項重要操作是讀取隊頭的元素。這個操作叫做 peek()。該操作返回隊頭元素，但不把它從隊列中刪除。除了讀取隊頭元素，我們還想知道隊列中存儲了多少元素，可以使用 length 屬性滿足該需求；要想清空隊列中的所有元素，可以使用 clear() 方法來實現。

使用數組來實現隊列看起來順理成章。JavaScript 中的數組具有其他程式語言中沒有的優點，數組的 push() 方法可以在數組末尾加入元素，shift() 方法則可刪除數組的第一個元素。

構建Queue類

class Queue {
    constructor() {
        this.dataStore = [];
    }
    enqueue(element) {
        this.dataStore.push(element);
    }
    dequeue() {
        return this.dataStore.shift();
    }
    front() {
        return this.dataStore[0];
    }
    back() {
        return this.dataStore[this.dataStore.length - 1];
    }
    empty() {
        return this.dataStore.length === 0;
    }
    toString() {
        return this.dataStore.toString();
    }
    length() {
        return this.dataStore.length;
    }
}

優先隊列

在一般情況下，從隊列中刪除的元素，一定是率先入隊的元素。但是也有一些使用隊列的應用，在刪除元素時不必遵守先進先出的約定。這種應用，需要使用一個叫做優先隊列的數據結構來進行模擬。

從優先隊列中刪除元素時，需要考慮優先權的限制。比如醫院急診科的候診室，就是一個採取優先隊列的例子。當病人進入候診室時，分診護士會評估患者病情的嚴重程度，然後給一個優先順序程式碼。高優先順序的患者先於低優先順序的患者就醫，同樣優先順序的患者按照先來先服務的順序就醫。

先來定義存儲隊列元素的對象，然後再構建我們的優先隊列系統：

class Patient {
    constructor(name, code) {
        this.name = name;
        this.code = code;
    }
}

變數 code 是一個整數，表示患者的優先順序或病情嚴重程度(code越小代表病情越嚴重)。

下面需要重新定義Queue類的dequeue方法，使其刪除隊列中擁有最高優先順序的元素。新的 dequeue()方法遍歷隊列的底層存儲數組，從中找出優先碼最低的元素，然後使用數組的 splice()方法刪除優先順序最高的元素。新的dequeue()方法定義如下所示：

dequeue() {
    let priority = this.dataStore[0];
    for (const i = 0, len = this.dataStore.length; i < len; i++){
        if (this.dataStore[i].code < priority) {
            priority = i;
        }
    }
    return this.dataStore.splice(priority, 1);
}

最後，需要定義 toString() 方法來顯示 Patient 對象。

toString() {
    let retStr = "";
    for (var i = 0; i < this.dataStore.length; ++i) {
        retStr += `${this.dataStore[i].name} code: ${this.dataStore[i].code}\n`;
    }
    return retStr;
}

測試優先隊列

企业微信截图_20210426173457.png

雙端隊列

雙端隊列（deque，或稱double-ended queue）是一種允許我們同時從前端和後端添加和移除元素的特殊隊列。

在電腦科學中，雙端隊列的一個常見應用是存儲一系列的撤銷操作。每當用戶在軟體中進行了一個操作，該操作就會被存在雙端隊列中。當用戶點擊撤銷按鈕時，該操作會從雙端隊列中彈出，表示它被從後端移除了一個了。在進行了一定數量的操作後，最先進行的操作會被從雙端隊列的前端移除。由於雙端隊列同時遵循了先入先出和後入先出的原則，可以說是它是把隊列和棧相結合的一種數據結構。

創建Deque類

class Deque {
    constructor() {
        this.dataStore = [];
    }
    addFront(element) {
        if(this.empty()){
            this.addBack(element)
        }else{
            this.dataStore.unshift(element);
        }
    }
    addBack(element) {
        this.dataStore.push(element);
    }
    removeFront() {
        return this.dataStore.shift();
    }
    removeBack() {
        return this.dataStore.pop();
    }
    front() {
        return this.dataStore[0];
    }
    back() {
        return this.dataStore[this.dataStore.length - 1];
    }
    empty() {
        return this.dataStore.length === 0;
    }
    toString() {
        return this.dataStore.toString();
    }
    length() {
        return this.dataStore.length;
    }
}

測試Deque類的程式碼

QQ20210426-202023@2x.png

實際應用-->迴文字元串的判斷

迴文是指這樣一種現象：一個單詞、短語或數字，從前往後寫和從後往前寫都是一樣的。 比如，單詞「dad」、「racecar」就是迴文；如果忽略空格和標點符號，下面這個句子也是回 文，「A man, a plan, a canal: Panama」；數字 1001 也是迴文。

在之前的文章中是使用棧(Stack)這一數據結構，其實迴文字元串字型大小的判斷方法是使用雙端隊列(Deque)來實現。

function isPalindrome(word) {
    if (typeof word !== "string") {
        throw TypeError(`參數不是string類型`);
    }
    let tmp = new Deque();
    for (let element of word) {
        tmp.addBack(element);
    }
    while (tmp.length() > 1) {
        if (tmp.removeFront() !== tmp.removeBack()) {
            return false;
        }
    }
    return true;
}

console.log(isPalindrome("racecar")) // true
console.log(isPalindrome("hello")) // false

參考資料

  • 數據結構與演算法JavaScript描述
  • 學習JavaScript數據結構與演算法 第3版
Tags:

VirMach 便宜 VPS