嵌入式開發經典算法之棧逆序

? 不借助其他數據結構，如何實現棧的逆序？這是一道非常經典的算法筆試題。

所謂棧的逆序，就是把元素12345變成54321。 ? ?

如果允許再來一個棧結構的話，那過程就會非常簡單，只要把第一個棧中的棧頂元素不停的出棧，再進入第二個棧中，就能解決問題。

但是題目明確規定，不允許借助其他數據結構。所以問題就變得復雜一些。

我們知道，在調用函數的時候，也會用到棧這種結構。于是，這個就成了解決問題的關鍵，可以借助遞歸來實現。

第一步，看下如何在不借助其他數據結構的情況下，能把棧底元素取出來。 ? ? 也就是讓棧里面的元素變成1234，把5丟掉。

假設函數名叫做delete，在delete函數中做的第一件事就是讓棧頂元素出棧，而且也只能執行一次，如果連續出棧的話，就得開辟數組來保存這些元素，很顯然違背了題目的本意。

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

? 剛才出棧的元素被記在了變量中，這個變量叫做局部變量，只要函數調用沒有結束，他就一直存在不會被釋放。

于是在delete函數中再次調用delete函數，又會出棧一個元素，注意，已經出棧的兩個元素都還在內存中，因為函數調用沒有結束。不停的調用delete，遲早會把棧里面的元素清空，然后再回頭操作，把這些還在內

存里面的元素逐個在進棧放回去。

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函數返回5。過程理解起來比較復雜，但是代碼確實很簡單，這也是遞歸的特點。

第二步，在delete函數的基礎上，繼續實現棧的逆序。

原理一樣，還是得遞歸。

假設逆序的函數叫做reverse。reverse函數要做的第一件事就是獲得棧底元素，就是剛才寫的delete函數，然后再次調用reverse函數，再獲得棧底元素，這些元素都被記在了內存中，因為函數調用沒有結束，所以也不會被釋放。當棧變成空棧的時候，再把剛才那些元素逐個進棧，最終得到的就是被反轉的棧。

void reverse(Stack *s)
{
    if (isEmpty(s))
    {
        return;
    }


    int i = delete(s);


    reverse(s);


    push(s, i);
}

? 代碼也是非常簡單，其實就是調用了三個函數，delete ?reverse ?push，再加上一個判斷。

這是一段很經典的代碼，如果你有就業需求，建議直接背下來。

很多同學都在糾結，做嵌入式開發要不要學習算法，因為算法太難了。其實不僅是嵌入式開發，只要是寫代碼，都得涉及一些算法，只是多少和深淺的問題，如果你打算挑戰大廠的嵌入式開發崗位，算法務必得多刷。

　　審核編輯：湯梓紅

閱讀全文