快捷導(dǎo)航

C++使用遞歸函數(shù)和棧操作逆序一個(gè)棧的算法示例

更新時(shí)間：2017年05月10日 11:20:11 作者：難免有錯(cuò)_

這篇文章主要介紹了C++使用遞歸函數(shù)和棧操作逆序一個(gè)棧的算法,結(jié)合實(shí)例形式分析了C++遞歸函數(shù)與逆序棧的相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了C++使用遞歸函數(shù)和棧操作逆序一個(gè)棧的算法。分享給大家供大家參考，具體如下：

題目：

一個(gè)棧依次壓入1、2、3、4、5，那么棧頂?shù)綏５追謩e為：5、4、3、2、1。
將這個(gè)棧逆置后棧頂?shù)綏５追謩e為1、2、3、4、5。
用遞歸函數(shù)來實(shí)現(xiàn)，不能用其他數(shù)據(jù)結(jié)構(gòu)。

解題思路及代碼

1、遞歸函數(shù)一：將棧的棧底元素一個(gè)個(gè)返回并移除。
2、遞歸函數(shù)二：逆序棧，調(diào)用遞歸函數(shù)一實(shí)現(xiàn)。

C++實(shí)現(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);
  }
};

程序測(cè)試用例：

#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");
}

運(yùn)行結(jié)果：

Before reverse:
6 5 4 3 2 1
After reverse:
1 2 3 4 5 6
請(qǐng)按任意鍵繼續(xù). . .

希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。

您可能感興趣的文章:

相關(guān)文章

C++編程中break語(yǔ)句和continue語(yǔ)句的學(xué)習(xí)教程
這篇文章主要介紹了C++編程中break語(yǔ)句和continue語(yǔ)句的學(xué)習(xí)教程,break和continue是C++循環(huán)控制中的基礎(chǔ)語(yǔ)句,需要的朋友可以參考下
2016-01-01
C++ 空指針解引用的解決方法
空指針解引用是一種常見且嚴(yán)重的錯(cuò)誤,它通常由于指針未初始化、被設(shè)置為nullptr或指向無效地址引起,本文主要介紹了C++ 空指針解引用的解決方法,感興趣的可以了解一下
2024-08-08
C++從匯編的視角審視對(duì)象的創(chuàng)建問題
這篇文章主要介紹了C++從匯編的視角看對(duì)象的創(chuàng)建,從匯編的視角來看，調(diào)用構(gòu)造器和調(diào)用 “返回對(duì)象” 的函數(shù)是一樣的，從匯編的角度來看，對(duì)象就是一堆數(shù)據(jù)的排列，比如說最普通的對(duì)象就是數(shù)據(jù)成員按照聲明順序直接排列，需要的朋友可以參考下
2022-01-01
C++中實(shí)現(xiàn)WebSocket通信的兩種方法：libwebsockets庫(kù)、Boost.Beast?庫(kù)
C++中WebSocket庫(kù)主要有以下幾個(gè)?：cpp-websocket?、asio_websocket?、websockets++?、?websocketpp?、?libwebsockets?、?uWebSockets?、Boost.Beast?、Simple-WebSocket-Server?,這篇文章使用libwebsockets庫(kù)、Boost.Beast?庫(kù)來實(shí)現(xiàn)c++中的WebSocket通信
2025-01-01
C語(yǔ)言實(shí)現(xiàn)影院售票管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)影院售票管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-08-08
C++ 輸入一行數(shù)字(含負(fù)數(shù))存入數(shù)組中的案例
這篇文章主要介紹了C++ 輸入一行數(shù)字(含負(fù)數(shù))存入數(shù)組中的案例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2020-12-12
C++二進(jìn)制翻轉(zhuǎn)實(shí)例分析
這篇文章主要介紹了C++二進(jìn)制翻轉(zhuǎn),通過幾個(gè)實(shí)例分析二進(jìn)制翻轉(zhuǎn)算法的實(shí)現(xiàn)技巧,需要的朋友可以參考下
2014-09-09
C指針原理教程之AT&T匯編
AT&T 匯編是一種和intel匯編在語(yǔ)法上完全不同的匯編語(yǔ)言，為避免混淆intel語(yǔ)法，本文只介紹AT&T匯編，AT&T的第一個(gè)特點(diǎn)就是每個(gè)寄存器名前必須加‘%’,立即數(shù)前必須加‘$’
2019-02-02
VC實(shí)現(xiàn)的病毒專殺工具完整實(shí)例
這篇文章主要介紹了VC實(shí)現(xiàn)的病毒專殺工具完整實(shí)例,詳細(xì)講述了針對(duì)病毒的進(jìn)程終止、刪除文件及回復(fù)注冊(cè)表與啟動(dòng)項(xiàng)等,同時(shí)介紹了與之相關(guān)的系統(tǒng)函數(shù),非常具有參考借鑒價(jià)值,需要的朋友可以參考下
2014-10-10
C語(yǔ)言指針變量作為函數(shù)參數(shù)的實(shí)現(xiàn)步驟詳解
這篇文章主要介紹了C語(yǔ)言指針變量作為函數(shù)參數(shù)的實(shí)現(xiàn)步驟，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧
2023-02-02