재귀 적으로 스택을 검색하지만 스택은 그대로 두십시오.

Question

스택을 검색하지만 스택을 원래 상태로 유지하는 재귀 함수를 작성하려고했습니다. 나는 고비를 내고 스택을 터뜨릴 수 있지만 도우미 스택이나 다른 데이터 구조는 사용하지 않습니다.

네, 숙제입니다. 완전한 코딩 된 대답은 기대하지 않습니다. :). 재귀 검색이 완료된 후에 스택이 손상되지 않도록 스택에 접근하는 방법에 대한 약간의 도움이됩니다.

지정된 항목에 대한 스택을 검색합니다 (그러나 스택을 파괴) 재귀 함수는 아래와 같습니다 :

template <class Type> 

Type getNth(stack(Type) & s, int n) 

{ 

    if(s.empty()) 
     return -1; 
    if(s.top() == n) 
     return s.top(); 
    if(s.top() != n && s.empty()) 
     return -1; 
    else 
     s.pop(); 
     return getNth(s, n); 
} 

이것은 지금까지 작동합니다. 어떤 도움을 크게 반환하기 전에 pop() 에드 값 다시는 pop() 에드 값, 재귀 호출 결과 및 push()을 저장해야

Answer 1

감사.

하여 다른 사람이 그런 일 같아야합니다

else 
    temp = s.pop(); 
    retVal = getNth(s, n); 
    s.push(temp); 
    return retVal; 

(*)가 temp 및 retVal를 선언하지 용서해 [그 이외의, 그것은 괜찮 은데,이에서 일반적인 생각을 이해할 수있다 ..

---

편집 : 나는, 무슨 일이 일어나고 있는지 간단한 예제를 추가하려면 스택을 가정하기로 결정
는

,691,363입니다 (210)

|1| 
|2| 
|3| 
|4| 
--- 

당신은 getNth (들, 3)을 호출 할 수 있습니다 :이 첫번째 팝업()와 getNth() 후 스택
에 무슨 일이 일어날 것입니다 : 조건에 도달하지 않은 중지, 그래서 계속]

|2| 
|3| 
|4| 
--- 

2 팝업(), getNth() : 지금

|3| 
|4| 
--- 

[다시, 계속] s.top() == n을, 당신은 그들이 실현 경우 확인! 그래서 너는 n을 반환한다. 다시 재귀 오는 경우
는 s.push(temp) 호출 및 temp==2, 그래서 우리는 얻을 수있다 :

|2| 
|3| 
|4| 
--- 

우리가 재귀에서 이제 다시, 다시 RETVAL을 반환, 우리는 다시 s.push()를 사용하고 우리가 얻을 :

|1| 
|2| 
|3| 
|4| 
--- 

원본 스택! 재귀에 의해 반환 된 동일한 returnVal을 반환합니다.

참고 :이 당신의 질문이 아니라 함수의 이름은 당신이 찾고 있던 값을 반환하지 않는 것을 의미하지만, 스택 오히려 번째 요소, 의미, 당신의 스택 경우 입니다 :

|5| 
|8| 
|8| 
|8| 
|2| 
|4| 
--- 

getNth(2) 귀하의 질문에 설명으로, 8, NOT 2를 반환해야합니다.
하지만 그 사실을 확실히 알 수는 없지만 문제가 너무 많지 않으면이 질문을 처리 할 수있는 도구가 충분하다고 생각합니다!

행운을 빈다! EDIT 2

---

: 코멘트에 토론 후
, 영업 이익은 원래의 질문이 무엇을 설명 후, 조금 다른 것을, 그래서 때문에 여분의 편집 싶었던 것이 분명하다 :

당신의 솔루션은 요소를 검색하고 그것을 반환합니다. 아마도 여러분이하고 싶은 것은이 요소가 반환 될 때까지 반환해야합니다. [다시 말하면 모든 변수를 선언하지 않고 컴파일하지 않고 단지 방향 일뿐입니다] :

template <class Type> 
Type getNth(stack(Type) & s, int n) 
{ 
    if(s.empty()) {return -1; } //note that in C++ throwing an exception here will be more wise, since -1 might be not matching to Type 
    else if(n == 0) { return s.top(); } 
    else { 
     temp = s.pop(); 
     retVal = getNth(s, n-1); 
     s.push(temp); 
     return retVal; 
    } 
}