[자료구조] 연결리스트를 통한 큐(Queue) 구현 - C

큐(Queue)

 

위 이미지와 같이 들어온 순서대로 나가게 되는 자료구조이다.

First In First Out의 구조를 갖는다.

 

 

각 함수에 대해서 간략히 설명하고 넘어가겠다.

 

isEmpty()

큐가 비어있는지 검사하는 함수

• 비어있으면 1 반환
• 비어있지 않으면 0 반환

 

isFull()

큐가 가득 차있는지 검사하는 함수

• 연결리스트는 계속해서 확장할 수 있으므로 isFull함수를 사용하지 않는다.

 

Enqueue()

큐에 새로운 데이터를 삽입하는 함수

• 새로운 노드를 생성하여 데이터를 저장하고, 그 새로운 노드와 head 노드를 연결한다.

 

Dequeue()

큐에 있는 데이터를 삭제, 반환하는 함수

• 가장 처음 들어온 노드의 값을 찾아 반환해야한다.
• 이전 노드의 위치도 기억해야 하므로 prev 포인터 노드와 temp 포인터 노드 두 개 사용

 

 

 

소스코드

#include<stdio.h>
#include<stdlib.h>

typedef struct _queue
{
    int data;
    struct _queue *link;
}Queue;

int isEmpty(Queue* head){
    return (head == NULL);
}

void Enqueue(Queue** head, int data){
    Queue *newnode = (Queue *)malloc(sizeof(Queue));
    newnode->data = data;
    newnode->link = *head;
    *head = newnode;
}

int Dequeue(Queue** head){
    if(isEmpty(*head)){
        printf("큐가 비어있습니다!\n");
        exit(1);
    }
    
    Queue *temp = *head;
    Queue *prev = NULL;

    while(temp->link != NULL){
        prev = temp;
        temp = temp->link;
    }
    
    int return_data = temp->data;
    
    if(prev == NULL){
        *head = NULL;
    } else {
        prev->link = NULL;
    }
    
    free(temp);
    return return_data;
}

int main(void){
    Queue *head = NULL;
    
    Enqueue(&head, 10);
    Enqueue(&head, 20);
    Enqueue(&head, 30);
    
    printf("Dequeued: %d\n", Dequeue(&head)); 
    printf("Dequeued: %d\n", Dequeue(&head)); 
    printf("Dequeued: %d\n", Dequeue(&head)); 
    
    return 0;
}

 

 

실행 결과