대기열을 재귀 적으로 역전시키는 방법은 무엇입니까?

Question

다음 클래스 템플릿이 있고 외부/추가 데이터 구조를 사용하지 않고 reverse() 함수를 재귀 적으로 구현하고자합니다.

template <class T> struct Node { 
T value; Node<T> ∗next; 
}; 
template <class T> class Dynque 
{ 
protected : 
Node<T> ∗front; 
Node<T> ∗rear; 
int numItems ; public : 
Dynque(); 
Dynque (Dynque &) ; 
virtual ̃Dynque () ; 
virtual void enqueue (T) ; // add an element 
T dequeue();// remove an element from front 
bool isEmpty () ; 
int getNumItems () ; 
void clear(); // remove all elements 
void reverse(); // reverse order of elements 
}; 

Answer 1

그것은 개념적으로 생각하는 것이 유용 할 수 있습니다, 당신이 반복적으로 큐를 반대 것입니다 방법에 대해 설명합니다.

모든 좋은 재귀 함수와 마찬가지로 기본 사례가 필요하며 더 간단할수록 좋습니다! 합리적인 선택은 빈 큐를 선택하는 것입니다. 빈 대기열을 쉽게 반대로 되돌릴 수 있습니다. 그래서 우리는 다음과 같이이 함수를 작성하기 시작할 수 있습니다 :

template <typename T> void Dynque<T>::reverse() { 
    if (!isEmpty()) { 
     /* ... handle the recursive case ... */ 
    } 
} 

이제 우리는 재귀 적 사건에 대해 생각해야합니다. 우리가 비어 있지 않은 큐를 가지고 상상하고, 단순화를 위해, 다음과 같이 1, 2, 3, ..., N, 번호가의이 요소를 가정 해 봅시다 : 큐 작업 할 때

1 2 3 4 5 6 ... n-2 n-1 n 

것은, 우리가 단지에 액세스 할 수 정면의 요소. 첫 번째 요소, 그리고 다른 모든 것들 : 그래서 우리는 두 그룹으로이 큐 분할되어 있다고 가정 해 봅시다

| 
1 | 2 3 4 5 6 ... n-2 n-1 n 
    | 

지금을, 우리는 큐 역 할 때 우리가 결국 무엇을보고 :

        | 
n n-1 n-2 ... 6 5 4 3 2 | 1 
            | 

공지 사항을 그 여기에있는 것은 첫 번째 요소를 제외하고 큐의 모든 요소의 역순으로 다음에 큐의 첫 번째 요소가옵니다.

이것은 약간의 통찰력을 이끌어냅니다. 큐의 앞쪽에서 큐를 빼면 나머지는 "다른 것"으로 남습니다. 그런 다음 "그 외 모든 것"을 역으로하면 제거한 요소를 대기열에 추가 할 수 있고 원래 대기열의 역순으로 처리 할 수 ​​있습니다. 다음은이 모습은 다음과 같습니다

template <typename T> void Dynque<T>::reverse() { 
    if (!isEmpty()) { 
     T first = dequeue(); // Store the first element... 
     reverse();   // ... reverse everything else ... 
     enqueue(first);  // ... and enqueue the element we removed. 
    } 
} 

재귀 조치가 대기열을 통해 일어나고있는 큐의 상태로 변화의 결과로 발생되기 때문에 그것은, 인수가없는 재귀 함수를 볼 수 이상해 및 dequeue 작업.

이유가 궁금하신 분은 [1, 2, 3] 대기열을 취소하려고하면 어떻게되는지 생각해보십시오. 논리는 다음과 같이 보입니다.

To reverse `[1, 2, 3]`, we dequeue 1, then recursively reverse `[2, 3]. 
    To reverse `[2, 3]`, we dequeue 2, then recursively reverse `[3]`. 
     To reverse `[3]`, we dequeue 3, then recursively `[]`. 
      To reverse `[]`, we don't need to do anything! 
     Now we enqueue the 3 we removed to get `[3]`. 
    Now we enqueue the 2 we removed to get `[3, 2]`. 
Now we enqueue the 1 we removed to get `[3, 2, 1]`. 

메모는 매우 효율적인 방법으로 큐를 뒤집을 수 없습니다. 스택 공간을 사용하여 각 단계에서 제거 된 모든 요소를 ​​보유합니다. 명시적인 std::stack 객체 나 그와 비슷한 것을 사용하여 역전을 수행하는 것이 유리합니다 (역방향 함수를 자유 함수로 구현하는 경우). 또는 포인터를 내부적으로 다시 배열하여 모든 것을 재정렬 할 수 있다는 이점을 활용하는 것이 좋습니다. 이 솔루션을 조금만 최적화 해 볼 수도 있지만 근본적으로 다른 솔루션 전략을 선택하는 것보다 가치가 떨어집니다.

Answer 2

Node reverse(Node front) 
{ 
if(front==NULL) 
    return NULL; 
if(front->next==null) 
    return front; 
Node rev=reverse(front->next); 
front->next->next=front; 
front->next=null; 
return rev; 

} 

IT는 LinkedList의 반전처럼 작동합니다. 희망이 도움이됩니다.

Answer 3

그것은 (하지 테스트) 같은 것을해야한다 :

void reverse() { 
    // Base case 
    if (isEmpty()) return; 

    // Get head 
    T head = dequeue(); 
    // Reverse everything else 
    reverse(); 
    // Add head after reversion of everything else 
    enqueue(head); 
} 

Answer 4

enqueue()와 dequeue()는 모두 값에 대해 연산하므로 복사본을 만듭니다. 당신은 정말로 이러한 방법을 사용하고 싶지 않습니다. 당신은 데이터를 추가하거나 제거하지 않고, 단지 주위를 돌아 다니기 때문에, 그렇게 해봅시다.

void Dynque::reverse() 
{ 
    // No effect on 0 or 1 elements' count. 
    if (isEmpty() || !front->next) 
     return; 

    // Remember the element at the front by keeping a pointer to it. 
    Node<T>* move_me_to_back = front; 

    // "Erase" the first element. 
    front = front->next; 

    // Call again on now shortened queue. 
    // In the most nested call, the queue should have only one element, with front == back. 
    reverse(); 

    // "Insert" the last remembered element. 
    back->next = move_me_to_back; 

    // Update the pointer to back. 
    back = back->next; 
}