C++使用遞歸函數(shù)和棧操作逆序一個棧的算法示例
更新時間：2017年05月10日 11:20:11 作者：難免有錯_
這篇文章主要介紹了C++使用遞歸函數(shù)和棧操作逆序一個棧的算法,結合實例形式分析了C++遞歸函數(shù)與逆序棧的相關操作技巧,需要的朋友可以參考下
本文實例講述了C++使用遞歸函數(shù)和棧操作逆序一個棧的算法。分享給大家供大家參考，具體如下：
題目：
一個棧依次壓入1、2、3、4、5，那么棧頂?shù)綏５追謩e為：5、4、3、2、1。
將這個棧逆置后棧頂?shù)綏５追謩e為1、2、3、4、5。
用遞歸函數(shù)來實現(xiàn)，不能用其他數(shù)據(jù)結構。
解題思路及代碼
1、遞歸函數(shù)一：將棧的棧底元素一個個返回并移除。
2、遞歸函數(shù)二：逆序棧，調用遞歸函數(shù)一實現(xiàn)。
C++實現(xiàn)：
class Solution
{
public:
//遞歸函數(shù)一
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;
}
}
//遞歸函數(shù)二
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 請按任意鍵繼續(xù). . .
希望本文所述對大家C++程序設計有所幫助。
相關文章
C語言中const,volatile,restrict的用法總結
以下是對C語言中const,volatile,restrict的用法進行了詳細的總結介紹，需要的朋友可以過來參考下2013-10-10
深處開發(fā)崗，其實排序也是繞不開的環(huán)節(jié)，其中冒泡排序，選擇排序，插入排序，歸并排序，快速排序，堆排序也是我在秋招以來頻繁問到的技術點，今天我們來重點聊聊排序2021-11-11
這篇文章主要介紹了C++ float、double判斷是否等于0問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
這篇文章主要為大家詳細介紹了C語言結構數(shù)組實現(xiàn)貪吃蛇小游戲，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
這篇文章主要介紹了C++ 回文字符串的實例詳解的相關資料,需要的朋友可以參考下2017-07-07
C++通過共享內存ShellCode實現(xiàn)跨進程傳輸
在計算機安全領域,ShellCode是一段用于利用系統(tǒng)漏洞或執(zhí)行特定任務的機器碼,本文主要為大家介紹了C++如何通過共享內存ShellCode實現(xiàn)跨進程傳輸,需要的可以參考下2023-12-12
這篇文章主要介紹了數(shù)據(jù)結構 順序棧的定義、初始化、空棧判斷、入棧、出棧操作的相關資料,需要的朋友可以參考下2017-06-06
C++11規(guī)定，允許將變量聲明為constexpr類型以便由編譯器來驗證變量的值是否是一個常量表達式，這篇文章主要介紹了C++11/C++14中constexpr的使用,需要的朋友可以參考下2023-06-06
下面小編就為大家?guī)硪黄獪\談C++中派生類對象的內存布局。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要介紹了C語言編程中如何來自定義C++個性化類型，文中附含詳細的示例代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-09-09