Javascript數據結構之棧和隊列詳解

Posted on by

前言

我們實際開發中，比較熟悉的數據結構是數組。一般情況下夠用瞭。但如果遇到復雜的問題，數組就捉襟見肘瞭。在解決一個復雜的實際問題的時候，選擇一個更為合適的數據結構，是順利完成這些任務的前提基礎。所以好好瞭解學習數據結構，對我們高效的解決問題非常重要。

下面我總結瞭兩種我們在實際開發過程中比較常用到的數據結構，簡單整理說明一下，希望對大傢有幫助。

棧（stack）

棧是一種具有 「後入先出」(Last-in-First-Out，LIFO) 特點的抽象數據結構。

瞭解棧的樣子，最常見的例子如：一摞盤子、一個壓入子彈的彈夾。還有比如我們上網使用的瀏覽器，都有『後退』、『前進』按鈕。後退操作，就是把當前正在瀏覽的頁面（棧頂）地址出棧，倒退回之前的地址。我們使用的編輯類的軟件，比如 IDE，Word，PhotoShop，他們的撤銷（undo）操作，也是用棧來實現的，軟件的具體實現代碼可能會有比較大的差異，但原理是一樣的。

由於棧後入先出的特點，每次隻能操作棧頂的元素，任何不在棧頂的元素，都無法訪問。要訪問下面的元素，先得拿掉上面的元素。所以它是一種高效的數據結構。

用 Javascript 實現一個棧，通常我們用數組就可以。可以做一個簡單的封裝。

棧實現

棧通常需要實現下面常用功能：

  • push（插入新元素，並讓新元素成為棧頂元素）
  • pop（棧頂元素出棧，並返回棧頂元素）
  • peek（想知道棧最後添加的是哪個，用這個方法。返回棧頂元素，不出棧。是個輔助方法）
  • clear（清空棧）
  • isEmpty（若棧為空，返回 true，否則返回 false）
  • size（返回棧元素個數）
class Stack {
    constructor() {
        this.items = [];
    }
    push(item) {
        this.items.push(item);
    }
    pop() {
        return this.items.pop();
    }
    peek() {
        return this.items[this.items.length - 1];
    }
    clear() {
        this.items = [];
    }
    isEmpty() {
        return this.items.length === 0;
    }
    size() {
        return this.items.length;
    }
}
const stack = new Stack();
stack.push('c++');
stack.push('swift');
stack.push('python');
stack.push('javascript');
console.log(stack.isEmpty()); // false
console.log(stack.size());    // 4
console.log(stack.peek());    // javascript
const removedItem = stack.pop();
console.log(removedItem);     // javascript
console.log(stack.peek());    // python
stack.clear();
console.log(stack.isEmpty()); // true
console.log(stack.size());    // 0

解決實際問題

那麼棧如何應用解決實際問題，下面是一個例子。

一個十進制轉換為二進制的例子：

function transitionToBin(decNumber) {
    const stack = new Stack();
    do {
        // 每次循環計算出的低位值，依次入棧
        stack.push(decNumber % 2);
        decNumber = Math.floor(decNumber / 2);
    } while(decNumber > 0);
    let result = '';
    // 此時，stack 中存放的是轉換後二進制值，棧頂是高位，依次向下。
    while (stack.size() > 0) {
        // 從棧頂的高位依次出棧，拼接到顯示結果中
        result += stack.pop();
    }
    return result;
}
const binNumber = transitionToBin(321);
console.log('binNumber: ', binNumber);

棧的另外應用

棧也被用於內存保存變量和方法調用。函數調用的時候壓棧，return 結果的時候，出棧。比如我們經常用的遞歸 （recursion） ，就是棧應用的例子。

比如下面一個計算階乘的例子：

function factorial(n) {
    return n > 1 ? n * factorial(n - 1) : n;
}
console.log(factorial(4));

簡單隊列（Queue）

除瞭棧，隊列也是一種常用的數據結構。隊列是由順序元素組成的線性數據結構，又不同於棧 （Last-in-First-Out，LIFO） ，他遵循的是先進先出（First-In-First-Out，FIFO） 。

隊列在隊尾添加新元素，在頂部移除元素。

現實中，最常見的隊列例子就是排隊。

計算機中，隊列應用也相當廣泛。例如計算機 CPU 作業調度（Job Scheduling）、外圍設備聯機並發（spooling）、樹和圖的廣度優先搜索（BFS）

隊列實現

一個隊列數據結構，主要是要實現兩個操作：

  • enqueue 把一個新元素推入隊列
  • dequeue 從隊列中移除一個已有元素

我們創建一個類來封裝一個隊列。我們可以使用 javascript 原生的數組來存儲裡面的數據內容，和 javascript 自帶的函數來實現隊列的操作。

class Queue {
    constructor() {
        this.items = [];
    }
    // 推入
    enqueue(item) {
        this.items.push(item);
    }
    // 移除
    dequeue() {
        return this.items.shift();
    }
    // 隊列頭元素
    peek() {
        return this.items[0];
    }
    // 為空判斷
    isEmpty() {
        return this.items.length === 0;
    }
    size() {
        return this.items.length;
    }
}

隊列應用 – 樹的廣度優先搜索（breadth-first search，BFS）

我們在遍歷一顆樹的時候，可以使用棧思路進行深度優先遍歷，也可以采用隊列的思路，廣度優先遍歷。假設我們有下面這樣一個樹形的數據結構，我們查找它所有的節點值。

const treeData = {
     node: {
         value: 12,
         children: [{
             value: 30,
             children: [{
                 value: 22,
                 children: null
             }, {
                 value: 10,
                 children: [{
                     value: 5,
                     children: null
                 }, {
                     value: 4,
                     children: null
                 }]
             }]
         }, {
             value: 6,
             children: [{
                 value: 8,
                 children: null
             }, {
                 value: 70,
                 children: null
             }]
         }]
     }
 };

我們用隊列進行廣度優先的思路來遍歷。代碼和示意圖如下：

function bfs(tree) {
    // 準備一個空的隊列
    const queue = new Queue();
    queue.enqueue(tree);
    // 一個用於顯示結果的數組
    const result = [];
    do {
        // 出隊列
        let node = queue.dequeue();
        result.push(node.value);
        if (node.children && node.children.length > 0) {
            node.children.forEach(sub => {
                queue.enqueue(sub);
            });
        }
    } while (queue.size() > 0);
    // 顯示遍歷結果
    console.log('result:', result.join(', '));
}
bfs(treeData.node);
// result: 12, 30, 6, 22, 10, 8, 70, 5, 4

優先隊列

在實際情況中，有的隊列需要一些特殊的處理方式，出隊列規則的不一定是簡單粗暴的最早進入隊列最先出。 比如：

  • 醫院對病人的分診，重癥的優先給予治療
  • 我們銷售某件商品時，可以按照該商品入庫的進貨價作為條件，進貨價高的優先拿出銷售。

於是，就有瞭優先隊列。優先隊列是普通隊列的一種擴展，它和普通隊列不同的在於，隊列中的元素具有指定的優先級別（或者叫權重）。 讓優先級高的排在隊列前面，優先出隊。優先隊列具有隊列的所有特性，包括基本操作，隻是在這基礎上添加瞭內部的一個排序。

優先隊列實現

因為設置瞭一些規則，我們可以用順序存儲的方式來存儲隊列，而不是鏈式存儲。換句話說，所有的節點都可以存儲到數組中。

滿足上面條件，我們可以利用線性數據結構的方式實現，但時間復雜度較高，並不是最理想方式

線性數據結構實現優先隊列

我們要實現優先隊列，就會有兩種方法。

  • 第一種，就是插入的時候，不考慮其他，就在隊列末尾插入。而移除的時候，則要根據優先級找出隊列中合適的元素移除。
  • 第二種是，插入元素的時候，根據優先級找到合適的放置位置，而移除的時候，直接從隊列前面移除。

下面以第二種情況為例，實現一個優先隊列：

class QItem {
    constructor(item, priority) {
        this.item = item;
        this.priority = priority;
    }
    toString() {
        return `${this.item} - ${this.priority}`;
    }
}
class PriorityQueue {
    constructor() {
        this.queues = [];
    }
    // 推入
    enqueue(item, priority) {
        const q = new QItem(item, priority);
        let contain = false;
        // 這個隊列本身總是按照優先級，從大到小的
        // 所以找到第一個比要插入值小的那個位置
        for (let i = 0; i < this.queues.length; i++) {
            if (this.queues[i].priority < q.priority) {
                this.queues.splice(i, 0, q);
                contain = true;
                break;
            }
        }
        // 都比它大，放最後
        if (!contain) {
            this.queues.push(q);
        }
    }
    // 移除
    dequeue() {
        return this.queues.shift();
    }
    // 隊列頭元素
    peek() {
        return this.queues[0];
    }
    isEmpty() {
        return this.queues.length === 0;
    }
    size() {
        return this.queues.length;
    }
}
const queue = new PriorityQueue();
queue.enqueue('K40', 3100);
queue.enqueue('K50', 5000);
queue.enqueue('K10', 6100);
queue.enqueue('K10', 6000);
queue.enqueue('K10', 5600);
queue.enqueue('K50', 4600);
queue.enqueue('K40', 5900);
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
/*
QItem { item: 'K10', priority: 6100 }
QItem { item: 'K10', priority: 6000 }
QItem { item: 'K40', priority: 5900 }
QItem { item: 'K10', priority: 5600 }
QItem { item: 'K50', priority: 5000 }
QItem { item: 'K50', priority: 4600 }
QItem { item: 'K40', priority: 3100 }
*/

Heap（堆）數據結構實現優先隊列

上面是簡單的使用一個線性數據結構，實現瞭一個優先隊列。我們也可以用實現。這種堆數據存儲的時候也是一個線性的，隻是這些數據的存放位置有一定規則。

堆可以理解為可以迅速找到一堆數中的最大或者最小值的數據結構

堆是具有特殊特征的完全二叉樹（也叫二叉堆）。

二叉堆特點：

  • 它是一個完全二叉樹（complete binary tree） 的數據結構。所謂完全二叉樹（complete binary tree）,就是整個二叉樹，除瞭底層的葉子節點，其他的層都是填滿的，而且底層的葉子節點，從左到右不能有空的。（這樣一個完全二叉樹就能使用 Array 這種線性結構來存儲）
  • 大頂堆（Max heap） ：父節點的值大於或者等於子節點的值，堆頂是這個堆的最大元素
  • 小頂堆（Min heap） ：父節點的值小於或者等於子節點的值，堆頂是這個堆的最小元素

因為完全二叉樹的特性，我們可以用一個數組來存儲二叉堆

二叉堆是實現堆排序和優先隊列的基礎。二叉堆常用的應用場景就是優先隊列，它處理最大、最小值效率很高。同時堆排序算法也用到瞭二叉堆。

代碼實現一個二叉堆

二叉堆的插入和刪除操作比較復雜，我們用 max-heap 舉例說明。

插入（enqueue）操作

  • 新元素一律先插入到堆的尾部
  • 依次向上調整整個堆的結構（一直到根即可）

HeapifyUp

刪除（dequeue）操作

  • 取出頂部元素（因為它永遠是最大那個）
  • 將尾元素替換到頂部（先不用管它的大小）
  • 依次從根部向下調整整個堆的結構（一直到堆尾即可）

HeapifyDown

下面是一個 max-heap 的實現。comparator 函數裡面修改一下，就可以變成一個 min-heap

class Heap {
    constructor(comparator = (a, b) => a - b) {
        this.arr = [];
        this.comparator = (iSource, iTarget) => {
            const value = comparator(this.arr[iSource], this.arr[iTarget]);
            if (Number.isNaN(value)) {
                throw new Error(`Comparator should evaluate to a number. Got ${value}！`);
            }
            return value;
        }
    }
    enqueue(val) {
        // 插入到末尾
        this.arr.push(val);
        // 向上冒泡，找到合適位置
        this.siftUp();
    }
    dequeue() {
        if (!this.size) return null;
        const val = this.arr.shift();
        const rep = this.arr.pop();
        this.arr.splice(0, 0, rep);
        this.siftDown();
    }
    get size() {
        return this.arr.length;
    }
    siftUp() {
        // 新元素索引
        let index = this.size - 1;
        // 根據完全二叉樹的規則，這裡我們可以依據元素索引index的值，獲得他對應父節點的索引值
        const parent = (i) => Math.floor((i - 1) / 2);
        if (parent(index) >= 0 && this.comparator(parent(index), index) < 0) {
            // 如果父節點存在，並且對比值比當前值小，則交互位置
            this.swap(parent(index), index);
            index = parent(index);
        }
    }
    siftDown() {
        let curr = 0;
        const left = (i) => 2 * i + 1;
        const right = (i) => 2 * i + 2;
        const getTopChild = (i) => {
        // 如果右節點存在，並且右節點值比左節點值大
        return (right(i) < this.size && this.comparator(left(i), right(i)) < 0)
                ? right(i) : left(i);
    };
    // 左節點存在，並且當前節點的值，小於子節點中大的那個值，交換
    while (left(curr) < this.size && this.comparator(curr, getTopChild(curr)) < 0) {
        const next = getTopChild(curr);
        this.swap(curr, next);
        curr = next;
        }
    }
    // 交換位置
    swap(iFrom, iTo) {
        [this.arr[iFrom], this.arr[iTo]] = [this.arr[iTo], this.arr[iFrom]];
    }
}
const heap = new Heap();
heap.enqueue(56);
heap.enqueue(18);
heap.enqueue(20);
heap.enqueue(40);
heap.enqueue(30);
heap.enqueue(22);
console.log('heapify: ', heap.arr.join(', '));
heap.dequeue();
console.log('step 1: ', heap.arr.join(', '));
heap.dequeue();
console.log('step 2: ', heap.arr.join(', '));
heap.dequeue();
console.log('step 3: ', heap.arr.join(', '));
// heapify:  56, 40, 22, 18, 30, 20
// step 1:  40, 30, 22, 18, 20
// step 2:  30, 20, 22, 18
// step 3:  22, 20, 18

如上面代碼所示，數據進入隊列是無序的，但在出隊列的時候，總是能找到最大那個。這樣也實現瞭一個優先隊列。

小頂堆在 React Scheduler 事務調度的包應用

Scheduler 存在兩個隊列，timerQueue（未就緒任務隊列） 和 taskQueue（就緒任務隊列）。當有新的未就緒任務被註冊，就會 push 到 timerQueue 中，並根據開始時間重新排列任務順序。

push 方法是在一個叫 schedulerMinHeap.js 的文件中基於最小堆（min-heap）來實現的。schedulerMinHeap 源碼

export function push(heap: Heap, node: Node): void {
    const index = heap.length;
    heap.push(node);
    siftUp(heap, node, index);
}

看到代碼中，在 push 之後，調用瞭 siftUp 來重新整理順序

function siftUp(heap, node, i) {
    let index = i;
    while (index > 0) {
        const parentIndex = (index - 1) >>> 1;
        const parent = heap[parentIndex];
        if (compare(parent, node) > 0) {
            // The parent is larger. Swap positions.
            heap[parentIndex] = node;
            heap[index] = parent;
            index = parentIndex;
        } else {
            // The parent is smaller. Exit.
            return;
        }
    }
}

這裡計算 parentIndex 是用瞭位移的方法（等價於除以 2 再去尾），帥！

最後

數據結構還有很多內容，這裡隻是簡單的說瞭兩種，為瞭能引導大傢去學習其他更復雜的數據結構知識。真正的掌握數據結構，並把它應用於實際工作中，對我們非常重要。

到此這篇關於Javascript數據結構之棧和隊列的文章就介紹到這瞭,更多相關js棧和隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：