遞歸反轉堆棧

Question

我需要在C++中使用遞歸來反轉堆棧。我只能使用pop,push和reverseStack,沒有額外的功能，例如insertAtBottom，這是我在搜索stackoverflow和web時發現的。

我已經試過：

void Stack::reverseStack(){ 
    if (isEmpty()) 
     return; 
    else{ 
     int x; 
     pop(x); 
     reverseStack(); 
     push(x); 
    } 
} 

，但是這將創建一個堆完全一樣原始。

Answer 1

您需要實現的功能在底部插入一個項目一個例子是

void Stack::insertAtBottom(int item) { 
    if(isEmpty()) 
     push(item); 
    else { 
     int x; 
     pop(x); 
     insertAtBottom(item); 
     push(x); 
    } 
} 

此時您可以實現反向如下

void Stack::reverseStack(){ 
    if (isEmpty()) 
     return; 
    else{ 
     int x; 
     pop(x); 
     reverseStack(); 
     insertAtBottom(x); 
    } 
} 

編輯： 如果他們需要在一個功能中，以下是兩者的組合

void Stack::reverseStack(bool reverse=true,int item=0){ 
    if(reverse) { 
     if (isEmpty()) 
      return; 
     else{ 
      int x; 
      pop(x); 
      reverseStack(); 
      reverseStack(false,x); 
     } 
    } else { 
     if(isEmpty()) 
      push(item); 
     else { 
      int x; 
      pop(x); 
      reverseStack(false,item); 
      push(x); 
     } 
    } 
} 

乾杯！

Answer 2

#include <iostream> 
#include <stack> 

using namespace std; 

stack<int> S, R; // S is original stack, R is reversed stack 

void reverseStack() { 
    if(!S.empty()) { 
     R.push(S.top()); 
     S.pop(); 
     reverseStack(); 
    } 
    return; 
} 

int main() { 
    S.push(1); 
    S.push(2); 
    S.push(3); 
    S.push(4); 
    S.push(5); 

    reverseStack(); 

    // Check if R is reversed 
    while(!R.empty()) { 
     cout << R.top() << " "; 
     R.pop(); 
    } 
    return 0; 
} 

希望這有助於！