[Data Structure] #3-2 연결 큐 (Linked Queue)

연결 큐 (Linked Queue)

 Linked List를 이용한 Queue이다. Linked List의 Size에 한계가 없는 특징이 Queue에 접목되었다. 주요한 코드에 주석을 달아놨기 때문에 코드를 읽어도 이해하는데 무리가 없을 것이다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// windows 환경에서는
// #include <malloc.h>
#include <malloc/malloc.h> // for mac

typedef int element;

typedef struct {
    element data;
    struct QueueNode* link;
} QueueNode;

typedef struct {
    QueueNode *front;
    QueueNode *rear;
} QueueType;

void error(char *msg){
    fprintf(stderr,"%s\n",msg);
    exit(1);
}

void init(QueueType *q){
    q->front = NULL;
    q->rear = NULL;
}

int is_empty(QueueType *q){
    return q->front == NULL;
}

int is_full(QueueType *q){
    //Linked Queue 이기 때문에 항상 FALSE를 리턴
    return 0;
}

void enqueue(QueueType *q, element item){
    if (is_full(q)) // 사실상 의미 없다
        error("q is full");

    QueueNode *new_node = (QueueNode*) malloc(sizeof(QueueNode));
    new_node->data = item;
    new_node->link = NULL;
    
    if (is_empty(q)) {
        q->front = new_node;
        q->rear = new_node;
    } else {
        // 순서가 중요하다
        q->rear->link = (struct QueueNode*) new_node;
        q->rear = new_node;
    }
}

element dequeue(QueueType *q){
    if (is_empty(q))
        error("q is empty");

    QueueNode *removed = q->front;
    element item = removed->data;
    q->front = (QueueNode*) q->front->link;
    
    if (q->front == NULL) // size is 1
        q->rear = NULL;

    free(removed);
    return item;
}

element peek(QueueType *q){
    if (is_empty(q))
        error("q is empty");
    
    QueueNode *tmp = (QueueNode*) q->front;
    return tmp->data;
}

int main(){
    QueueType q;
    init(&q);
    
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    
    printf("dequeue()=%d\n",dequeue(&q));
    printf("dequeue()=%d\n",dequeue(&q));
    printf("dequeue()=%d\n",dequeue(&q));
    
    return 0;
}

질문은 언제나 환영!