[C] 큐와 연결리스트

단순 연결리스트(simply linked list)로 큐를 구현해보자.

스택과 마찬가지로 큐도 연결리스트로 구현 가능하다. 단순 연결리스트에 2개의 포인터를 추가한 것과 같은데, front로 삭제하고 rear로 삽입한다. FIFO이기 때문에 먼저 들어온 요소가 먼저 삭제된다.

 

나머지는 [C]스택과 연결리스트에 정의되어 있는 함수들과 같고, 삽입은 enqueue 삭제는 dequeue가 해준다.

마찬가지로 전역변수를 쓸 때와 쓰지 않을 때로 나누어보았다.

 

 

(1) 전역변수 사용

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define ERROR_VALUE -300000
 
typedef struct LinkedNode {
    int data;
    struct LinkedNode* link;
}Node;
 
Node* front;
Node* rear;
 
void init() { front = rear = NULL; }
int is_empty() { return (front == NULL && rear == NULL); }
int size() {
    Node* p;
    int count = 0;
    for (p = front; p != rear; p = p->link) //front에서 rear가 아닐 때가지 돈다
        count++;
    return count + 1; //위에보면 조건식이 p!=rear일 때까지이니까 rear일 때도 고려해줘야 함!
}
void enqueue(int value) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = value;
    n->link = NULL;
    if (is_empty()) front = rear = n;
    else {
        rear->link = n;
        rear = n;
    }
}
int dequeue() {
    Node* removed = front;
    int value;
    /*
    두 가지의 경우의 수가 있다.
    1. 스택 안의 노드 개수가 하나인 경우, 즉 이때 삭제 연산을 하면 front와 rear 둘 다 NULL을 가리켜야 한다.
    2. 스택 안의 노드 개수가 2개 이상인 경우
    */
    if (is_empty()) {
        printf("Queue Empty Error!\n");
        return ERROR_VALUE;
    }
    else if (size() == 1) {
        front = rear = NULL;
    }
    else {
        front = removed->link;
        value = removed->data;
        free(removed);
        return value;
    }
}
int peek() {
    int value;
    if (is_empty()) {
        printf("Queue Empty Error!\n");
        return ERROR_VALUE;
    }
    else {
        value = front->data;
        return value;
    }
}
 
void print_all() {
    Node* p;
    printf("QUEUE STATUS: size=%d\n", size());
    for (p = front; p != NULL; p = p->link)
        printf("[%2d]->", p->data);
    printf("NULL\n");
    /* 
    아니면 for문부터 이렇게 해도 됨
    for (p=front; p!=rear; p=p->link)
    printf("[%2d]", p->data);
    printf("[%2d]\n", p->data);
    이러면 마지막꺼 출력해야되니까 한 번 더 넣어줘야 됨!
    */
}
 
int main(void) {
    int value, sel;
 
    init();
    while (1) {
        do {
            printf("1.ENQUEUE 2.DEQUEUE 3.PEEK 4.STATUS 0.EXIT :");
            scanf("%d", &sel);
        } while (sel < 0 || sel > 4);
        if (sel == 1) {
            printf("Enter value to enqueue from rear : ");
            scanf("%d", &value);
            enqueue(value);
        }
        else if (sel == 2) {
            value = dequeue();
            if (value != ERROR_VALUE)
                printf("[%2d] has been dequeued from front\n", value);
        }
        else if (sel == 3) {
            value = peek();
            if (value != ERROR_VALUE)
                printf("[%2d] is the front value of QUEUE\n", value);
        }
        else if (sel == 4) {
            if (is_empty()) printf("Queue is Empty!\n");
            else print_all();
        }
        else break;
    }
    printf("\nE N D  O F  P R O G R A M");
    return 0;
}

 

++ 이 코드에는 함정이 있다. 오류는 아니지만 돌려보면 dequeue함수에 뭔가 이상한 점이 있다. 밑에 코드와 비교하면 쉽게 찾을 수 있다. 이 때까지만 해도 문제가 있는 걸 몰랐는데, dequeue가 모든 값을 반환하지 않는다는 걸 알았어야 했다...

 

 

(2) 전역변수 미사용

전역변수가 예전과 다르게 front, rear 2개이다. 둘 다 main으로 집어넣고 일일이 매개변수로 넘겨야 하나?라고 두려움에 떨고 있었는데, 교재가 멋진 해답을 알려줌. 바로 front와 rear 둘 다 새로운 구조체에 포함시켜버리는 것이다!

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define ERROR_VALUE -300000
 
typedef struct LinkedNode {
    int data;
    struct LinkedNode* link;
}Node;
 
typedef struct {
    Node* front, * rear;
}LinkedType;
 
void init(LinkedType* q) {
    q->front = q->rear = 0;
}
int is_empty(LinkedType* q) { 
    return (q->front == NULL && q->rear == NULL); 
}
int size(LinkedType* q) {
    Node* p;
    int count = 0;
    for (p = q->front; p != q->rear; p = p->link) 
        count++;
    return count + 1; 
}
void enqueue(LinkedType* q, int value) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = value;
    n->link = NULL;
    if (is_empty(q)) q->front = q->rear = n;
    else {
        q->rear->link = n; //장난하냐... 순서 헷갈리지 말자
        q->rear = n;
    }
}
int dequeue(LinkedType* q) {
    Node* removed = q->front;
    int value;
    if (is_empty(q)) {
        printf("Queue Empty Error!\n");
        return ERROR_VALUE;
    }
    else if (size(q) == 1) {
        value = q->rear->data;
        q->front = q->rear = NULL;
        return value;
    }
    else {
        q->front = removed->link;
        value = removed->data;
        free(removed);
        return value;
    }
}
int peek(LinkedType* q) {
    int value;
    if (is_empty(q)) {
        printf("Queue Empty Error!\n");
        return ERROR_VALUE;
    }
    else {
        value = q->front->data;
        return value;
    }
}
 
void print_all(LinkedType* q) {
    Node* p;
    printf("QUEUE STATUS: size=%d\n", size(q));
    for (p = q->front; p != NULL; p = p->link)
        printf("[%2d]->", p->data);
    printf("NULL\n");
}
 
int main(void) {
    LinkedType queue;
    int value, sel;
 
    init(&queue);
    while (1) {
        do {
            printf("1.ENQUEUE 2.DEQUEUE 3.PEEK 4.STATUS 0.EXIT :");
            scanf("%d", &sel);
        } while (sel < 0 || sel > 4);
        if (sel == 1) {
            printf("Enter value to enqueue from rear : ");
            scanf("%d", &value);
            enqueue(&queue, value);
        }
        else if (sel == 2) {
            value = dequeue(&queue);
            if (value != ERROR_VALUE)
                printf("[%2d] has been dequeued from front\n", value);
        }
        else if (sel == 3) {
            value = peek(&queue);
            if (value != ERROR_VALUE)
                printf("[%2d] is the front value of QUEUE\n", value);
        }
        else if (sel == 4) {
            if (is_empty(&queue)) printf("Queue is Empty!\n");
            else print_all(&queue);
        }
        else break;
    }
    printf("\nE N D  O F  P R O G R A M");
    return 0;
}
 

책이 init()함수를 어떻게 구성하면 될지 힌트를 좀 줬다. 대신 main에서 변수를 선언할 때 구조체 포인터를 쓰지 않는다.

내 짧은 경험으로는 이런 적이 처음이다;;; 구조체 쓰려면 항상 포인터 써줘야 하는거 아니였나?

 

 

<결과 창>

 

STATUS 전체 출력을 보면, NULL 쪽이 rear라는 것을 알 수 있음.