[C언어] 큐(Queue) 구현 실습하기

큐(Queue) 구현 실습하기

이번 큐 구현 실습은 이전에 다뤘던 연결 리스트(Linked List) 구현체를 그대로 활용하여 진행됩니다. 즉, 연결 리스트를 기반으로 한 큐(Queue) 를 C 언어로 구현해보는 실습입니다.

 

따라서, 연결 리스트를 구현해본 적이 없다면 [연결 리스트 구현 실습하기]를 한 번 따라가 보셔도 좋고, 큐 구현부터 시작하고 싶다면 해당 글에서 연결 리스트의 구성과 기본 함수 정의만 빠르게 훑고 넘어오셔도 괜찮습니다.

 

 

필요한 구조체, 함수 정의하기

구조체

• Queue: (struct) 큐 구조체
  • ll: (LinkedList) 큐 연산 구현을 위한 연결 리스트 구조체
• LinkedList: (struct) 연결 리스트 구조체
• ListNode: (struct) 노드 구조체

함수 (추천 구현 순서)

• void enqueue(Queue *q, int item): 큐의 뒤에 요소 추가
• int isEmptyQueue(Queue *q): 큐가 비어있는지 확인
• int dequeue(Queue *q): 큐의 앞에서 요소를 꺼내고 제거
• void removeAllItemsFromQueue(Queue *q): 큐의 모든 요소를 제거
• ListNode *findNode(LinkedList *ll, int index): 연결 리스트에서 index에 해당하는 노드의 주소를 찾아 반환
• int insertNode(LinkedList *ll, int index, int value): index 위치에 새 노드를 삽입. 성공 시 0, 실패 시 -1 반환
• int removeNode(LinkedList *ll, int index): index 위치의 노드를 삭제. 성공 시 0, 실패 시 -1 반환
• void printList(LinkedList *ll): 연결 리스트의 모든 노드 값을 순서대로 출력
• void removeAllItems(LinkedList *ll): 연결 리스트의 모든 노드를 제거하고 초기화

 

전체 실습 코드

연결 리스트를 활용한 큐 구현 실습용 뼈대 코드입니다. 각 함수에는 간단한 힌트가 주석으로 포함되어 있어, 스스로 고민하며 구현해볼 수 있게끔 되어 있습니다. 칠판이나 노트에 그림을 그려 보면서 기본 함수들을 하나씩 구현해 보세요.

#include <stdio.h>
#include <stdlib.h>

// 연결 리스트 구조체
typedef struct _listnode{
	int item;
	struct _listnode *next;
} ListNode;
// 노드 구조체
typedef struct _linkedlist{
	int size;
	ListNode *head;
} LinkedList;
// 큐 구조체
typedef struct _queue
{
	LinkedList ll;
} Queue;

// 기본 함수 선언
void enqueue(Queue *q, int item);
int isEmptyQueue(Queue *q);
int dequeue(Queue *q);
void removeAllItemsFromQueue(Queue *q);

ListNode *findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);
void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);

// 큐 기본 함수 확인용 프로그램
// 함수 구현 후 C파일을 실행해 제대로 동작하는지 테스트해볼 수 있습니다.
int main() {
    Queue q;
    q.ll.head = NULL;
    q.ll.size = 0;

    int c = 1;
    int value, result;

    printf("===== 큐 테스트 메뉴 =====\n");
    printf("1: enqueue(value)\n");
    printf("2: dequeue()\n");
    printf("3: isEmptyQueue()\n");
    printf("4: printList()\n");
    printf("5: removeAllItemsFromQueue()\n");
    printf("0: 종료\n");

    while (c != 0) {
        printf("\n메뉴 선택 (0~5): ");
        scanf("%d", &c);

        switch (c) {
        case 1:
            printf("삽입할 값을 입력하세요: ");
            scanf("%d", &value);
            enqueue(&q, value);
            printf("삽입 성공!\n");
            printList(&(q.ll));
            break;

        case 2:
            result = dequeue(&q);
            if (result != -1) {
                printf("꺼낸 값: %d\n", result);
            } else {
                printf("큐가 비어 있습니다.\n");
            }
            printList(&(q.ll));
            break;

        case 3:
            if (isEmptyQueue(&q))
                printf("큐는 비어 있습니다.\n");
            else
                printf("큐에 값이 존재합니다.\n");
            break;

        case 4:
            printList(&(q.ll));
            break;

        case 5:
            removeAllItemsFromQueue(&q);
            printf("모든 요소 제거 완료!\n");
            printList(&(q.ll));
            break;

        case 0:
            removeAllItemsFromQueue(&q);
            printf("프로그램 종료.\n");
            break;

        default:
            printf("알 수 없는 선택입니다.\n");
            break;
        }
    }

    return 0;
}

// 큐의 뒤에 요소를 추가하는 함수
void enqueue(Queue *q, int item) {
    /*  리스트의 어느 위치에 넣는 게 적절할까요?
        add your code here  */
}

// 큐가 비어있는지 확인하는 함수
// 큐가 비어있으면 1, 아니면 0을 반환
int isEmptyQueue(Queue *q) {
    /*  연결 리스트의 어떤 값을 활용하면 될까요?
        add your code here  */
}

// 큐의 앞에서 요소를 꺼내고 제거하는 함수
// 큐가 비어있다면 -1, 아니면 꺼낸 값을 반환
int dequeue(Queue *q) {
    /*  먼저 확인해야 할 조건은 무엇일까요? 
        꺼낸 뒤에는 어떤 처리가 필요할까요?
        add your code here  */
}

// 큐의 모든 요소를 제거하는 함수
void removeAllItemsFromQueue(Queue *q) {
    /*  큐가 빌 때까지 어떤 작업을 반복하면 될까요?
        add your code here  */
}

// ==================== 기존 연결 리스트 기본 함수 ==================== //
// index에 해당하는 노드의 주소를 반환하는 함수
// 노드를 찾았다면 해당 노드, 노드를 찾을 수 없다면 NULL 반환
ListNode *findNode(LinkedList *ll, int index)
{
    if (ll == NULL || ll->head == NULL || index < 0 || index >= ll->size) return NULL;

    ListNode *cur = ll->head;
    int i = 0;
    while (i < index) {
        cur = cur->next;
        i++;
    }
    return cur;
}

// index 위치에 새로운 노드를 삽입하는 함수
// 성공 시 0, 실패 시 -1 반환
int insertNode(LinkedList *ll, int index, int value)
{
    if (index < 0 || index > ll->size) return -1;

    ListNode *pre;
    ListNode *new_node = malloc(sizeof(ListNode));
    new_node->item = value;
    new_node->next = NULL;
    if (index == 0) {
        new_node->next = ll->head;
        ll->head = new_node;
    } else {
        pre = findNode(ll, index -1);
        new_node->next = pre->next;
        pre->next = new_node;
    }

    ll->size++;
    return 0;
}

// index 위치의 노드를 삭제하는 함수
// 성공 시 0, 실패 시 -1 반환
int removeNode(LinkedList *ll, int index)
{
    if (ll == NULL || ll->head == NULL || index < 0 || index >= ll->size) return -1;

    ListNode *pre, *cur;
    if (index == 0) {
        cur = ll->head;
        ll->head = cur->next;
        free(cur);
    } else {
        pre = findNode(ll, index-1);
        cur = pre->next;
        
        pre->next = cur->next;
        free(cur);
    }

    ll->size--;
    return 0;
}

// 연결 리스트의 모든 노드 값을 순서대로 출력하는 함수
void printList(LinkedList *ll)
{
    ListNode *cur;
    printf("현재 연결 리스트: ");
    if (ll == NULL || ll->head == NULL) {
        printf("Empty\n");
    } else {
        cur = ll->head;
        while (cur != NULL) {
            printf("%d ", cur->item);
            cur = cur->next;
        }
        printf("\n");
    }
}

// 연결 리스트의 모든 노드를 제거하고 초기화하는 함수
void removeAllItems(LinkedList *ll)
{
    if (ll == NULL || ll->head == NULL) {
        return;
    }

    ListNode *cur;
    while (ll->head != NULL) {
        cur = ll->head;
        ll->head = cur->next;
        free(cur);
        ll->size--;
    }
    printf("리스트 초기화 완료\n");
}

 

 

큐 구현하기

각 함수에 주어진 매개변수(parameter)를 바탕으로, 먼저 해당 함수가 어떤 기능을 수행해야 하는지 논리적으로 생각해보고, 실제로 구현해봅니다.

 

각 함수는 어떤 기본 동작 흐름을 따르는지, 어떤 포인터 변수를 새로 만들어야 할지, 그리고 예외 상황(큐가 비어 있는 경우)에는 어떻게 대응해야 할지도 함께 고민해보면 더 좋습니다. 그리고 연결 리스트 기반 큐이므로, 기존 연결 리스트 기본 함수들을 사용해서 큐의 기본 함수들을 구현해도 상관 없습니다.

 

enqueue 함수

큐의 뒤에 요소를 추가하는 함수

• *q: (pointer) 큐 주소
• item: (int) 추가할 요소의 값

enqueue 구현하기

// 큐의 뒤에 요소를 추가하는 함수
void enqueue(Queue *q, int item) {
    // 연결 리스트의 size 위치(=맨 뒤)에 노드를 삽입
    insertNode(&(q->ll), q->ll.size, item);
}

 

isEmptyQueue 함수

큐가 비어있는지 확인하는 함수

• *q: (pointer) 큐 주소

isEmptyQueue 구현하기

// 큐가 비어있는지 확인하는 함수
// 큐가 비어있으면 1, 아니면 0을 반환
int isEmptyQueue(Queue *q) {
    if (q->ll.size == 0) {
        return 1;
    }
    return 0;
}

 

dequeue 함수

큐의 앞에서 요소를 꺼내고 제거하는 함수

• *q: (pointer) 큐 주소

dequeue 구현하기

// 큐의 앞에서 요소를 꺼내고 제거하는 함수
// 큐가 비어있다면 -1, 아니면 꺼낸 값을 반환
int dequeue(Queue *q) {
    if (isEmptyQueue(q)) return -1;           // 비어 있으면 -1 반환

    int val = q->ll.head->item;               // 맨 앞 노드의 값 꺼내기
    removeNode(&(q->ll), 0);                  // index 0 위치 제거
    return val;                               // 꺼낸 값 반환
}

 

removeAllItemsFromQueue 함수

큐의 모든 요소를 제거하는 함수

• *q: (pointer) 큐 주소

removeAllItemsFromQueue 구현하기

// 큐의 모든 요소를 제거하는 함수
void removeAllItemsFromQueue(Queue *q) {
    // 이미 비어 있다면 return
    if (isEmptyQueue(q)) return;
    // 큐가 빌 때까지 dequeue 반복
    while (!isEmptyQueue(q)) dequeue(q);
}