[C언어] Stack&Queue(5) - recursiveReverseQueue 함수 구현하기

Stack&Queue(5) - recursiveReverseQueue 함수 구현하기

재귀를 이용해 큐를 뒤집는 함수

주어진 요소 확인하기

구조체

• Queue: (struct) 큐 구조체
  • ll: (LinkedList) 큐 연산 구현을 위한 연결 리스트 구조체
• LinkedList: (struct) 연결 리스트 구조체
  • size: (int field) 연결 리스트 요소 갯수
  • *head: (pointer field) 연결 리스트 첫 노드의 주소
• ListNode: (struct) 노드 구조체
  • item: (int field) 노드의 값
  • *next: (pointer field) 다음 노드의 주소

recursiveReverseQueue 함수의 매개 변수

• *q: (pointer) 큐 주소

 

핵심 아이디어

• Base Condition: 큐가 비어 있다면 return
• 요소 하나를 꺼낸 후(dequeue), 재귀 호출
• 돌아오면서 요소를 하나씩 enqueue

 

구현하기

void recursiveReverseQueue(Queue *q) {
    // Base Condition: 큐가 비었으면 재귀 호출 종료(return)
    if (isEmptyQueue(q)) return;

    // 큐에서 값 하나 꺼내기
    int val = dequeue(q);

    // 나머지를 재귀적으로 뒤집기
    recursiveReverseQueue(q);

    // 꺼낸 값을 다시 큐에 삽입 → 결국 뒤집힌 순서로 삽입
    enqueue(q, val);
}