本文實例講述了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 1After reverse:1 2 3 4 5 6請按任意鍵繼續. . .
希望本文所述對大家C++程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
