정글 5주차 과제로는 기본적으로 제공하는 자료구조 구조체 및 함수를 이용해서, 다양한 응용문제를 풀게 됩니다.

블로그에서 모든 응용문제를 다루기보다는, 기본 제공 코드의 구조체 및 함수의 동작 원리만 분석할 계획입니다. 사실 이걸 제대로 알면 응용문제를 푸는 게 더 수월할 거에요.

• 따라서 코드는 제가 직접 작성하진 않았고(약간의 수정은 있음) 정글에서 제공한 코드입니다. 물론 주석, 설명이랑 그림은 제가 추가했습니다!

스택에 대한 상세한 설명은 이 글을 참고해주세요

본 글의 전체 소스 코드는 깃허브에 올려 두었습니다

구조체 선언

• 본 코드에서는 이전 글에서 구현한 연결 리스트를 이용해 스택을 구현
  • insertNode, removeNode, printList 등 함수 사용. 기억이 안 나면 이전 글을 보고 올 것
• 스택 최상단의 데이터가 머리 노드에 위치
• 이후 스택의 상단에서 하단 순서대로 연결 리스트의 노드가 이어짐
  • 푸시 연산: 연결 리스트의 맨 앞에 값을 추가하면 됨
  • 팝 연산: 연결 리스트의 머리 노드를 제거하면 됨

// 각 노드를 나타내는 구조체 Node
typedef struct _listnode{
    int item;                   // 노드에 저장된 값
    struct _listnode *next;     // 다음 노드를 가리키는 포인터
} ListNode;

// 연결 리스트 전체를 나타내는 구조체 LinkedList
typedef struct _linkedlist{
    int size;                   // 연결 리스트의 원소 수
    ListNode *head;             // 머리 노드
} LinkedList;

// 스택을 나타내는 구조체 Stack
typedef struct _stack {
    LinkedList ll;
} Stack;

• 보통 함수는 Stack *s와 같이, Stack 구조체를 가리키는 포인터를 매개변수로 받음
• s는 포인터기 때문에, s -> ll을 이용해 연결 리스트에 접근
  • (s -> ll).head, (s -> ll).size을 이용해 head, size 멤버에 접근

스택이 비어 있는지 확인

• 스택이 비어 있을 때 팝을 하거나 최상단 값을 반환하는 오류를 막기 위해,
• 스택이 비어 있는지 확인할 방법이 필요함

int isEmptyStack(Stack *s){
	if (s == NULL) return 1;	// 스택이 없는 경우

    // 원소 수가 0개거나 머리 노드가 존재하지 않음
    if ((s -> ll).size < 1 || (s -> ll).head == NULL){
        return 1;   // 참, 비어 있음
    } else{
        return 0;   // 거짓, 비어 있지 않음
    }
}

• 스택의 원소 수가 1개 미만이거나 ((s -> ll).size < 1)
• 머리 노드가 존재하지 않으면 ((s -> ll).head == NULL)
  • 스택이 비어 있으니 1 반환 (참)
  • 둘 중 하나만 체크해도 정상 작동하나, 혹시 모를 오류를 위해 둘 다 확인
• 비어 있지 않은 경우 0 반환 (거짓)

스택에 원소 푸시

// 스택에 값 item을 푸시
void push(Stack *s, int item){
	if (s == NULL) return;	// 스택이 없는 경우
    
    // 연결 리스트의 인덱스 0에 노드 삽입
    insertNode(&(s -> ll), 0, item);
}

• 스택 구조체 내 연결 리스트의 주소 &(s -> ll)를 insertNode 함수에 전달
• 0번째 인덱스에 item을 삽입하여, 새 원소를 스택의 맨 위에 쌓음

스택에서 원소 팝

// 스택의 최상단 원소를 제거해 반환
int pop(Stack *s){
	if (s == NULL) return -99999;	// 스택이 없는 경우 에러 (-99999)
    // 스택이 비어있지 않는 경우 (머리 노드 존재)
    if (isEmptyStack(s) == 0){
        // 0번째 값 저장
        int pop_value = (s -> ll).head -> item;
        // 0번째 노드 제거
        removeNode(&(s -> ll), 0);
        return pop_value;
    } else {
        return -99999;  // 스택이 빈 경우 -99999 반환 (에러)
    }
}

• 스택이 비어 있지 않은 경우 (앞서 만든 isEmptyStack 사용)
  • 머리 노드의 값 ((s -> ll).head -> item)을 pop_value에 저장
  • removeNode 함수를 이용해 0번째 노드를 제거
  • 이후 pop_value 반환
• 스택이 비어 있는 경우, 에러를 뜻하는 -99999 반환

스택의 최상단 값 반환

// 스택의 최상단 값 반환
int peek(Stack *s){
	if (s == NULL) return -99999;	// 스택이 없는 경우 에러 (-99999)

    // 스택이 비어있지 않는 경우 (머리 노드 존재)
    if (isEmptyStack(s) == 0){
        // 머리노드의 값 반환
        return (s -> ll).head -> item;
    } else {
        return -99999;  // 스택이 빈 경우 -99999 반환 (에러)
    }
}

• 스택이 비어 있지 않은 경우 (앞서 만든 isEmptyStack 사용)
  • 머리 노드의 값 ((s -> ll).head -> item) 반환
• 스택이 비어 있는 경우, 에러를 뜻하는 -99999 반환

동작과정

int main(void){
    Stack s;
    // 스택 내 연결 리스트의 size는 0, head는 NULL로 초기화
    s.ll.size = 0;
    s.ll.head = NULL;
    
    // 스택에 푸시
    push(&s, 41);
    push(&s, 9);
    push(&s, 33);

    // 스택에서 팝
    printf("팝한 원소: %d\n", pop(&s));
    // [출력] 팝한 원소: 33

    // 다시 푸시
    push(&s, 1);
    push(&s, 10);

    // 최상단 값 확인
    printf("최상단 값: %d\n", peek(&s));
    // [출력] 최상단 값: 10
    
    // 현재 스택 확인
    printList(&(s.ll));
    // [출력] 10 1 9 41 (상단 -> 하단 순으로 출력)

    // 스택의 크기 확인
    printf("스택의 크기: %d\n", s.ll.size);
    // [출력] 스택의 크기: 4
    
    // 모든 원소 제거 및 메모리 할당 해제
    removeAllItems(&(s.ll));

    return 0;
}

• 스택 내 연결 리스트의 크기는 0, 머리 노드는 NULL로 초기화
• 전 글에서 만든 printList 함수로 연결 리스트의 주소(&(s.ll))를 보내면 현재 스택을 출력할 수 있음
  • 최상단 원소부터 차례로 상단 -> 하단 순으로 출력됨에 유의하기
• 연결 리스트의 크기 (s.ll.size)로 스택의 크기를 확인할 수 있음
• 메모리 할당 해제는, 전 글에서 만든 removeAllItems 함수 사용