[자료구조] 스택과 큐(Stack and Queue) 재귀(Recursion)를 이용한 큐 뒤집기(Queue Reverse) 구현(C 언어)

문제 설명

이번 포스트에서는 재귀 함수를 활용하여 큐(Queue)의 원소들을 반전시키는 방법에 대해 알아보겠습니다. 이전에는 스택을 이용한 방법을 살펴보았지만, 이번에는 재귀 호출을 통해 큐의 순서를 뒤집는 방법을 중점적으로 다루겠습니다.

정수형 큐가 주어졌을 때, 큐의 원소들을 반전시키는 함수 reverseQueue()를 구현하는 것이 목표입니다. 예를 들어, 큐에 저장된 원소가 (1, 2, 3, 4, 5)라면, 함수를 호출한 후 결과는 (5, 4, 3, 2, 1)이 되어야 합니다.

---

문제 요구사항

 

• 입력: 정수형 큐 q​
• 출력: 큐 q의 원소 순서를 반전시킨 상태​
• 제약 조건:
  • 큐가 비어있을 경우, 아무 작업도 수행하지 않고 함수를 종료해야 합니다.​
  • 큐의 원소들은 정수형이며, 큐는 연결 리스트로 구현되어 있습니다.​
  • 재귀 호출을 활용하여 큐의 원소들을 반전시켜야 합니다.

---

 

문제 코드 설명

1. 구조체 정의

1 - 1 노드 구조체

typedef struct _listnode {
    int item;               // 노드의 값
    struct _listnode *next; // 다음 노드의 주소
} ListNode;

• item: 노드가 담고 있는 값 (정수)​
• next: 다음 노드를 가리키는 포인터

1 - 2 연결리스트 구조체

typedef struct _linkedlist {
    int size;        // 연결 리스트 요소(노드) 개수
    ListNode *head;  // 연결 리스트의 첫 노드 주소
    ListNode *tail;  // 연결 리스트의 마지막 노드 주소
} LinkedList;

• size: 연결 리스트의 노드 개수​
• head: 연결 리스트 첫 노드의 주소
• tail: 연결 리스트 마지막 노드의 주소

1 - 3 큐 구조체

typedef struct _queue {
    LinkedList ll;
} Queue;

• ll: 큐의 데이터 저장을 위한 연결 리스트

2. 함수 원형

void recursiveReverse(Queue *q);

• 매개변수: Queue *q – 반전할 큐의 포인터​
• 반환값: 없음 (void형)

---

재귀를 이용한 큐 뒤집기 플로우 차트

 

• 시작
  프로세스를 시작합니다.
• 큐가 비어있는가?
  • 예: 프로세스를 종료합니다.​
  • 아니요: 다음 단계로 진행합니다.​
• 큐의 앞에서 원소를 꺼냄
  dequeue(q)를 호출하여 큐의 앞에서 원소를 하나 꺼냅니다.
• 재귀 호출
  recursiveReverse(q)를 호출하여 나머지 큐에 대해 동일한 작업을 수행합니다.
• 꺼낸 원소를 큐의 뒤에 삽입
  enqueue(q, temp)를 호출하여 꺼냈던 원소를 큐의 뒤에 다시 삽입합니다.
• 종료
  프로세스를 종료합니다.

 

---

구현

// 큐의 원소들을 재귀적으로 반전시키는 함수
void recursiveReverse(Queue *q)
{
    // 기저 조건(Base Case): 큐가 비어있으면 아무 작업도 하지 않고 종료
    if (q->ll.head == NULL)
        return;

    // 큐의 앞에서 원소를 하나 꺼냄
    int temp = dequeue(q);

    // 나머지 큐에 대해 재귀적으로 reverse 함수를 호출
    recursiveReverse(q);

    // 재귀 호출이 끝난 후, 꺼냈던 원소를 큐의 뒤에 다시 삽입
    enqueue(q, temp);
}