스택·큐 Q2. 연결 리스트로 스택 만들고 짝수 제거하기

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

스택·큐 Q2. 연결 리스트로 스택 만들고 짝수 제거하기

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

Section C Stack and Queue createStackFromLinkedListremoveEvenValues

연결 리스트를 스택으로 옮기고, 그 스택에서 짝수 값만 제거하는 두 함수를 구현하는 문제다. 같은 데이터라도 큐로 보느냐 스택으로 보느냐에 따라 '순서 보존' 방식이 달라진다. 여기서는 push 방향 때문에 입력 순서가 역전된다는 점이 핵심이다.

한눈에 보는 문제 정보

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

대상 함수: createStackFromLinkedList, removeEvenValues

카테고리: 스택과 큐

문제에서 요구한 것

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

• 1: Insert an integer into the linked list
• 2: Create the stack from the linked list
• 3: Remove even numbers from the stack
• 0: Quit
• Input an integer that you want to add to the linked list
• The resulting linked list is

핵심 구현 흐름

STEP 1

연결 리스트를 앞에서부터 읽으며 스택에 push한다.

STEP 2

스택을 순회하면서 짝수 값을 걸러낸다.

STEP 3

필요하면 임시 스택을 이용해 원래 순서를 복구한다.

핵심 코드

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

핵심 코드: createStackFromLinkedList

void createStackFromLinkedList(LinkedList *ll, Stack *s)
{
    ListNode *cur;
	cur = ll->head;
	if ( s != NULL)
	{	
		while (!isEmptyStack(s))
		{
			pop(s);
		}


	}
	while (cur != NULL)
	{
		push( s, cur->item);
		cur= cur ->next;
	}
}

핵심 코드: removeEvenValues

void removeEvenValues(Stack *s)
{	
	Stack temp;
    int item;
    int count = s->ll.size;
	temp.ll.head = NULL;
    temp.ll.size = 0;

    for (int i = 0; i < count; i++)
    {
        item = pop(s);

        if (item % 2 != 0)
        {
            push(s, item);
        }
	}
	while (!isEmptyStack(&temp))
    {
    	push(s, pop(&temp));
    }

}

구현할 때 체크할 점

• 큐처럼 enqueue하듯 옮기면 스택의 top 순서가 달라진다.
• 짝수를 제거한 뒤 남은 값의 순서를 어떤 기준으로 유지할지 미리 정해야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 같은 데이터라도 큐로 보느냐 스택으로 보느냐에 따라 '순서 보존' 방식이 달라진다. 여기서는 push 방향 때문에 입력 순서가 역전된다는 점이 핵심이다.

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