溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了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++程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
