C++使用遞歸函數和棧操作逆序一個棧的算法示例。本站提示廣大學習愛好者：（C++使用遞歸函數和棧操作逆序一個棧的算法示例）文章只能為提供參考，不一定能成為您想要的結果。以下是C++使用遞歸函數和棧操作逆序一個棧的算法示例正文

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++程序設計有所幫助。