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

Stack&Queue(4) - reverseQueue 함수 구현하기

스택을 이용하여 큐를 뒤집는 함수

주어진 요소 확인하기

구조체

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

reverseQueue 함수의 매개 변수

• *q: (pointer) 큐 주소

 

핵심 아이디어

• 큐가 비어 있다면 return
• 큐에서 dequeue를 통해 꺼낸 값을 임시 스택에 push
• 임시 스택에서 pop을 통해 꺼낸 값을 큐에 enqueue

 

구현하기

void reverseQueue(Queue *q) {
	// 큐가 비어 있다면 return
    if (q == NULL) return;

    // 임시 스택 동적 할당 및 초기화
    Stack *tmp = malloc(sizeof(Stack));
    tmp->ll.head = NULL;
    tmp->ll.tail = NULL;
    tmp->ll.size = 0;

    // 큐의 모든 원소 dequeue, 스택에 push → 순서 뒤집기 준비
    while (!isEmptyQueue(q)) {
        push(tmp, dequeue(q));
    }

    // 스택의 모든 원소 pop, 큐에 enqueue → 순서 뒤집기 완료
    while (!isEmptyStack(tmp)) {
        enqueue(q, pop(tmp));
    }

    // 메모리 해제 (스택 구조체 자체만, 내부 노드는 pop에서 제거됨)
    free(tmp);
}