큐 구현하기

만약에, 면접장에서 큐를 구현해보라는 말을 들으면 어떻게 해야할까? 이런 기본적인 자료구조를 바로 짜보라는 질문에 대비하여, 지금 다시 한번 복습해보자.

1. 배열로 구현하기

기본 자료구조를 먼저 정의해보자.

• 배열을 이용하여 queue의 사이즈를 정하여 선언한다.
• head, tail 그리고 queue의 현재사이즈를 담는 선언한다.

#define QUEUE_CAPACITY 8
int queue[QUEUE_CAPACITY]; 
int head = 0;
int tail = -1;
int queue_size = 0;

이제 큐에 원소를 삽입, 삭제하는 함수를 짜보자.

void enqueue(int n){
    if ( queue_size == QUEUE_CAPACITY ){
        printf("queue is full! \n");
        return;
    }

    tail = (tail + 1) % QUEUE_CAPACITY;
    queue_size++;
    queue[tail] = n;
}

int dequeue(){
    int r;

    if ( queue_size == 0 ){
        printf("queue is empty! \n");
        return;
    }

    r = queue[head];
    head = (head + 1) % QUEUE_CAPACITY;
    queue_size--;
    return r;
}

코드가 직관적으로 이해 될 것이다. 다음 사항만 주의하면 될 것이다.

• queue 가 비어있거나 꽉 차있을 때의 예외처리
• 삽입, 삭제에 따른 head, tail 이동과 queue_size 처리.
• 삽입, 삭제시 원소를 일일이 이동하는 것이 번거롭기 때문에 원형 큐를 사용한다는 점.

메인에서는 다음과 같이 쓸 수 있다.

int main(){
    int t;

    enqueue(3); // 큐에 3 삽입
    enqueue(4); // 큐에 4 삽입
    t = dequeue() // 큐에서 원소 빼기. 3이 리턴된다.
    printf("%d \n"); // 3 출력

    return 0;
}

2. 연결리스트로 구현하기

마찬가지로 먼저 기본 자료구조부터 짜보자.

struct _node{
    int key;
    struct _node *next;
}node_t;
typedef struct _node node_t;

node_t *head = NULL;
node_t *tail = NULL;

• 연결리스트 구조체를 기본적으로 구현한다.
• head 와 tail이 항상 같이 따라온다는 것을 잊지말자.

삽입과 삭제에 관련된 함수를 짜보자.

void insert_node(int n){
    node_t *new_node = (note_t *)malloc(sizeof(node_t));

    new_node->key = n;
    new_node->next = NULL;

    tail->next = new_node;
    tail = new_node;
}

int delete_node(){
    node_t *node;
    int r;

       if ( head == NULL ){
        printf("queue is empty! \n");
        return;
    }

    node = head;
    head = head->next;

    r = node->key;
    free(node);
    return r;
}

이까지만 하면, 기본적인 삽입, 삭제 구현은 된것같지만, 각 케이스에 대해 생각해야봐야 한다.

• 삽입 시, 큐가 비어있다면? head와 tail을 어떻게 처리할 것인가?
• 삽입 시, tail->next 로 새 노드를 연결하는데, 만약 tail 이 NULL 이면, tail->next 는 처리가 될까?

첫 번째는 큐가 비어있다면, 삽입 시 head = tail = (새로운 노드) 로 맞춰주어야 하고, 이후에는 tail->next = (새로운 노드) 로 처리해주면 된다.

두 번째는, 삭제 시에 head = head->next 의 방식으로 노드를 연결리스트에서 끊어내고 있기 때문에, tail 은 전혀 영향받고 있지 않다. 따라서 임의적으로 이를 잡아주어야 한다.

수정된 코드는 다음과 같다.

void insert_node(int n){
    node_t *new_node = (note_t *)malloc(sizeof(node_t));

    new_node->key = n;
    new_node->next = NULL;

    /// 추가된 부분 ///
    if ( head == NULL )
        head = new_node;
    else
        tail->next = new_node;
    //////////////////

    tail = new_node;
}

int delete_node(){
    node_t *node;
    int r;

       if ( head == NULL ){
        printf("queue is empty! \n");
        return;
    }

    node = head;
    head = head->next;

    /// 추가된 부분 ///
    if ( head == NULL )
        tail = NULL;
    //////////////////

    r = node->key;
    free(node);
    return r;
}

자칫하면 이런 예외를 생각하지 못하는 실수를 할 수 있으므로, 조금 까다롭다는걸 기억하자.