(資料圖)

不借助其他數(shù)據(jù)結構，如何實現(xiàn)棧的逆序？這是一道非常經(jīng)典的算法筆試題。所謂棧的逆序，就是把元素12345變成54321。 如果允許再來一個棧結構的話，那過程就會非常簡單，只要把第一個棧中的棧頂元素不停的出棧，再進入第二個棧中，就能解決問題。但是題目明確規(guī)定，不允許借助其他數(shù)據(jù)結構。所以問題就變得復雜一些。我們知道，在調(diào)用函數(shù)的時候，也會用到棧這種結構。于是，這個就成了解決問題的關鍵，可以借助遞歸來實現(xiàn)。第一步，看下如何在不借助其他數(shù)據(jù)結構的情況下，能把棧底元素取出來。 也就是讓棧里面的元素變成1234，把5丟掉。假設函數(shù)名叫做delete，在delete函數(shù)中做的第一件事就是讓棧頂元素出棧，而且也只能執(zhí)行一次，如果連續(xù)出棧的話，就得開辟數(shù)組來保存這些元素，很顯然違背了題目的本意。

int delete(Stack *s){intresult=pop(s);}

剛才出棧的元素被記在了變量中，這個變量叫做局部變量，只要函數(shù)調(diào)用沒有結束，他就一直存在不會被釋放。于是在delete函數(shù)中再次調(diào)用delete函數(shù)，又會出棧一個元素，注意，已經(jīng)出棧的兩個元素都還在內(nèi)存中，因為函數(shù)調(diào)用沒有結束。不停的調(diào)用delete，遲早會把棧里面的元素清空，然后再回頭操作，把這些還在內(nèi)存里面的元素逐個在進棧放回去。

int delete(Stack *s){    int result = pop(s);    if (isEmpty(s))    {        return result;    }    else    {        int last = delete(s);        push(s, result);        return last;    }}

最終得到的就是1234，delete函數(shù)返回5。過程理解起來比較復雜， 但是代碼確實很簡單，這也是遞歸的特點。第二步，在delete函數(shù)的基礎上，繼續(xù)實現(xiàn)棧的逆序。原理一樣，還是得遞歸。假設逆序的函數(shù)叫做reverse。reverse函數(shù)要做的第一件事就是獲得棧底元素，就是剛才寫的delete函數(shù)，然后再次調(diào)用reverse函數(shù)，再獲得棧底元素，這些元素都被記在了內(nèi)存中，因為函數(shù)調(diào)用沒有結束，所以也不會被釋放。當棧變成空棧的時候，再把剛才那些元素逐個進棧，最終得到的就是被反轉的棧。

void reverse(Stack *s){    if (isEmpty(s))    {        return;    }    int i = delete(s);    reverse(s);    push(s, i);}

代碼也是非常簡單，其實就是調(diào)用了三個函數(shù)，delete reverse push，再加上一個判斷。這是一段很經(jīng)典的代碼，如果你有就業(yè)需求，建議直接背下來。很多同學都在糾結，做嵌入式開發(fā)要不要學習算法，因為算法太難了。其實不僅是嵌入式開發(fā)，只要是寫代碼，都得涉及一些算法，只是多少和深淺的問題，如果你打算挑戰(zhàn)大廠的嵌入式開發(fā)崗位，算法務必得多刷。

審核編輯：湯梓紅