如何仅用递归函数和栈操作逆序一个栈（栈 / 模拟）

如何仅用递归函数和栈操作逆序一个栈

描述

一个栈依次压入 1、2、3、4、5，那么从栈顶到栈底分别为 5、4、3、2、1。将这个栈转置后，从栈顶到栈底为 1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

---

链接

https://www.nowcoder.com/questionTerminal/ba7d7f5d1edf4d1690d66e12e951f6ea

---

题解

• 将栈中的元素逆序，相当于先将栈清空，然后一个接一个压入栈顶元素
• 问题是将栈清空后，还怎么得到原来的栈顶元素

• 这时候我们可以利用递归来保存栈中的元素，然后进行还原，很容易写出代码：

  void _reverse0(stack <int> &s)
  {
      if (!s.empty())
      {
          int last = s.top(); // ③
          s.pop();
          _reverse0(s);
          s.push(last); // ①
      }
  }

• 但是这段代码无效，为什么呢？
• 仔细观察一下，你会发现，① 处 s 相当于是从栈底开始 push 的，也就是说在递归结束后，栈中元素的顺序根本没变，过程如下图所示：

  

• 我们需要再考虑一下怎么才能从栈顶开始 push，也就是按照 3 2 1 的顺序入栈
• 我们可以再设计一个函数 f，让 ① 处 s 每次 push 的都是栈顶元素，也就是取代 ③ 处 last 的值
• ③ 处 last 的值是从栈顶开始输出的，结果为 3 2 1，使得 s push 的顺序为 1 2 3
• 那么函数 f 每次的返回值应该是从栈底开始，结果为 1 2 3，从而 s push 的顺序为 3 2 1
• 也就是说 f 的功能是获取栈底元素，但是如果栈中的元素不变的话，会导致每次获取的都是 1

• 所以我们在获取栈底元素后，还需要将栈底元素删除，代码如下：

  int _remove(stack <int> & s)
  {
      int element = s.top();
      s.pop();
      if (s.empty())
          return element;
      int last = _remove(s);
      s.push(element);
      return last;
  }

• 过程如下图所示：

  

---

代码

最终的代码：

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

// 移除栈底元素并返回
int _remove(stack <int> & s)
{
    int element = s.top();
    s.pop();
    if (s.empty())
        return element;
    int last = _remove(s);
    s.push(element);
    return last;
}

// 反转
void _reverse1(stack <int> &s)
{
    if (!s.empty())
    {
        int last = _remove(s);
        _reverse1(s);
        s.push(last);
    }
}

void _reverse0(stack <int> &s)
{
    if (!s.empty())
    {
        int last = s.top();
        s.pop();
        _reverse0(s);
        s.push(last);
    }
}

void display(stack <int> s)
{
    cout << "stack element: " << endl;
    while (!s.empty())
    {
        cout << s.top() << endl;
        s.pop();
    }
}

int main()
{
    stack<int>s;
    for (int i = 1; i <= 3; ++i)
        s.push(i);
    display(s);
    _reverse1(s);
    display(s);
    return 0;
}

效果：

stack element:
3
2
1
stack element:
1
2
3

---

The end.
2020年4月24日 星期五