[C언어 소스] 연결리스트를 이용하여 구현한 큐

안녕하세요. 언제나 휴일이예요.

이번에는 연결리스트를 이용하여 구현한 큐의 소스 코드예요.

큐는 자료를 한쪽으로 보관하고 다른쪽에서 꺼내는 FIFO(First In First Out) 방식의 자료구조입니다. 큐에 자료를 보관하는 연산을 PUT 혹은 ENQUEUE라 말하고 꺼내는 연산을 GET 혹은 DEQUEUE라고 말합니다. 그리고 보관할 위치 정보를 rear, 꺼낼 위치 정보를 front라고 말해요.

연결리스트를 이용하여 구현한 큐에서는 보관할 때 rear 뒤에 보관하고 꺼낼 때 front에 있는 것을 꺼냅니다. 그리고 보관할 때 허용하는 메모리 범위 내에서 보관할 수 있어 꽉 찼는지 확인할 필요가 없습니다.

알고리즘

PUT 연산
now = MakeNode(data) (노드 생성)

IF Queue Is Empty (비어있을 때)
    front = now (front를 now로 설정)
Else (비어있지 않을 때)

    rear의 next= now (rear의 netx를 now로 설정)
rear=now (rear를 now로 설정)

GET 연산
IF Queue is empty Then (비었으면)
    Underflow (버퍼 언더플로우)
Else
now = front

    data = front의 data (data를 front의 data로 설정)

    fornt =now의 next (front를 now의 next로 설정)

DisposeNode(now) (now 노드 소멸)

data 반환

원형 큐 실행 화면

소스 코드

C

//큐 - 연결리스트 이용 #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Node //노드 정의 { int data; struct Node *next; }Node; typedef struct Queue //Queue 구조체 정의 { Node *front; //맨 앞(꺼낼 위치) Node *rear; //맨 뒤(보관할 위치) int count;//보관 개수 }Queue; void InitQueue(Queue *queue);//큐 초기화 int IsEmpty(Queue *queue); //큐가 비었는지 확인 void Enqueue(Queue *queue, int data); //큐에 보관 int Dequeue(Queue *queue); //큐에서 꺼냄 int main(void) { int i; Queue queue; InitQueue(&queue);//큐 초기화 for (i = 1; i <= 5; i++)//1~5까지 큐에 보관 { Enqueue(&queue, i); } while (!IsEmpty(&queue))//큐가 비어있지 않다면 반복 { printf("%d ", Dequeue(&queue));//큐에서 꺼내온 값 출력 } printf("\n"); return 0; } void InitQueue(Queue *queue) { queue->front = queue->rear = NULL; //front와 rear를 NULL로 설정 queue->count = 0;//보관 개수를 0으로 설정 } int IsEmpty(Queue *queue) { return queue->count == 0; //보관 개수가 0이면 빈 상태 } void Enqueue(Queue *queue, int data) { Node *now = (Node *)malloc(sizeof(Node)); //노드 생성 now->data = data;//데이터 설정 now->next = NULL; if (IsEmpty(queue))//큐가 비어있을 때 { queue->front = now;//맨 앞을 now로 설정 } else//비어있지 않을 때 { queue->rear->next = now;//맨 뒤의 다음을 now로 설정 } queue->rear = now;//맨 뒤를 now로 설정 queue->count++;//보관 개수를 1 증가 } int Dequeue(Queue *queue) { int re = 0; Node *now; if (IsEmpty(queue))//큐가 비었을 때 { return re; } now = queue->front;//맨 앞의 노드를 now에 기억 re = now->data;//반환할 값은 now의 data로 설정 queue->front = now->next;//맨 앞은 now의 다음 노드로 설정 free(now);//now 소멸 queue->count--;//보관 개수를 1 감소 return re; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

//큐 - 연결리스트 이용
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node //노드 정의
{
    int data;
    struct Node *next;
}Node;

typedef struct Queue //Queue 구조체 정의
{
    Node *front; //맨 앞(꺼낼 위치)
    Node *rear; //맨 뒤(보관할 위치)
    int count;//보관 개수
}Queue;

void InitQueue(Queue *queue);//큐 초기화
int IsEmpty(Queue *queue); //큐가 비었는지 확인
void Enqueue(Queue *queue, int data); //큐에 보관
int Dequeue(Queue *queue); //큐에서 꺼냄

int main(void)
{
    int i;
    Queue queue;

    InitQueue(&queue);//큐 초기화
    for (i = 1; i <= 5; i++)//1~5까지 큐에 보관
    {
        Enqueue(&queue, i);
    }
    while (!IsEmpty(&queue))//큐가 비어있지 않다면 반복
    {
        printf("%d ", Dequeue(&queue));//큐에서 꺼내온 값 출력
    }
    printf("\n");
    return 0;
}

void InitQueue(Queue *queue)
{
    queue->front = queue->rear = NULL; //front와 rear를 NULL로 설정
    queue->count = 0;//보관 개수를 0으로 설정
}

int IsEmpty(Queue *queue)
{
    return queue->count == 0;    //보관 개수가 0이면 빈 상태
}

void Enqueue(Queue *queue, int data)
{
    Node *now = (Node *)malloc(sizeof(Node)); //노드 생성
    now->data = data;//데이터 설정
    now->next = NULL;

    if (IsEmpty(queue))//큐가 비어있을 때
    {
        queue->front = now;//맨 앞을 now로 설정
    }
    else//비어있지 않을 때
    {
        queue->rear->next = now;//맨 뒤의 다음을 now로 설정
    }
    queue->rear = now;//맨 뒤를 now로 설정
    queue->count++;//보관 개수를 1 증가
}

int Dequeue(Queue *queue)
{
    int re = 0;
    Node *now;
    if (IsEmpty(queue))//큐가 비었을 때
    {
        return re;
    }
    now = queue->front;//맨 앞의 노드를 now에 기억
    re = now->data;//반환할 값은 now의 data로 설정
    queue->front = now->next;//맨 앞은 now의 다음 노드로 설정
    free(now);//now 소멸
    queue->count--;//보관 개수를 1 감소
    return re;
}