來征服資料結構與演算法吧 | 簡單來說就是像排隊的 Queue
Hi！大家好，我是神 Q 超人！這篇文章要試著用 JavaScript 來分享和實作一種叫做 Queue 的資料結構，也會搭配個 Leetcode 的題目來服用，讓大家之後在解題或處理類似需求的時候能想得到 Queue！
Queue
Queue 這個資料結構的實作以生活上平易近人的詞來說就是排隊。當你在超商準備結帳的時候，如果前面有人正在結賬，那你就必須排在他的後面，其他人也是，想結帳就必須再排到你後面，一直到店員把眼前客人的帳結完才會輪到你，然後處理完你的帳後，才會再處理後面的人。
像這樣先來先處理的流程，就是 Queue 這個資料結構在做和限制的事情。還有大家常看到的 FIFO（First In, First Out） 也同樣是在說先進先出。
另一方面，Queue 的特色還有時間複雜度，對於 Queue 來說，不論現在 Queue 裡面有一萬個或是一億個資料，當你把新的資料放到 Queue，或是把資料從 Queue 裡拿出來的時間複雜度永遠都會相同，也就是 O(1) 的時間複雜度。
稍微了解 Queue 的概念後，就來進入實作環節吧！
實作
因為 JavaScript 沒有提供 Queue 這個資料結構，所以如果想要用的話就要自己針對 Queue 的原理來實作一個，而實作的內容則會依照上方提到的 Queue 的兩個特色。
那使用 Queue 究竟需要哪些方法呢？以一個簡單的 Queue 來說，最基本的一定是把東西放進去和拿出來，也就是 enqueue 和 dequeue 啦！
首先建立一個名字叫做 Queue 的 Class，並把方法都建立好：
在選擇 Queue 的實作時，雖然我們可以直接使用 JavaScript 提供的 array 和相關的 methods 做操作，像這樣子：
雖然在功能上已達到了 FIFO，但根據 這則留言 內的測試，unshift 方法執行的時間似乎會根據 array 裡有多少東西而不同。以下是該留言內的測試程式碼：
如果 unshift 是 O(1) 的時間複雜度，那 unshift 應該不管在任何情況下的執行時間都會相同才對。基於上方的原因，那用 array 輕鬆完成 Queue 的方法在時間複雜度的疑慮下就行不通。
那換個角度想，除了 array 之外，我們也可以用 object 做一個簡單的 key 和 value 的對照來實現 Queue，像這樣子：
執行的結果會與和 array 實作一模一樣，實作方式則是用 tail 來當作目前要擺放的位置，而 head 則是目前要取出的位置，把東西放進 Queue 的時候就把 tail 加一，從 Queue 取出東西的時候把原本 head 對照的 value 刪掉，然後換把 head 加一，畢竟取出來了就沒必要再留在 object 裡面。
也因為我們用 object 的 key-value 實作的關係，不論 queue 裡面有多少東西，當我放進或取出新東西時，時間都會是一樣的，也就是 O(1) 的時間複雜度。這麼一來，不論是 FIFO 或是時間複雜度都符合了 Queue 的定義啦！ 🎉
Queue 的題型
在文章的最後就來解一下 Leetcode 上的 1700. Number of Students Unable to Eat Lunch 這道題目吧！
這一題的說明好像很長很複雜，但主要就是題目會給你兩個 Array，分別是學生和三明治的 Array，學生和三明治分別會有 1 和 0 兩個值，1 的學生只會拿 1 的三明治，0 的學生就會只拿 0 的三明治。然後如果排第一個的學生看到目前最上面的三明治不是自己喜歡的口味，就會到最後重新排隊，那如果剛好是喜歡的口味就會直接拿走，也不會重新排隊。
如此反覆，一直到最後我們要回傳有多少學生會拿不到三明治吃。所以學生在拿三明治時會有以下幾種狀況：
狀況一：
學生：[1,0,1,0] 三明治：[0,1,1]
因為第一個學生 1 看到第一個三明治是 0 就不會拿，而是直接重新排隊，變成：
學生：[0,1,0,1] 三明治：[0,1,1]狀況二：
學生：[0,1,0,1] 三明治：[0,1,1]
第一個學生 0 看到第一個三明治是 0，就會直接拿走：
學生：[1,0,1] 三明治：[1,1]狀況三：
學生：[1,1,1] 三明治：[0,1,1]
第一個三明治是 0，剩下想拿 1 的學生就都不會拿，因此有三個學生吃不到三明治，回傳 3
這一題的主要思維就是把學生放進一個 Queue 裡面，然後用迴圈每次都拿出第一個學生，看最上方的三明治是不是他想要的，是的話就拿走三明治，不是的話就再把學生丟回 Queue 裡面。一直到目前最上方的三明治都沒有人想要拿的時候，就可以結束迴圈，並回傳當前 Queue 裡的學生數量了！
整理完上方的思維後，解法如下：
可以發現上方的 MyQueue 除了 enqueue 和 dequeue 之外，我還多增加了 contains 和 getSize 兩個方法，方便判斷當前的三明治種類有沒有學生想拿，和最後 Queue 裡面有多少學生。畢竟是自己實作 Queue 嘛！再多封裝一些常用的方法也是合情合理！
除了上方那一題之外，Leetcode 上還有一些實作 Queue 的練習像是 實作各種指定功能的 Queue 或是用 Queue 來實作 Stack 等等，都是滿有趣的題目，看完這篇文章還意猶未盡的話可以做看看！
參考資料
文章一開始先介紹了 Queue 這個資料結構，再解釋如何用 JavaScript 簡單實作，最後用 Queue 解個 Leetcode 的題目做個結尾，讓自己複習的同時也順便打文章記錄一下，希望能幫助到大家！ 🙌
如果文章裡有任何需要補充或是錯誤的地方，再麻煩留言告訴我！非常感謝！ 🙏
