嵌入式开发经典算法之栈逆序

不借助其他数据结构，如何实现栈的逆序？这是一道非常经典的算法笔试题。

所谓栈的逆序，就是把元素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，再加上一个判断。

这是一段很经典的代码，如果你有就业需求，建议直接背下来。

很多同学都在纠结，做嵌入式开发要不要学习算法，因为算法太难了。其实不仅是嵌入式开发，只要是写代码，都得涉及一些算法，只是多少和深浅的问题，如果你打算挑战大厂的嵌入式开发岗位，算法务必得多刷。

　　审核编辑：汤梓红

阅读全文