嵌入式開發(fā)經(jīng)典算法之棧逆序

? 不借助其他數(shù)據(jù)結(jié)構(gòu)，如何實(shí)現(xiàn)棧的逆序？這是一道非常經(jīng)典的算法筆試題。

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

如果允許再來一個(gè)棧結(jié)構(gòu)的話，那過程就會(huì)非常簡單，只要把第一個(gè)棧中的棧頂元素不停的出棧，再進(jìn)入第二個(gè)棧中，就能解決問題。

但是題目明確規(guī)定，不允許借助其他數(shù)據(jù)結(jié)構(gòu)。所以問題就變得復(fù)雜一些。

我們知道，在調(diào)用函數(shù)的時(shí)候，也會(huì)用到棧這種結(jié)構(gòu)。于是，這個(gè)就成了解決問題的關(guān)鍵，可以借助遞歸來實(shí)現(xiàn)。

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

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

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

? 剛才出棧的元素被記在了變量中，這個(gè)變量叫做局部變量，只要函數(shù)調(diào)用沒有結(jié)束，他就一直存在不會(huì)被釋放。

于是在delete函數(shù)中再次調(diào)用delete函數(shù)，又會(huì)出棧一個(gè)元素，注意，已經(jīng)出棧的兩個(gè)元素都還在內(nèi)存中，因?yàn)楹瘮?shù)調(diào)用沒有結(jié)束。不停的調(diào)用delete，遲早會(huì)把棧里面的元素清空，然后再回頭操作，把這些還在內(nèi)

存里面的元素逐個(gè)在進(jìn)棧放回去。

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。過程理解起來比較復(fù)雜， 但是代碼確實(shí)很簡單，這也是遞歸的特點(diǎn)。

第二步，在delete函數(shù)的基礎(chǔ)上，繼續(xù)實(shí)現(xiàn)棧的逆序。

原理一樣，還是得遞歸。

假設(shè)逆序的函數(shù)叫做reverse。reverse函數(shù)要做的第一件事就是獲得棧底元素，就是剛才寫的delete函數(shù)，然后再次調(diào)用reverse函數(shù)，再獲得棧底元素，這些元素都被記在了內(nèi)存中，因?yàn)楹瘮?shù)調(diào)用沒有結(jié)束，所以也不會(huì)被釋放。當(dāng)棧變成空棧的時(shí)候，再把剛才那些元素逐個(gè)進(jìn)棧，最終得到的就是被反轉(zhuǎn)的棧。

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


    int i = delete(s);


    reverse(s);


    push(s, i);
}

? 代碼也是非常簡單，其實(shí)就是調(diào)用了三個(gè)函數(shù)，delete ?reverse ?push，再加上一個(gè)判斷。

這是一段很經(jīng)典的代碼，如果你有就業(yè)需求，建議直接背下來。

很多同學(xué)都在糾結(jié)，做嵌入式開發(fā)要不要學(xué)習(xí)算法，因?yàn)樗惴ㄌy了。其實(shí)不僅是嵌入式開發(fā)，只要是寫代碼，都得涉及一些算法，只是多少和深淺的問題，如果你打算挑戰(zhàn)大廠的嵌入式開發(fā)崗位，算法務(wù)必得多刷。

?

　　審核編輯：湯梓紅