스택·큐 Q4. 스택을 이용해 큐 뒤집기

자료구조 C 실습 · 스택과 큐 · Q4

스택·큐 Q4. 스택을 이용해 큐 뒤집기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section C Stack and Queue reverse

큐의 원소를 반대 순서로 뒤집기 위해 임시 스택을 사용하는 문제다. 큐는 FIFO, 스택은 LIFO다. 이 두 규칙을 이어붙이면 순서를 한 번 뒤집을 수 있다는 것이 이 문제의 핵심이다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Stack_and_Queue\Q4_C_SQ.c

대상 함수: reverse

카테고리: 스택과 큐

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Insert an integer into the queue
• 2: Reverse the queue
• 0: Quit
• Input an integer that you want to insert into the queue
• The queue is
• The resulting queue after reversing its elements is

핵심 구현 흐름

STEP 1

큐가 빌 때까지 dequeue하면서 임시 스택에 push한다.

STEP 2

스택이 빌 때까지 pop한 값을 다시 큐에 enqueue한다.

STEP 3

결과적으로 맨 앞 원소가 맨 뒤로 가며 전체 순서가 역전된다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: reverse

void reverse(Queue *q)
{
	Stack s;
	s.ll.head = NULL;
	s.ll.tail = NULL;
	s.ll.size = 0;

	while (!isEmptyQueue(q))
		push(&s, dequeue(q));

	while (!isEmptyStack(&s))
		enqueue(q, pop(&s));
}

구현할 때 체크할 점

• 임시 스택을 초기화하지 않으면 이전 실행 결과가 섞인다.
• 큐/스택 helper가 head·tail을 제대로 갱신하는지 같이 봐야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 큐는 FIFO, 스택은 LIFO다. 이 두 규칙을 이어붙이면 순서를 한 번 뒤집을 수 있다는 것이 이 문제의 핵심이다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.