データ構造を使用しない逆スタック

Question

（余分な）データ構造を使用せずにスタックを逆転するにはどうすればよいですか？任意の提案や疑似コードが役立つ可能性があります。私は努力しており、実行可能な解決策を見つけることができませんでした。ここの問題は私もスタックの大きさではありません。私が何かを作ることを少なくとも進めることができると知ったら、事前に感謝します。

Answer 1

follows:のように2回再帰することができます。

void insert_at_bottom(node **stack, int data) 
{ 
    if(isempty(*stack)){ 
      push(stack,data); 
      return; 
    } 
    int temp=pop(stack); 
    insert_at_bottom(stack,data); 
    push(stack,temp); 
} 


void rev_stack(node **stack) 
{ 
    if(isempty(*stack)) return; 
    int temp = pop(stack); 
    rev_stack(stack); 
    insert_at_bottom(stack,temp); 
} 

Answer 2

再帰を使用して簡単に行うことができます。最大許容スタックサイズは、最大再帰深度によって制限されます。いくつかのコード：

public void reverse(Stack st) { 
    int m = (int)st.Pop(); 
    if (st.Count != 1) { 
     reverse(st); 
    } 
    Push(st , m); 
    } 

public void Push(Stack st , int a) { 
    int m = (int)st.Pop(); 
    if (st.Count != 0) { 
     Push(st , a); 
    } 
    else { 
     st.Push(a); 
     st.Push(m); 
    } 
}