WEEK 05 C언어 스택 앤 큐 1,2,3,4번 문제(4월15일 화요일)

저번 포스팅에 이어서 스택 앤 큐에 풀어본 문제에 대해 작성해봤습니다.

1. C언어 Stack and Queue 1번

1. createQueueFromLinkedList

문제 설명:

연결 리스트에 저장된 정수들을 모두 큐에 넣어(linked-list 기반 큐) 새로운 큐를 생성하는 C 함수를 작성하세요.

첫 번째 노드부터 순서대로 enqueue() 하며, 큐가 비어 있지 않다면 먼저 비워야 합니다.

함수 원형:

void createQueueFromLinkedList(LinkedList *ll , Queue *q);

예시:

입력 연결 리스트가 1, 2, 3, 4, 5일 경우:

결과 큐는 1 2 3 4 5

[풀이 방법]

1. 노드 첫번째부터 지정
2. NULL일때까지 실행(밑에 과정)
3. 연결리스트의 각 값을 큐에 삽입
4. 커서를 다음 노드로 옮깁니다.

[코드와 해설]

void createQueueFromLinkedList(LinkedList *ll, Queue *q)
{
    /* 연결 리스트를 큐로 복사하는 함수 */
    ListNode *cur = ll->head;   // 노드 첫번째부터 지정
    while (cur != NULL) {       // NULL일때까지 실행
        enqueue(q, cur->item);  // 연결 리스트의 각 값을 큐에 삽입
        cur = cur->next;        // 커서를 다음으로 옮긴다
    }
}

[번외] 큐에서 짝수만 꺼내기

void removeOddValues(Queue *q)  // 구현 안해도되는 문항임(짝수 제거 우선)
{
    if(q == NULL)   // q가 NULL이면 그냥 리턴
    return;

    int count = q -> ll.size;    // 큐에 들어간 길이만큼 받아오기위함

    for(int i = 0; i < count; i++){
        int item = dequeue(q);  // 큐의 모든 item을 순회하면서 각 큐에서 제거
        if (item % 2 == 0)      // 그 아이템이 짝수인 경우 다시 큐에 추가
        enqueue(q, item);       // 다시 큐에 넣음
    }
}

---

2. C언어 Stack and Queue 2번

2. createStackFromLinkedList

문제 설명:

연결 리스트에 저장된 정수들을 모두 스택에 push() 하여 새로운 스택(linked-list 기반)을 생성하는 C 함수 작성.

첫 번째 노드부터 순서대로 push() 하며, 스택이 비어 있지 않다면 먼저 비워야 합니다.

함수 원형:

void createStackFromLinkedList(LinkedList *ll , Stack *stack);

예시:

입력 연결 리스트가 1, 3, 5, 6, 7이면

결과 스택은 7 6 5 3 1

[풀이 방법]

1. 첫번째 노드부터 지정
2. NULL일때까지 반복(밑의 과정)
3. 스택을 구현하기위해 item을 push로 넣습니다.
4. 커서를 다음 노드로 옮깁니다.

[코드와 해설]

void createStackFromLinkedList(LinkedList *ll, Stack *s)
{
    ListNode *cur = ll->head;
    while (cur != NULL) {
        push(s, cur->item);
        cur = cur -> next;
    }
}

[번외] 큐에서 짝수만 꺼내기

void removeEvenValues(Stack *s)
{
    Stack stack;            //새로운 stack 생성
    stack.ll.head = NULL;
    stack.ll.size = 0;

    while(!isEmptyStack(s))
    {
        push(&stack, pop(s));    //원래 스택에서 아이템을 꺼내 임시 스택에 넣음
    }

    while(!isEmptyStack(&stack))
    {
        int item = pop(&stack);        //임시 스택에서 아이템을 꺼내서 홀수인 경우, 원래 스택에 다시 pop
        if(item % 2 != 0)
            push(s,item);
    }
}

---

3. C언어 Stack and Queue 3번

3. isStackPairwiseConsecutive

문제 설명:

스택에 저장된 정수들이 짝지어서 연속된 값인지(pairwise consecutive) 확인하는 C 함수 작성.

※ 오직 push()와 pop()만 사용해야 합니다.

함수 원형:

int isStackPairwiseConsecutive(Stack *s);

예시:

• (16, 15, 11, 10, 5, 4) → 연속됨
• (16, 15, 11, 10, 5, 1) → 연속되지 않음
• (16, 15, 11, 10, 5) → ※ 스택의 크기가 홀수이면 연속되지 않음

※ 구현 팁:

if size odd return 0
else check every pair, any not-satisfied return 0
all check passed then return 1

[풀이 방법]

1. 만약에 스택의 크기가 홀수이면 연속되지 않음.(예외처리)
2. 순회하여 두 개 값 비교하여 연속되면 통과하고 다음 케이스 확인
3. 그렇지 않으면 연속되지 않음.

[코드와 해설]

int isStackPairwiseConsecutive(Stack *s)
{
  /* 
  1. 만약에 스택의 크기가 홀수이면 연속되지 않음.(예외처리)
  2. 순회하여 두 개 값 비교하여 연속되면 통과하고 다음 케이스 확인
  3. 그렇지 않으면 연속되지 않음.
  */

  Stack temp;
  temp.ll.head = NULL;  // 첫 헤드값은 NULL임
  temp.ll.size = 0;  // 사이즈도 0일 것임

  if(s->ll.size % 2 != 0)
  return 0;   // 비정상 출력

  while(!isEmptyStack(s)){
    push(&temp, pop(s));
  }

  while(!isEmptyStack(&temp)){
    int item1 = pop(&temp);
    int item2 = pop(&temp);

    if(abs(item1 - item2) != 1)   // 두개를 뺄을 때, 차가 1이면 연속된 수이다.(절댓값이 쓰어져야 -1이어도 판정가능)
    return 0;    // 정상 출력
  }
  return 1;  // 위 사항 빼고는 모두 비정상 출력
}

---

4. C언어 Stack and Queue 4번

4. reverseQueue

문제 설명:

큐를 스택을 이용해 뒤집는(reverse) 반복적 C 함수 작성.

※ 스택은 push(), pop()만 사용하고 큐는 enqueue(), dequeue()만 사용해야 합니다.

함수 원형:

void reverseQueue(Queue *q);

예시:

입력 큐: (1, 2, 3, 4, 5) → 결과 큐: (5, 4, 3, 2, 1)

[풀이 방법]

스택을 이용해서 큐를 뒤집습니다.
GPT의 도움을 받아 로직을 고민했습니다.

1. 큐에서 앞쪽 요소부터 꺼내고(dequeue), 꺼낸 요소를 스택에 쌓음(push)
2. 다시 스택에서 5부터 하나씩 꺼내고(pop), 큐에 다시 넣는다(enqueue)
   직접 예시를 생각하면 풀어보면 이해하기 수월합니다.

[코드와 해설]

void reverse(Queue *q)
{
/*
스택을 이용해서 큐를 뒤집습니다.
GPT의 도움을 받아 로직을 고민했습니다.
1. 큐에서 앞쪽 요소부터 꺼내고(dequeue), 꺼낸 요소를 스택에 쌓음(push)
2. 다시 스택에서 5부터 하나씩 꺼내고(pop), 큐에 다시 넣는다(enqueue)
직접 예시를 생각하면 풀어보면 이해하기 수월하다.
*/
    // 초기화줄
    Stack s;
    s.ll.head = NULL;
    s.ll.size = 0;

    while(!isEmptyQueue(q)){
        push(&s, dequeue(q));   // 큐에서 앞쪽 요소부터 꺼내고(dequeue), 꺼낸 요소를 스택에 쌓음(push)
        // (1,2,3,4,50 라면 1꺼내고 스택에 쌓는다. (1,2,3,4,5)이고 5가 상단
    }

    while(!isEmptyStack(&s)){
        enqueue(q, pop(&s));    // 다시 스택에서 5부터 하나씩 꺼내고(pop), 큐에 다시 넣는다(enqueue)
        // (5,4,3,2,1) 순으로 큐에 넣어진다. 
    }
}

---

이렇게 4가지의 스택앤 큐 문제를 풀고 끝냈습니다. 새벽 4시에 집으로 돌아갔습니다.