C++使用递归函数和栈操作逆序一个栈的算法示例

本文实例讲述了C++使用递归函数和栈操作逆序一个栈的算法。分享给大家供大家参考，具体如下：

题目：

一个栈依次压入1、2、3、4、5，那么栈顶到栈底分别为：5、4、3、2、1。
将这个栈逆置后栈顶到栈底分别为1、2、3、4、5。
用递归函数来实现，不能用其他数据结构。

解题思路及代码

1、递归函数一：将栈的栈底元素一个个返回并移除。
2、递归函数二：逆序栈，调用递归函数一实现。

C++实现：

class Solution
{
public:
  //递归函数一
  static int getAndRemoveStackLastElem(stack<int>& s)
  {
    int result = s.top();
    s.pop();
    if (s.empty())
      return result;
    else
    {
      int last = getAndRemoveStackLastElem(s);
      s.push(result);
      return last;
    }
  }
  //递归函数二
  static void reverseStack(stack<int>& s)
  {
    if (s.empty())
      return;
    int i = getAndRemoveStackLastElem(s);
    reverseStack(s);
    s.push(i);
  }
};

程序测试用例：

#include <iostream>
#include <stack>
using namespace std;
class Solution
{
public:
  static int getAndRemoveStackLastElem(stack<int>& s)
  {
    int result = s.top();
    s.pop();
    if (s.empty())
      return result;
    else
    {
      int last = getAndRemoveStackLastElem(s);
      s.push(result);
      return last;
    }
  }
  static void reverseStack(stack<int>& s)
  {
    if (s.empty())
      return;
    int i = getAndRemoveStackLastElem(s);
    reverseStack(s);
    s.push(i);
  }
};
//打印栈
void show(stack<int> s)
{
  while (!s.empty())
  {
    cout << s.top() << " ";
    s.pop();
  }
  cout << endl;
}
int main()
{
  stack<int> s;
  s.push(1);
  s.push(2);
  s.push(3);
  s.push(4);
  s.push(5);
  s.push(6);
  cout << "Before reverse: " << endl;
  show(s);
  cout << "After reverse: " << endl;
  Solution::reverseStack(s);
  show(s);
  system("pause");
}

运行结果：

Before reverse:
6 5 4 3 2 1
After reverse:
1 2 3 4 5 6
请按任意键继续. . .

希望本文所述对大家C++程序设计有所帮助。

# C++ # 递归函数 # 栈 # 逆序栈 # C++实现递归函数的方法 # C语言递归函数与汉诺塔问题简明理解 # C语言深入分析递归函数的实现 # C语言用递归函数实现汉诺塔 # C语言的递归函数详解 # C语言用递归函数对素数进行判断流程 # 递归 # 分别为 # 数据结构 # 给大家 # 不能用 # 请按 # 来实现 # 所述 # 程序设计 # 移除 # 讲述了 # main # endl # 栈逆置后栈顶到栈底 # reverse # br # class # brush # pre # cout

返回目录在线咨询

上一篇：Go语言中sync.WaitGroup指针地址的常见误解与解析
下一篇：重工零配件网站设计：如何创建用户友好的界面和导航？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

C++使用递归函数和栈操作逆序一个栈的算法示例

您的项目需求