MENU

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

2020 年 04 月 24 日 • 阅读: 418 • 练习阅读设置

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

描述

一个栈依次压入 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 的,也就是说在递归结束后,栈中元素的顺序根本没变,过程如下图所示:

    1

  • 我们需要再考虑一下怎么才能从栈顶开始 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;
    }
  • 过程如下图所示:

    2


代码

最终的代码:

#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日 星期五