圖片來源
今天要來討論堆疊(Stack)和佇列(Queue)的基本觀念，之前和朋友交換面試心得時，很常聽到面試官考到，就以前端領域來說這個題目是常見的，網路上應該都可以找到很多相關資訊。當你了解stack 和 queue 是什麼，對 JS 的非同步也會比較有概念

▌堆疊(Stack)是什麼？

堆疊是一種具有順序性的資料結構，有以下兩種特性（存取方式）：

• 後進先出（Last In First Out, LIFO）：最後放的資料會最先被取出
• 先進後出（First In Last Out, FILO）：最先放的資料會最後被取出

把堆疊儲存資料的方式看成上面這張插收據、紙張的插單器，只會進行兩個動作，「Push」在最上面插入新的紙、「Pop」撕掉最上面的紙。只允許資料在單一位置端增加或減少，並且沒有 index ，所以沒有辦法直接訪問

示意圖 圖片取自維基百科

javaScript 就有內建實作堆疊的方法，push 會將一個或多個元素添加到陣列的末尾，而 pop 用於刪除陣列的最後一個元素

let stack = [];
// 存入堆疊(push)
stack.push("a");
stack.push("b");
stack.push("c");

// 從堆疊取出(pop)
let c = stack.pop();
let b = stack.pop();
let a = stack.pop();

▪ 堆疊的應用

我們可以利用一維陣列（Array）和鏈接串列（Linked List）來實作「堆疊」。以下是幾個應用情境

• 函式呼叫（Function Call）時
  又可叫「呼叫堆疊」（Call Stack），注意！這裡的呼叫是指呼叫函式時所使用的堆疊，而不是去呼叫一個堆疊喔！系統需要追蹤每個function的執行狀態，包括該 function 的本地變數、執行位置和返回點（即 function 完成後應該返回的位置）。這種函數執行狀態的追蹤通常是使用堆疊（Stack）來實現的

• 遞迴（Recursive）
  堆疊保存當前遞迴調用的狀態，以便在結束時能夠恢復原本狀態

• 瀏覽某個網頁時，可以按下「上一頁」一直返回

• 記錄操作的歷史記錄
  平常我們在用 command + Z（Ctrl + Z）恢復先前操作時，就是堆疊的概念，每按一次command + Z，就會從抹除最後一個操作記錄！堆疊是一個非常靈活的資料結構，可以用於許多不同的情境中，以解決各種問題

以下附上幾個 Leecode 與 stack 有關的題目：

1. 有效的括號（Valid Parentheses）
   這題要用堆疊來檢查括號是否是一致成對的

2. 簡化路徑（Simplify Path)
   這題需要使用堆疊來處理路徑中的 "." 和 ".."

▌佇列(Queue)

圖片來源

佇列又稱「隊列」，跟堆疊一樣是一個有順序性的資料結構，不過新增與刪除發生在串列的兩端。新增的端點稱為「尾端」（Rear, Tail, Back），只能在佇列的末端才能進行，在佇列裡新增元素，在計算機領域中又稱為 「Enqueue」。「刪除」的端點稱為前端（Front），只能在佇列的開頭才能進行！而移除佇列中的元素又稱為「Dequeue」。具有先進先出（First In First Out，FIFO）的特性，跟 stack 一樣都沒有 index

▪ 佇列的應用

實作上，經常以陣列或鏈結串列（Linked list）來實現。可以把佇列的概念想像成是排隊！當多個人排隊等待服務時，第一個到達的就會先被服務到，越後面來的，就越慢服務到。在軟體開發中，隊列用於管理待處理的任務，確保它們按照特定順序進行處理

• 在多執行序的語言中，會共享的任務佇列，以確保線程按照 FIFO 順序執行任務
• 在單線程應用中，可以管理工作流程、事件處理和非同步操作，提高應用程序的效率、可讀性和可維護性

附上 Leecode 上與 Queue 有關的題目：

1.Implement Stack using Queues

2.Implement Queue using Stacks

▌總結

堆疊和佇列都是應用廣泛的典型資料結構之一。堆疊常見的應用情境像是函式呼叫時，打開 F12 的 source 就會看到右邊有 call Stack 的視窗，只要在程式碼中下中斷點（debugger）就能看到函式的呼叫順序，藉此尋找問題；佇列常見的應用情境大多具有一個特徵：暫時存放，稍候執行，並且一定會按先來後到的順序執行。兩者最大的差別就是堆疊執行的端點為同一端，佇列則有兩端

在談論了 Stack 和 Queue 之後，要理解前端很常考的面試題目 - Event Loop 就會比較容易一點! javaScript 是個 Single Thread 的程式語言，一次只能做一件事情，所以 Stack 會把裡面的任務「由上而下」依序處理，每處理完一個片段就移除，直到Stack 為空，這時 queue 如果還有排隊等候的任務就會加入到 stack 裡面，這個過程稱為 Event Loop

event loop demo 線上演示器，可以看到 function 的執行狀態

▌參考資料

1. 堆疊(stack)是什麼
2. 佇列(Queue)是什麼？
3. leecode - stack
4. leecode - queue