反向堆棧不使用任何數據結構

Question

如何反向堆棧而不使用任何（額外）數據結構？任何建議或僞代碼都可能有幫助。我試圖找不到任何可行的解決方案。這裏的問題是我不知道堆棧的大小。如果我知道我可以至少繼續創造一些東西，請提前致謝。

Answer 1

這可以通過雙遞歸來完成，如follows:。

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