[자료구조] 연결리스트로 구현한 큐(queue)

1. 연결된 큐(Linked queue)

연결리스트로 구현한 스택과 마찬가지로

큐 자료구조를 배열이 아닌 연결리스트로 구현한 것이다.

기본적인 큐 구조는 Last In First Out : LIFO 로 동일하며

큐의 rear단에서 삭제가 일어나고, front단에서 삽입이 일어난다.

 

2. 삽입 연산(enqueue)

삽입할 경우 큐의 rear의 링크가 새로운 노드를 가리키게 한다.

큐가 공백 상태일 경우에는 새로 만든 노드가 큐의 front, rear 모두 가리키게 한다.

//큐가 공백 상태인지 확인하는 함수
int is_empty(LinkedQueueType *q){
    return q->front == NULL;
}

//삽입 함수
void enqueue(LinkedQueueType *q){
    int data;
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    
    printf("enqueue data : ");
    scanf("%d", &data);
    
    new_node->data = data;
    new_node->link = NULL;
    
    //큐가 공백이라면 새로 만든 노드가 큐의 front, rear 둘 다 가리키게 한다.
    if(is_empty(q)){
        q->rear = new_node;
        q->front = new_node;
    //큐가 공백이 아니라면 새로 만든 노드가 큐의 rear에 연결한다.
    }else{
        q->rear->link = new_node;
        q->rear = new_node;
    }
}

 

3. 삭제 함수(dequeue)

삭제할 경우 큐의 front 포인터의 데이터를 반환하고

front의 다음 링크가 되게 하면 된다.

//큐가 공백 상태인지 확인하는 함수
int is_empty(LinkedQueueType *q){
    return q->front == NULL;
}

//삭제 함수
void dequeue(LinkedQueueType *q){
    QueueNode *temp = q->front;
    
    if(is_empty(q)){
        printf("no data\n");
    }else{
        printf("dequeue data : %d\n", temp->data);
        q->front = q->front->link;
        free(temp);
    }
}

 

<<전체 코드>>

//이중 연결 리스트
#include <stdio.h>
#include <stdlib.h>

typedef struct queueNode{
    int data;
    struct queueNode* link;
}QueueNode;

typedef struct{
    QueueNode *front,*rear;
}LinkedQueueType;

//큐가 공백 상태인지 확인하는 함수
int is_empty(LinkedQueueType *q){
    return q->front == NULL;
}

//삽입 함수
void enqueue(LinkedQueueType *q){
    int data;
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    
    printf("enqueue data : ");
    scanf("%d", &data);
    
    new_node->data = data;
    new_node->link = NULL;
    
    //큐가 공백이라면 새로 만든 노드가 큐의 front, rear 둘 다 가리키게 한다.
    if(is_empty(q)){
        q->rear = new_node;
        q->front = new_node;
    //큐가 공백이 아니라면 새로 만든 노드가 큐의 rear에 연결한다.
    }else{
        q->rear->link = new_node;
        q->rear = new_node;
    }
}

//삭제 함수
void dequeue(LinkedQueueType *q){
    QueueNode *temp = q->front;
    
    if(is_empty(q)){
        printf("no data\n");
    }else{
        printf("dequeue data : %d\n", temp->data);
        q->front = q->front->link;
        free(temp);
    }
}

void print_queue(LinkedQueueType *q){
    QueueNode *temp;
    
    for(temp = q->front; temp != NULL; temp = temp->link){
        printf("%d ", temp->data);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    int menu;
    
    LinkedQueueType q;
    q.rear = NULL;
    q.front = NULL;

    do{
        printf("========================\n");
        printf("1.enqueue 2.dequeue 3.print 4.end\n");
        printf("========================\n");
        printf("menu : ");
        scanf("%d", &menu);
        
        if(menu == 1){
            enqueue(&q);
        }else if(menu == 2){
            dequeue(&q);
        }else if(menu == 3){
            print_queue(&q);
        }
    }while(menu != 4);
}