堆疊與佇列是蠻常見的資料結構，在理解與實作上並不會很困難，因此會放在一起作介紹。本篇會從基本原理開始介紹，接著進行程式實作及效能分析，最後會介紹堆疊/佇列在瀏覽器上的應用。
實作程式碼: github
堆疊＆佇列原理
堆疊
堆疊為後進先出（LIFO, Last In First Out）的有序串列，在現實中有點像是在餐廳用完餐點後疊起來的盤子，剛用完的盤子肯定是放在最上面的，取走時也是從最上面的盤子開始依序往下取：
由此可知堆疊的資料結構有兩種基本的操作，其中 Push 為將資料放入目前資料結構的頂端；Pop 為移除目前資料結構的頂端資料，透過 Push 與 Pop 可逐步的新增即刪除資料。
佇列
佇列為先進先出（FIFO, First In First Out）的有序串列，就像我們現實中的排隊一樣，先行排隊的人即可享有優先權：
從圖中可看出其與堆疊的差別， 佇列的新增和刪除節點是發生在不同端，新增節點時會加入到資料結構的尾部、移除節點時則是從資料結構的首節點開始移除。了解原理後，接著就可以開始撰寫程式了，這邊會採用之前有介紹過的連結串列進行實作。
實作堆疊＆佇列
實作堆疊
首先宣告一個節點的 class ，建構式中包含數值 value 以及指向下一節點的next ：
class Node { constructor(value){ this.value = value; this.next = null; }}
接著就可以來實作主要的堆疊程式了：
class Stack { constructor(){ this.first = null; this.last = null; this.size = 0; }
push(val){//插入節點 let newNode = new Node(val); if(!this.first){ //資料結構中無任何節點時 this.first = newNode; this.last = newNode; } else {//已有節點時 let temp = this.first; this.first = newNode; this.first.next = temp; } return ++this.size;
} pop(){//移除節點 if(!this.first) return null; //無節點時 let temp = this.first; if(this.first === this.last){//只有一個節點時 this.last = null; } this.first = this.first.next; this.size--; return temp.value; }}
Stack 中的建構式定義了首節點 first、尾節點 last 以及長度 size。使用 push 方法時會產生一個新的 newNode 節點並將值放入。若資料結構中尚無任何節點時，則令 first 及 last 皆為該 newNode 節點即可；若資料結構中已有節點時，則先宣告一個變數 temp 存放目前的首節點 first ，接著令 first 為新增的節點 newNode，first 的下一項為 temp 即可，最後將長度 size 加 1。
使用 pop 方法時，若資料結構中無任何節點則返回 null；若有節點時則宣告一個 temp 存放目前的首節點 first ，只有一個節點時則令 last 為 null；最後令 first 為其下一項並將 size 減一即可。
接著可將程式貼在 chrome 的開發者工具進行實測：
在下方宣告一個變數 stackData 並將 class Stack 進行實體化後，分別 push 了 3、1、8 這三個節點後使用 pop 進行移除，可以預期 8 這個節點會被移除(後進先出)，此時的首節點為 1，尾節點為 3，從圖中可看到執行結果符合預期。
實作佇列
一樣先宣告一個節點的 class ，建構式中包含數值 value 以及指向下一節點的next ：
class Node { constructor(value){ this.value = value; this.next = null; }}
接著撰寫主程式：
class Queue { constructor(){ this.first = null; this.last = null; this.size = 0; } enqueue(val){ let newNode = new Node(val); if(!this.first){//無節點時 this.first = newNode; this.last = newNode; } else {//已有節點時 this.last.next = newNode; this.last = newNode; } return ++this.size; } dequeue(){ if(!this.first) return null; let temp = this.first; if(this.first === this.last) { this.last = null; } this.first = this.first.next; this.size--; return temp.value; }}
程式碼與堆疊相似，最大的不同在於佇列在新增節點( enqueue )時並不是將其添加為首節點 first，而是新增為尾節點 last；移除節點( dequeue )的程式碼則與堆疊相同。接著可用 chrome 的開發者工具進行實測：
透過 queueData 將 class 實體化後分別 enqueue 了 3、1、8 三個節點後使用 dequeue進行移除，預期結果為節點 3 將會被移出(先進先出)，此時的首節點 first 為 1，尾節點為 8 ，從圖中可看到執行結果符合預期。
時間 / 空間複雜度分析
堆疊與佇列的時間/空間複雜度整理如下表：
由於兩者實作的差異僅在新增/刪除時節點順序的不同，故空間與時間複雜度是一致的(Access、Search 方法在本文無實作，可參考連結串列篇)。由於其結構近似於連結串列(Linked list)，因此 Access、Search 方法皆只能使用遍歷的方式做執行，故時間複雜度為 O(n)；新增( Insertion )及刪除( Deletion )僅操作首、尾節點，故時間複雜度為 O(1)；而資料結構所占用的記憶體空間會隨著資料的新增而增加，因此空間複雜度為 O(n)。
堆疊/佇列在瀏覽器上的應用
單線程
要了解堆疊/佇列在環境中的應用，首先需要知道 JavaScript 是單線程的程式語言，每個程式碼片段會進到堆疊中，並從堆疊的最上方開始往下執行。
執行堆疊
執行堆疊（called stack）說明了目前的程式執行到了哪個地方。讓我們實際來看個範例：
function multiply(a,b) { return a*b;//4}function square(n) { return multiply(n,n)//3}function printSquare(n) { let squared = square(n);//2 console.log(squared);//5}printSquare(4);//1
首先進入 stack 的會是這個檔案中全域環境的程式（這裡稱作 main），接著加入的是 printSquare ，放在堆疊的最上方，之後 square、multiply 依序進入，如下圖所示：
最上方的函式執行完後會從堆疊區移除 (即執行 pop 方法)，依序結束整個堆疊。
非同步處理與堆疊
到這邊可以知道由於 JavaScript 為單線程的程式語言，因此若堆疊區的函式執行過久，會有阻塞的問題( stack blocked )，為了解決阻塞的問題，就有了非同步（Asynchronous）的處理方式，常用的 AJAX ( Asynchronous JavaScript and XML) 即是使用這種方式來處理。
來看看這個範例影片：連結
程式碼如下:
console.log('hi');setTimeout(() => { console.log('there');}, 5000);console.log('JS');
從影片中可以得知，當堆疊執行到 setTimeout 這個函式時， setTimeout 實際上是一個瀏覽器提供的 API ，其提供了一個計時器給我們使用，此時會將該 setTimeout 程式從堆疊區移到 webAPIs 中開始計時，計時完後會把要執行的函式放到 「工作佇列」（task queue）中，當堆疊執行完後變會去執行這個項目，而當有很多的項目時則會依照進入工作佇列的順序依序執行；而前面所講的堆疊與佇列在這邊就得到應用了。
重點複習
- 堆疊是種遵守著「後進先出」的有序串列
- 佇列是種遵守著「先進先出」的有序串列
- 瀏覽器提供了 webAPIs 解決了JavaScript 單線程會造成的阻塞問題，在堆疊區中的程式執行完後，才會「依序」的執行排在工作佇列中的非同步程式。
