佇列理論就是這麼簡單
一、背景
前面分享了《 陣列就是簡單系列 》,接下來就是分享佇列和棧了。
我們知道,我們可以通過索引下標來隨機訪問陣列的元素。
但是有時候,我們會對訪問順序進行限制。
比如先進先出,就對應佇列資料結構;後進先出對應棧資料結構。
接下來的幾篇文章會介紹佇列和棧的基礎知識,以及用來解決什麼問題,即實踐與應用。
下面我們先來看看佇列的基礎知識和實踐吧。
二、佇列的定義
佇列是一種先進先出的資料結構。
先進先出英文是 First In First Out
,簡稱為 FIFO
。
具體含義就是首先處理新增到佇列中的第一個元素。
一般,插入操作稱為入隊(enqueue),具體實現是將新元素放在了佇列的最後。
而刪除操作稱為出隊(dequeue),即將最前面的元素刪除。
當然,語言內建的佇列名字有點不一樣。
名字大概是這樣:入隊(push)、出隊(pop)、是否為空(empty)、隊頭(front)、隊尾(back)、大小(size)。
三、佇列初步實現
面試的時候,我經常會問如何使用陣列實現一個佇列。
一般都能回答上來,即使用一個下標表示隊頭和隊尾。
如果個別幾個回答出隊時所有資料向前移動時,我就會和他探討這個操作的複雜度,以及有沒有優化空間。
經過的這樣討論,大家都可以想到使用下標來指向隊頭和隊尾。
比如下面是使用 vector
實現的一個簡單的佇列,當然,這裡沒有進行邊界檢查。
class MyQueue { private: vector<int> data; int p_start; public: MyQueue() {p_start = 0;} void push(int x) { data.push_back(x); } void pop() { p_start++; } int front() { return data[p_start]; } };
上面這個實現是很簡單,但是也有很多問題。
比如不斷的入隊和出隊, data
這個容器就會越來越大,但是前面的空間無法利用起來。
所以,這個時候,我會問面試者:該如何優化才能利用這些空間呢?
四、迴圈佇列
面對空間問題,幾乎所有人都能提出迴圈佇列這個答案。
即預設容器是定長的。
通過維護一個頭指標和尾指標來標記開始位置和結束位置,從而利用前面的空間。
這個時候有四連問:
1.入隊該如何實現?
2.出隊又該如何實現?
3.有什麼注意事項嗎?
4.怎麼判斷是否滿了?
這四個如果都可以答上來,一般就可以說明這個人的基礎知識還可以。
大概實現如下:
五、廣度優先搜尋
我們經常通過佇列來實現廣度優先搜尋。
最經典的問題是尋找從根結點到目標結點的最短路徑。
比如對於這樣一個圖,我們首先根節點 A
入隊。
然後,從隊首取出一個元素,將其所有的子節點 B C D
加入到佇列。
接著,依次從隊首取一個元素,並將元素的子節點加入到佇列(重複的不要加)。
這樣不斷迴圈下去,就可以遍歷圖上的所有可以到達的點。
而且,可以看到,使用佇列來搜尋的話,是一層層的搜尋的。
每搜尋一層,子節點的距離就是當前節點與根節點的距離加一。
所以我們搜尋的路徑,就是根節點到當前節點的最短路徑。
這裡面有一個很關鍵的地方:子節點不能重複加入佇列。
一般我們會使用一個容器來標記節點是否已經加入佇列。
下面我們來看三道題吧。
六、島嶼的個數
題意:輸入一個二維陣列,值是 0
海水或 1
陸地。陸地上下左右方向挨著時代表陸地連線著。
求互相獨立的島嶼個數。
思路:掃描二維陣列,找到一個陸地後,就使用佇列 BFS
將連續的陸地都標記為非陸地。
這樣進行下去,既可以統計到島嶼的總個數。
注意事項:對於二維陣列的上下左右,需要判斷是否越界。
這個在《陣列即使這麼簡單》系列裡曾介紹過。
七、開啟轉盤鎖
題意:有一個四個圓形撥輪的轉盤鎖,其實位置始終是 0000
,求最少旋轉幾下可以到達目標位置。
限制條件:有一些數字被封殺了,是死亡數字,遇到就代表無解,返回 -1
。
思路:典型的 BFS
題。只是這裡多了一個死亡數字的限制條件。
所以搜尋的時候,需要進行一個判斷:遇到死亡數字時不能遞迴搜尋。
具體見程式碼註釋吧。
八、完全平方數
題意:給一個正整數,可以選一些平方數(允許重複),使得和等於這個數。求平方數最少可以是多少個?
思路:這道題方法很多,這裡我們需要使用 BFS
的思想來做。
對於 BFS
,則是列舉一個平方數可以計算出那些數字,接著是兩個平方數可以計算出那些數字,這樣不斷進行下去,直到找到答案。
佇列初始條件可以是 0
。之後每次出隊一個數字時,要加上所有的平方數。如果沒找到答案,則去重入隊。
注意事項:對於和已經大於給定的數字時,就不需要入隊了。
九、最後
這篇文章簡單的介紹了佇列的基礎知識與應用實踐。
對於佇列的實現,面試的時候經常會被問到,比如如何使用定長陣列實現,如何進出隊,滿了怎麼辦等等。
而對於佇列的應用,則主要用於解決搜尋最優問題:即通過最少步數從起始位置到達目標位置。
之所以會這樣,是因為佇列對應於廣度優先搜尋。
其幾何意義就是一層層的搜尋,每搜一層,深度越深,那步數自然就越大了。
如果存在答案,則首次遇到的就是最優解。
-EOF-