原本今天想給大家講講快速選擇算法的,但是發現一連寫了好幾篇排序相關了,是以臨時改了題目,今天聊點資料結構,來看看經典并且簡單的資料結構——棧。
棧這個結構我想大家應該都耳熟能詳,尤其是在很多地方将和堆并列在一起,稱作“堆棧”就更廣為人知了。但其實堆和棧本質上是兩種不同的資料結構,我們不能簡單地混為一談。讓我們先從比較簡單的棧開始。
棧和隊列的本質其實都是數組(嚴格地說是線性表)。隻不過我們在數組上增加了一些限制,使得它滿足一定的條件而已,是以很多對資料結構畏首畏尾的同學可以放寬心,棧沒什麼特别的花樣,就是一種特殊的數組。
和其他廣義上的線性表資料結構比起來,棧的特殊性隻有兩條,一條是先進後出,另一條是隻能從數組的一側讀寫。但本質上來說這兩條是一樣的,由于我們隻能從一側讀寫元素,是以進的越早出的越晚,當然是先進後出。從下面這張圖應該很容易能看明白。
棧規定了我們隻能從一側進行讀寫,正常上我們将能夠讀寫的一側稱作是棧頂。不能讀寫的另一側稱為是棧底。從上面的圖可以看到,隻有棧頂的元素出棧了之後,才能通路到棧底的元素。
我們用Python的數組來實作棧這個資料結構,去掉注釋真的隻有30行不到,可以說是非常簡單,我們先來看代碼。
本質上來說,一般的棧實作隻有以上這麼幾個方法,可能會更少。因為有些語言當中的棧,top和彈出是合并的。意味着通路必須要彈出,不支援非彈出通路。是以棧的實作邏輯是非常簡單的,甚至可以說是毫無技術含量,非常适合入門資料結構。
當然,從另一個方面也可以說棧的實作原理并不太重要,相比之下更重要的是棧一般會用在什麼地方。
棧的應用
棧最廣泛的應用就是在作業系統當中,比如在程式執行調用方法的時候,在編譯器内部,其實是記錄了一個目前調用的方法棧。舉個例子,比如目前調用到的方法是A,如果在A方法中又去調用了方法B,那麼計算機就會在系統方法棧當中存儲一個指向B方法的指針,如果B方法又調用到了C方法,那麼又會新增一個C的指針。當C方法執行結束,那麼C就會彈出,計算機會将C的結果帶入B,繼續執行之前的B,以此類推,直到棧空為止。
那麼,問題來了,如果一個方法A自己調用自己會怎麼樣?
答案是計算機會建立一個新的A的指針填入棧中,如果A繼續遞歸,那麼系統再建立一個新的指針入棧……
從上面這個過程,我們可以确定兩個事情。第一,我們寫程式時候的遞歸,在編譯器内部其實是以棧的形式執行的。第二,如果我們用一個死循環去不停地遞歸,由于棧存在大小限制,是以當棧的深度超過限制的時候,就會出現SystemStackExceed的錯誤。也就是說遞歸并不是無限的,因為除了作業系統對于運作記憶體的限制之外,編譯器還會有最大遞歸深度的限制,防止遞歸中死循環導緻系統崩潰。雖然各個語言實作機制不完全一樣,但是有一點是肯定的,遞歸深度是有限的,我們不能無限制遞歸。
那問題來了,如果我們系統就是會存在大規模的遞歸怎麼辦?難道還要手動給機器加記憶體嗎?
這是ACM玩家在賽場上經常遇到的問題之一,有經驗的選手在第一天的熱身賽時一定會做的事情除了配置vim或者其他IDE之外,就是會測試一下電腦的最大遞歸深度。在C++當中,是支援通過彙編語言強行打開遞歸深度限制的,但是即使如此也是有限的,并且據我所知隻有C++可以這麼幹,對于其他語言,以及開大了遞歸深度還是不夠用的情況,就隻有一種辦法,就是手動建棧模拟遞歸。
手動遞歸
許多同學可能覺得遞歸痛苦,但是如果他們試着手動建棧來模拟遞歸的話,會發現要更加痛苦。不僅要額外增加變量存儲中間狀态,并且對于程式設計也是一個巨大的挑戰。
我們來看一個例子:
這是一棵簡單的二叉樹,畫出來是這個樣子:
下面我們要通過棧在不使用遞歸的情況下來中序周遊它,中序周遊我們都知道,就是先周遊左子樹,然後輸出目前節點,再周遊右子樹。寫成遞歸非常友善,隻有幾行:
大家想想,如果不使用遞歸應該怎麼辦?如果你真的試着去寫,就會發現看起來很簡單的問題好像變得非常複雜。我們很容易可以想到,我們把節點存儲在棧當中,但是存儲資料隻是表象。本質問題是當我們從棧當中拿到了一個節點之後,我們怎麼判斷它究竟應該做什麼?應該周遊左節點嗎,應該輸出嗎,還是應該周遊右節點?
對這些問題仔細分析和思考,我們可以發現它們都和遞歸的回溯有關。
在遞歸當中,當我們周遊完了目前節點的某棵子樹之後,随着棧的彈出,還會回到這個節點。比如上面這棵樹當中,在遞歸過程當中,我們會兩次碰到1這個節點。第一次時它不會輸出1,而是先去周遊了它的左子樹,也就是3,之後再次回到1,由于它的左子樹已經周遊過,是以會輸出1。這個離開又回來的過程稱為回溯。如果你把樹結構想象成瀑布的話,這個過程有點像是先順流而下,又逆流而上傳回,backtracking翻譯成回溯還是蠻合理的。
我們回到之前的問題,所有的搞不清楚的本質都來源于我們無法判斷目前遇到的節點究竟是初次見面,還是回溯之後的久别重逢。而這關系到我們要對它做什麼。原本在遞歸當中,由于程式會記錄遞歸時的狀态和代碼運作的位置,遞歸回溯之後會回到上次調用的位置,是以我們可以忽略這個問題。而現在我們由于不再使用遞歸,是以需要我們自己來判斷節點的狀态。
想通了其實很簡單,我們隻需要在節點當中加一個狀态的字段,表示這個節點是否會發生回溯。顯然在一開始的時候,所有的節點狀态都是True。
我們在Node類中加一個flag作為記錄,初始化時我們預設它為True。接着就很簡單了,我們就按照左中右的順序周遊節點,隻要左子樹存在且還沒有回溯過就往左邊周遊,在一路往左的過程中遇到的這些節點的flag全部置為False,因為它們的回溯已經開始,以後不會再發生回溯了。由于往右周遊不會存在回溯的問題,是以可以忽略,想明白了,代碼也就順理成章。
這段代碼雖然短,但其實不簡單,想要完全看懂需要對遞歸和循環有深入的了解。屬于典型的看着簡單實際不容易的題,我個人比較喜歡這類問題,除了鍛煉思維之外也很适合用來面試,候選人的思維能力、代碼駕馭能力基本上都一清二楚了。沒有看懂的同學也不用擔心,因為在實際場景當中并不會遇到這樣的場景,以後還會推出其他關于遞歸和搜尋算法的文章,隻要你堅持閱讀,我相信一定會看懂的。
今天的文章就是這些,如果覺得有所收獲,請順手點個關注或轉發吧,你們的舉手之勞對我來說很重要。