(资料图片仅供参考)

不借助其他数据结构，如何实现栈的逆序？这是一道非常经典的算法笔试题。所谓栈的逆序，就是把元素12345变成54321。 如果允许再来一个栈结构的话，那过程就会非常简单，只要把第一个栈中的栈顶元素不停的出栈，再进入第二个栈中，就能解决问题。但是题目明确规定，不允许借助其他数据结构。所以问题就变得复杂一些。我们知道，在调用函数的时候，也会用到栈这种结构。于是，这个就成了解决问题的关键，可以借助递归来实现。第一步，看下如何在不借助其他数据结构的情况下，能把栈底元素取出来。 也就是让栈里面的元素变成1234，把5丢掉。假设函数名叫做delete，在delete函数中做的第一件事就是让栈顶元素出栈，而且也只能执行一次，如果连续出栈的话，就得开辟数组来保存这些元素，很显然违背了题目的本意。

int delete(Stack *s){intresult=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，再加上一个判断。这是一段很经典的代码，如果你有就业需求，建议直接背下来。很多同学都在纠结，做嵌入式开发要不要学习算法，因为算法太难了。其实不仅是嵌入式开发，只要是写代码，都得涉及一些算法，只是多少和深浅的问题，如果你打算挑战大厂的嵌入式开发岗位，算法务必得多刷。

审核编辑：汤梓红