一、Stack & Queue

1.1 基本觀念介紹

這裡講的 stack 和 queue，就是和 event loop 裡會用到的 call stack 和 callback queue 的基礎資料結構。

如果不是很清楚 event loop 是什麼，可以看這篇。

Stack 和 Queue 常常用 array 或 linked list，但沒有限定，只要能實作出該資料結構即可。

Last in, First out (LIFO)

最後一個進去，第一個出來。

比如書籍堆疊起來，最後一本堆上去的會第一本先被拿走；

最下面 bottom 是第一個被放入的 frame，然後 frame 被一個一個堆起來 (push)，

如果要把 frame 抽走，只能從最上方開始拿 (pop)。

First In, First Out (FIFO)

第一個進去，第一個出來。

就跟現實中的排隊一樣 ~~(不考慮插隊的話~~)。

在解題時常常會用到 queue.shift() 但這樣的作法有問題是每次拿第一個值出來時，後續的數值都會往前移，故 time complexity 會是 O(n)；這是因為 JavaScript 沒有內建 queue 的資料結構，不過可使用其他 library 輔助。

在解題時可跟面試官解釋上述原因，並說那此處這裡是否可假設為 O(1)。

實作 traverse binary tree。

Stack 和 queue 常常使用在解 DFS 和 BFS 的題目，

不過這部份觀念會到 tree 那篇才會講解，這邊可以先參考看看。

關於這個 excel 表，你可以 :

題號 : 根據 LeetCode 題目出現的頻率, top interview 150 等整理的，但注意不代表這就涵蓋所有面試會考的題目。或你可以選擇 Grind 來安排你要刷的題目
難度 : 按照你現在想要的難度選擇刷題
重要性 : 比如說你注意到、或別人提到 Google 很常考這個題目之類，可以設定你覺得相對的重要性，之後可以拿來篩選用
第一次是否解出來 : 紀錄解題是否第一次就成功，若不成功可能需要複習
解題思路 : 題目的思路過程，寫大綱就好不用寫很詳細
其他解法 : 若解出來是否還可以想到其他解法，或是看到別人提供了更好的解法便記錄下來，在面試時還可以提出自己有不同解法
學到技巧 : 如此題可以用 two pointer 來解，寫下來下次遇到別的題目就可以知道說我多一個解法可以想想看可不可行
複習次數 : 用來記錄第一次解不出來的題目之練習次數
複習筆記 : 有可能再做一次還是解不出來，那可寫下這次癥結點是什麼，怎麼解決的，盡量完全理解解法，讓自己如果再做一次題目時若還是卡住，可以看筆記或是回想筆記試圖解出來
上次解題時間 : 可用來篩選下次該複習的題目

--
相關文章