js 中堆、棧、隊列介紹

1. 棧（Stack）
   • 概念：
     • 棧是一種遵循后進先出（LIFO - Last In First Out）原則的數據結構。就像一摞盤子，最后放上去的盤子最先被拿走。在JavaScript中，函數調用棧就是一個典型的棧結構。當一個函數被調用時，它的執行上下文（包括局部變量、參數等信息）就會被壓入棧中，當函數執行完畢后，這個執行上下文就會從棧頂彈出。
   • 應用實例：
     • 函數調用棧：
       • 例如下面的代碼：

   function a() {console.log("Function a is called");b();
   }
   function b() {console.log("Function b is called");
   }
   a();
   

• 當a函數被調用時，a的執行上下文被壓入棧中。然后a函數內部調用b函數，此時b的執行上下文被壓入棧頂。b函數執行完畢后，它的執行上下文從棧頂彈出，接著a函數執行完畢，它的執行上下文也彈出棧。
• 表達式求值（如四則運算）：
• 考慮一個簡單的數學表達式求值器，它可以處理簡單的四則運算，例如3 + 4 * 2。可以利用棧來實現運算符優先級的計算。先將數字3和4壓入棧，當遇到運算符*時，從棧頂彈出兩個數字進行乘法運算，將結果再壓入棧。接著遇到+運算符，再從棧頂彈出兩個數字進行加法運算。

2. 堆（Heap）
   • 概念：
     • 堆是一種用于動態分配內存的數據結構，在JavaScript中主要用于存儲對象和數組（復雜數據類型）。它是一個無序的內存區域，與棧不同，堆中的內存分配和釋放是由垃圾回收機制（Garbage Collection）來管理的。JavaScript的引擎會自動分配和回收堆中的內存，程序員一般不需要手動管理堆內存。
   • 應用實例：
     • 對象存儲：
       • 例如創建一個對象：

let person = {name: "John",age: 30
};

• 這個person對象就存儲在堆中。它的內存空間是在運行時動態分配的，JavaScript引擎會在堆中找到一塊足夠大的空間來存儲這個對象的屬性和值。
• 大型數組存儲：
• 當創建一個大型數組，如let largeArray = new Array(1000000);，這個數組也是存儲在堆中的。因為棧的空間相對較小，通常用于存儲簡單數據類型（如基本數據類型的值）和函數調用相關的信息，而像這種大型的數據結構就存儲在堆中。

3. 隊列（Queue）
   • 概念：
     • 隊列是一種遵循先進先出（FIFO - First In First Out）原則的數據結構。就像排隊買票，先到的人先買票離開。在JavaScript中，可以用數組來模擬隊列的操作。
   • 應用實例：
     • 任務隊列（事件循環中的任務隊列）：
       • 在JavaScript的事件循環機制中，有宏任務隊列和微任務隊列。例如，當瀏覽器加載頁面時，用戶觸發的事件（如點擊事件）會被放入宏任務隊列。當執行一個異步操作（如setTimeout），它的回調函數也會被放入宏任務隊列。當執行棧為空時，事件循環會從宏任務隊列中取出一個任務執行。
       • 例如：

console.log("Script start");
setTimeout(() => {console.log("Timeout callback");
}, 0);
console.log("Script end");

• 在這里，console.log("Script start")先執行，然后setTimeout的回調函數被放入宏任務隊列，接著console.log("Script end")執行。當執行棧為空時，從宏任務隊列中取出setTimeout的回調函數執行。
• 數據緩沖隊列：
• 假設你正在開發一個網絡應用，從服務器接收數據。數據可能是斷斷續續地到達的，你可以使用一個隊列來緩沖這些數據。當接收到新的數據時，將其放入隊列的尾部，當需要處理這些數據時，從隊列的頭部取出數據進行處理。例如：

let dataQueue = [];
function receiveData(data) {dataQueue.push(data);
}
function processData() {if (dataQueue.length > 0) {let data = dataQueue.shift();// 在這里進行數據處理，比如解析數據等操作console.log("Processing data:", data);}
}

js中 堆、棧、隊列的區別與應用

1. 區別
   • 存儲數據類型
     • 棧：主要存儲基本數據類型（如number、string、boolean、undefined、null）以及函數調用的執行上下文。這些數據的大小是固定的，并且在編譯階段就可以確定所需的內存空間。例如，一個number類型的數據在棧中占用固定的字節數。
     • 堆：用于存儲復雜數據類型，也就是對象（包括普通對象、數組、函數等）。對象的大小不固定，因為其屬性的數量和內容可以動態變化。比如一個包含多個屬性的對象，其內存占用空間取決于屬性的數量和每個屬性值的大小。
     • 隊列：本身不用于存儲特定的數據類型，而是一種數據結構模式。在JavaScript實現中，通常可以用數組來存儲各種類型的數據，無論是基本數據類型還是對象，重點在于按照先進先出的規則操作這些數據。
   • 內存管理方式
     • 棧：內存的分配和釋放是自動的，遵循后進先出原則。當一個函數被調用時，其相關的局部變量等信息被壓入棧，函數執行結束后，這些信息就會從棧頂自動彈出，內存空間被釋放。這種自動管理機制簡單高效，但棧的空間相對較小。
     • 堆：內存的分配是動態的，由JavaScript引擎的垃圾回收機制（Garbage Collection，GC）來管理。當對象不再被引用時，垃圾回收器會在適當的時候回收其占用的內存。由于堆的內存空間較大，但管理相對復雜，垃圾回收過程可能會對性能產生一定影響。
     • 隊列：在內存管理方面沒有特殊的機制，主要依賴于所使用的存儲結構（如數組）自身的內存管理。如果用數組來模擬隊列，數組的內存分配和釋放遵循JavaScript中數組的規則。
   • 數據訪問方式
     • 棧：數據的訪問遵循后進先出原則，只能從棧頂進行插入（壓棧）和刪除（出棧）操作。就像一個只有一個開口的容器，最后放入的東西最先被取出。
     • 堆：對象在堆中的存儲位置是通過引用（指針）來訪問的。一個變量（存儲在棧中）保存了對象在堆中的內存地址，通過這個引用可以訪問和操作對象的屬性。訪問對象的屬性是通過解引用的方式，從存儲引用的變量找到堆中的對象。
     • 隊列：按照先進先出的規則訪問數據，從隊列頭部取出數據，從隊列尾部插入數據。可以將其想象成一個管道，數據從一端進入，從另一端出去。
2. 應用

• 棧的應用
  - 函數調用和遞歸：在函數調用過程中，棧用于存儲函數的執行上下文，包括局部變量、參數、返回地址等信息。遞歸函數的執行也依賴于棧，每一次遞歸調用都會將新的執行上下文壓入棧中。例如，計算階乘的遞歸函數：

function factorial(n) {if (n === 0 || n === 1) {return 1;}return n * factorial(n - 1);
}

• 表達式求值：可以利用棧來實現算術表達式求值，特別是對于包含括號和不同優先級運算符的表達式。例如，將中綴表達式轉換為后綴表達式并求值的過程中，棧可以用于存儲運算符和操作數，按照運算符的優先級和括號規則進行計算。
• 堆的應用
  • 對象和數組操作：在JavaScript中，幾乎所有的對象和數組都存儲在堆中。這包括創建和操作DOM節點（在瀏覽器環境中）、處理復雜的數據結構如樹形結構（如HTML文檔的DOM樹）、存儲和管理大量的數據集合（如數據庫查詢結果以對象數組形式存儲）。
    • 動態內存分配：當需要在運行時動態創建大量的數據結構，如游戲中的角色屬性對象、圖形繪制中的圖形對象等，這些對象的內存分配都在堆中進行。垃圾回收機制確保了在對象不再使用時釋放內存，防止內存泄漏。
  • 隊列的應用
    • 任務隊列和事件循環：在JavaScript的事件驅動編程模型中，任務隊列（宏任務隊列和微任務隊列）是核心概念。例如，setTimeout和setInterval的回調函數、用戶觸發的事件處理函數（如點擊事件、鍵盤事件等）都被放入任務隊列中，等待執行棧空閑后按照先進先出的順序執行。
    • 消息隊列和異步處理：在一些異步編程場景中，如Web Workers（在瀏覽器中實現后臺線程處理）或者Node.js中的異步I/O操作，消息隊列可以用于傳遞和處理異步任務的結果。比如，一個Web Worker完成計算任務后，將結果通過消息隊列發送回主線程進行處理。

拓展（宏任務與微任務）

1. 概念
   • 宏任務隊列（Macrotask Queue）
     • 宏任務隊列是一個用于存儲宏任務的隊列。宏任務是指那些比較大型、執行時間相對較長的任務。在瀏覽器環境或者Node.js環境中，常見的宏任務包括setTimeout、setInterval、I/O操作（如讀取文件、網絡請求）、DOM操作（如添加或刪除節點）等。這些任務按照先進先出（FIFO）的原則排隊等待執行。
     • 事件循環（Event Loop）會不斷檢查調用棧是否為空，當調用棧為空時，它會從宏任務隊列中取出一個宏任務放入調用棧中執行。例如，當設置一個setTimeout函數時，其回調函數就會被放入宏任務隊列中，等待合適的時機執行。
   • 微任務隊列（Microtask Queue）
     • 微任務隊列用于存儲微任務。微任務通常是一些比較小的、執行速度相對較快的任務。在JavaScript中，常見的微任務包括Promise的then/catch/finally回調、MutationObserver（用于觀察DOM變化）回調、queueMicrotask函數（用于手動添加微任務）等。
     • 微任務隊列的優先級高于宏任務隊列。當一個宏任務執行完畢后，在執行下一個宏任務之前，事件循環會先檢查微任務隊列是否為空。如果微任務隊列中有任務，就會依次執行這些微任務，直到微任務隊列清空后，才會從宏任務隊列中取出下一個宏任務執行。
2. 工作流程示例
   • 假設我們有以下代碼：

console.log('Script start');
setTimeout(() => {console.log('SetTimeout callback');
}, 0);
Promise.resolve().then(() => {console.log('Promise then callback');
});
console.log('Script end');

• 執行過程如下：
  • 首先執行console.log('Script start')，輸出Script start。
  • 遇到setTimeout，其回調函數被放入宏任務隊列。
  • 遇到Promise.resolve().then()，其回調函數被放入微任務隊列。
  • 執行console.log('Script end')，輸出Script end。
  • 此時當前宏任務（主代碼塊）執行完畢，事件循環檢查微任務隊列，發現有任務，執行Promise的then回調函數，輸出Promise then callback。
  • 微任務隊列清空后，事件循環從宏任務隊列中取出setTimeout的回調函數并執行，輸出SetTimeout callback。

3. 應用場景
   • 微任務隊列應用場景
     • 異步操作的順序保證：Promise廣泛用于處理異步操作，通過微任務隊列可以確保Promise的后續操作（then、catch、finally）按照正確的順序執行。例如，在一系列連續的Promise操作中，后一個Promise的then回調可以在前一個Promise完成后立即執行，保證了異步操作的連貫性。
     • DOM更新的優化：MutationObserver利用微任務隊列來處理DOM的變化觀察。當DOM發生變化時，MutationObserver的回調函數作為微任務執行。這使得DOM更新可以在當前宏任務執行完所有同步操作之后、下一個宏任務開始之前進行處理，避免了不必要的DOM重繪和回流，提高了性能。
   • 宏任務隊列應用場景
     • 延遲執行和定時任務：setTimeout和setInterval是典型的宏任務應用，用于在指定的延遲時間后執行任務或者周期性地執行任務。例如，在網頁中實現一個定時刷新數據的功能，或者在一定延遲后顯示一個提示信息，都可以使用setTimeout將相應的任務放入宏任務隊列。
     • I/O操作和長時間任務：在Node.js中，讀取文件、網絡請求等I/O操作通常作為宏任務。這些任務可能需要較長的時間來完成，將它們放入宏任務隊列可以讓其他任務（如處理用戶輸入、執行一些快速的計算等）在等待I/O完成的過程中繼續執行，提高系統的整體效率。

Web Workers

1. Web Workers概念

   • Web Workers是HTML5提供的一種在后臺線程中運行腳本的機制。在傳統的JavaScript編程中，所有的腳本都在單線程（主線程）中運行，這意味著如果一個任務需要花費很長時間，如復雜的計算或者大量的數據處理，會阻塞主線程，導致頁面無響應（例如，瀏覽器的UI凍結，用戶無法進行交互操作）。Web Workers允許你將一些耗時的任務放在獨立于主線程的后臺線程中執行，這樣主線程可以繼續響應用戶的操作，從而提高頁面的性能和用戶體驗。
   • Web Workers通過消息傳遞機制與主線程進行通信。它不能直接訪問DOM元素，因為DOM操作不是線程安全的，多個線程同時操作DOM可能會導致不可預測的錯誤。每個Web Worker都有自己的全局對象（self），這個全局對象與主線程的window對象不同，它沒有document、window等與DOM相關的屬性。

2. 應用場景

   • 復雜計算任務
     • 在一些需要進行大量數學計算的場景中，如數據加密/解密、圖形渲染中的數學計算（例如3D圖形的光線追蹤算法）、金融數據計算（如風險評估模型）等。這些計算可能會花費大量時間，如果在主線程中進行，會導致頁面卡頓。使用Web Workers可以將這些計算任務放在后臺線程進行，不影響主線程的正常運行。
   • 數據處理任務
     • 當需要處理大量的數據，如大數據集的排序、過濾、分析等。例如，在一個數據分析Web應用中，用戶上傳一個包含大量數據點的文件，需要對這些數據進行統計分析。可以使用Web Workers在后臺處理這些數據，同時主線程可以更新進度條或者響應用戶的其他操作。
   • 多任務并發處理
     • 對于一些可以并行處理的任務，比如同時從多個不同的服務器獲取數據（如多圖加載）或者同時進行多個獨立的計算任務。通過創建多個Web Workers，可以并發地處理這些任務，加快整體任務的完成速度。

3. 實例

   • 計算斐波那契數列（復雜計算任務）
     • 主線程代碼（index.html）：

<!DOCTYPE html>
<html>
<head><title>Web Workers Fibonacci Example</title>
</head>
<body><p>計算斐波那契數列</p><input type="number" id="inputNumber" placeholder="輸入斐波那契數列的項數"><button id="calculateButton">計算</button><div id="result"></div><script>const calculateButton = document.getElementById('calculateButton');const resultDiv = document.getElementById('result');const inputNumber = document.getElementById('inputNumber');calculateButton.addEventListener('click', function () {const worker = new Worker('worker.js');const n = parseInt(inputNumber.value);worker.addEventListener('message', function (event) {resultDiv.textContent = '斐波那契數列的第' + n +'項是：' + event.data;});worker.postMessage(n);});</script>
</body>
</html>

• Web Worker代碼（worker.js）：

self.addEventListener('message', function (e) {const n = e.data;function fibonacci(n) {if (n === 0 || n === 1) {return n;}let a = 0, b = 1, temp;for (let i = 2; i <= n; i++) {temp = a + b;a = b;b = temp;}return b;}self.postMessage(fibonacci(n));
});

• 在這個例子中，當用戶點擊“計算”按鈕時，主線程創建一個Web Worker，并將用戶輸入的斐波那契數列的項數發送給Web Worker。Web Worker在后臺線程中計算斐波那契數列的指定項，計算完成后將結果發送回主線程。主線程收到結果后，將其顯示在頁面上。整個計算過程不會阻塞主線程，用戶可以在計算過程中繼續與頁面進行交互。