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

一、题目

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

二、解决思路

主要用两个函数实现:
1、int remove_stack_and_return(std::stack & stack_1)
2、void reverse(std::stack<int> &stack)
函数1的思想是:用递归的方式将栈顶的元素弹出并返回
函数2的思想是:用递归的方式将函数一返回的元素重新压入栈中,这样就可以实现逆序压栈

三、实现函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// cpp.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<time.h>

//将栈底的元素返回并移除
int remove_stack_and_return(std::stack<int> & stack_1)
{
    auto *pn = &stack_1;
    int result = stack_1.top();
    stack_1.pop();
    if (stack_1.empty())
        return result;
    else
    {
        int last = remove_stack_and_return(stack_1);
        stack_1.push(result);
        return last;
    }
}

//见上面函数返回的栈底的数重新压栈
void reverse(std::stack<int> &stack)
{
    if (stack.empty())
        return;
    int i = remove_stack_and_return(stack);
    reverse(stack);
    stack.push(i);
}

int main()
{
    int num = 500; //添加栈的数量
    std::stack<int> stack_0 ;
    for (int i = 0; i < num; i++)
        stack_0.push(i);
    //用于计算所耗时间
    clock_t one, two;
    one = clock();
    reverse(stack_0);
    two = clock();
    std::cout << "time is "
                  << (double)(two - one)/CLOCKS_PER_SEC
                  << std::endl;
   
    for (int i = 0; i < num; i++)
    {
        if (!stack_0.empty())
        {
            auto top = stack_0.top();
            std::cout << top << std::ends;
            stack_0.pop();
        }
    }
    system("pause");
    return 0;
}

四、总结

1、个人感觉这样的实现方法只适用于递归和栈的学习并不适用于生产环境,原因是,当栈内元素较多的时候,程序的运行时间大大提升。如图,当栈内元素数量为3000的时候,运行时间高达27s

2、较深的递归还会出现栈溢出的错误。当栈内元素数量超过5000时,vs2017出现如下的错误:

3、对于栈操作,慎写慎用

发表评论

电子邮件地址不会被公开。 必填项已用*标注