C - 큐(Queue)의 기본 구현

1. 큐란?

큐, 위키백과 출처

큐란 FIFO(First In First Out) 즉, 선입 선출 구조를 가진 자료구조다.

프린터의 대기열이나 번호표 등이 큐의 예시라고 이해하면 된다.]

 

2. 큐의 구현

 

큐 역시 배열과 링크드리스트 두가지의 방법으로 구현이 가능하다.

Enqueue와 Dequeue를 구현하는것을 목표로 진행하겠다.

 

2-1. 배열을 이용한 스택의 구현

// queue_array.c

#define MAX_LEN 5
#include<stdio.h>

void enqueue(int data);
void dequeue();
void show();

int queue[MAX_LEN];
int count = 0;

int main(void){
        int i;

        for(i=0; i<MAX_LEN; i++)
                enqueue(i);
        show();

        for(i=0; i<MAX_LEN; i++)
                dequeue();
        show();
        return 0;
}

void enqueue(int data){
        queue[count++] = data;
        printf("Enqueue %d \n", data);
}

void dequeue(){
        printf("Dequeue %d \n", queue[0]);
        for(int i=0; i<count-1; i++)
                queue[i] = queue[i+1];
        count--;
}

void show(){
        if(count == 0)
                printf("NO QUEUE!\n");
        for(int i=0; i<count; i++)
                printf("%d -> ", queue[i]);
        printf("\n");
}

 

5개의 데이터를 저장할 수 있는 큐를 배열로 만들었다.

 

스택과의 차이점이라고 하면 역시 입출력 순서일 것이다.

 

또한 큐를 당겨야하는 작업도 dequeue에서만 필요할 뿐 enqueue에서는 필요가 없다.

 

배열 큐의 도식화

 

들어간 순서대로 나오기 때문에 0번째 인덱스부터 차곡차곡 데이터를 쌓아나간다.

이후 0번째 요소를 dequeue 하고, 나머지 요소들을 한칸씩 당겨주면 완성이다.

 

실행시 위와 같이 출력된다.

 

2-2. 링크드 리스트를 이용한 큐의 구현

// queue_linkedList.c

#define INPUT_LEN 5
#include<stdio.h>
#include<stdlib.h>

void enqueue(int num);
void dequeue();
void show();

typedef struct Node{
        int data;
        struct Node *next;
}node;

node* queue = NULL;

int main(void){
        int i;

        for(i=0; i<INPUT_LEN; i++)
                enqueue(i);
        show();
        for(i=0; i<INPUT_LEN; i++)
                dequeue();
        show();

        return 0;
}

void enqueue(int num){
        node* new_node = (node*)malloc(sizeof(node));
        new_node->data = num;
        new_node-> next = NULL;

        if(queue == NULL)
                queue = new_node;
        else{
                node* temp = queue;
                while(temp->next != NULL)
                        temp = temp->next;
                temp->next = new_node;

                printf("Enqueue %d\n", num);
        }


}

void dequeue(){
        printf("Dequeue %d\n", queue->data);
        node* temp = queue;
        queue = queue->next;
        free(temp);
}

void show(){
        node* temp = queue;
        if(temp == NULL) {
                printf("NO QUEUE!\n");
                return;
        }
        while(temp != NULL){
                printf("%d-> ", temp->data);
                temp = temp->next;
        }
        printf("\n");
}

 

링크드 리스트를 활용한 코드는 위와 같다.

코드의 길이가 길어졌지만 노드 구조체에 대한 부분이 추가되었을 뿐 큰 동작의 차이는 없다.

 

동작에 대한 도식화를 진행하면 다음과 같다.

4가 큐에 추가됬을 때의 동작

링크드 리스트의 Front 부분인 node* queue에서 진입하여 3을 저장한 노드까지 이동한 다음 3의 next를 새로운 노드, 즉 4를 저장한 노드로 설정하면 enqueue 동작이 끝난다.

 

여기서 동작을 빠르게 하기 위하여 tail이라 표시된 부분, back의 주소를 따로 저장하여 back을 이용하여 enqueue 동작을 수행하는 방법도 있다.

 

• 위 코드에서는 enqueue 동작시 front부터 tail까지 하나하나 거쳐가며 새로운 노드가 들어갈 자리를 찾는다.           ( 0, 1, 2, 3 순서로 거쳐간다.)
• back이라는 새로운 변수를 통하여 바로 접근하여 enqueue 할 경우 성능의 향상을 도모할 수 있다.                       ( back 즉, 3에 바로 접근하여 4를 추가한다음 4를 back으로 설정한다면 성능 개선이 가능하다. )

 

dequeue의 경우에는 front에서 진행하므로 front를 dequeue하고 다음 노드인 1을 front로 설정해주면 된다.

이 코드의 출력은 다음과 같다.

 

 

3. 마무리

큐의 기본적인 구현 방법에 대하여 알아보았다.

다만 큐는 다양한 종류를 가지고 있다. 어떻게 연결되었는지, 방향이 어디인지 등에 따라 나눠진다.

다음에는 그에 대한 것을 다뤄보겠다.