배열로 작성한 원형 큐는 한 번에 용량을 받아서 생성합니다.
아무리 큐의 Rear와 Front가 연결되어 있다고 해도 큐가 다 차는 경우에는 크기를 변경할 수 없다는 단점을 가지고 있습니다.
큐의 용량의 제한 없이 동적으로 생성할 수 있는 연결 리스트로 구현하는 큐가 필요합니다.
연결 리스트 큐 구조체
데이터를 저장하고 관리하기 위한 노드 구조체를 만듭니다.
|
1
2
3
4
5
6
7
8
9
|
// 큐 데이터 타입 정의
typedef int ElementType;
// 연결 리스트 큐 노드 구조체
typedef struct Node
{
ElementType Data;
struct Node* NextNode;
} Node;
|
연결 리스트를 사용한 큐는 다음 노드를 가리킬 포인터가 필요합니다.
작성한 노드 구조체를 담은 연결 리스트 큐를 작성합니다.
|
1
2
3
4
5
6
7
|
// 연결 리스트 큐 구조체
typedef struct LinkedListQueue
{
Node* Front; // 큐의 전단 노드
Node* Rear; // 큐의 후단 노드
int Count; // 큐의 노드 개수
} LinkedListQueue;
|
큐의 용량과 데이터를 빼줄 맨 앞의 위치인 전단과, 데이터를 넣어줄 맨 뒤의 위치인 후단을 가지고 있습니다.
연결 리스트 큐의 노드 개수를 가지고 있는 변수도 만듭니다.(큐가 비어 있는 경우 파악 등)
연결 리스트 큐 연산
연결 리스트 큐를 만들고, 사용하기 위해 구현하는 간단한 연산들입니다.
- 연결 리스트 큐 - 생성, 소멸
- 연결 리스트 큐 - 노드 추가
- 연결 리스트 큐 - 노드 소멸
- 연결 리스트 큐 - 데이터 삽입
- 연결 리스트 큐 - 데이터 제거
- 연결 리스트 큐 - 비어 있는지 확인
1. 연결 리스트 큐 - 생성
연결 리스트 큐을 생성하고 초기화를 하는 연산입니다.
배열로 구현했던 원형 큐와 다르게 용량이 필요없습니다.
|
1
2
3
4
5
6
7
8
9
10
11
|
// LLQ 생성
void LLQ_CreateQueue(LinkedListQueue** Queue)
{
// 큐를 자유저장소에 할당
(*Queue) = (LinkedListQueue*)malloc(sizeof(LinkedListQueue));
// 큐 Front, Rear, Count 초기화
(*Queue)->Front = NULL;
(*Queue)->Rear = NULL;
(*Queue)->Count = 0;
}
|
생성된 큐가 비여있으므로 Front와 Rear를 0으로 초기화합니다.
2. 연결 리스트 큐 - 소멸
자유저장소에 동적으로 할당했던 연결 리스트 큐와 노드를 소멸시키는 연산입니다.
free() 함수를 사용해서 할당된 메모리를 해제합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// LLQ 소멸
void LLQ_DestroyQueue(LinkedListQueue* Queue)
{
// 큐의 노드를 자유 저장소에서 해제
while (!LLQ_IsEmpty(Queue))
{
Node* Popped = LLQ_Dequeue(Queue);
LLQ_DestroyNode(Popped);
}
// 큐를 자유 저장소에서 해제
free(Queue);
}
|
메모리가 누수되지 않도록, 먼저 할당된 노드를 자유저장소에서 해제한 다음에 큐를 해제합니다.
3. 원결 리스트 큐 - 노드 생성
연결 리스트 큐의 노드를 생성하는 함수입니다.
노드를 자유 저장소에 할당하고 초기화한 후에 주소값을 반환합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// LQ 노드 생성
Node* LLQ_CreateNode(char* NewData)
{
// 노드를 자유 저장소에 할당
Node* NewNode = (Node*)malloc(sizeof(Node));
// 노드 초기화
NewNode->Data = NewData;
NewNode->NextNode = NULL;
// 생성한 노드의 주소값 반환
return NewNode;
}
|
4. 원결 리스트 큐 - 노드 소멸
연결 리스트 큐의 노드를 소멸하는 함수입니다.
생성된 연결 리스트 큐의 노드를 자유 저장소에서 해제합니다.
|
1
2
3
4
5
|
// LLQ 노드 소멸
void LLQ_DestroyNode(Node* _Node)
{
free(_Node);
}
|
5. 연결 리스트 큐 - 데이터 삽입(Enqueue)
연결 리스트 큐에 데이터를 넣는 Enqueue 연산입니다.
구현했던 링크드 리스트에서 Tail 뒤에 노드를 추가하는 연산과 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
// LLQ 데이터 삽입
void LLQ_Enqueue(LinkedListQueue* Queue, Node* NewNode)
{
// 노드가 없을 경우(큐가 빈 경우)
if (Queue->Front == NULL)
{
Queue->Front = NewNode;
Queue->Rear = NewNode;
Queue->Count++;
}
// Rear 노드의 다음 노드로 삽입
else
{
Queue->Rear->NextNode = NewNode;
Queue->Rear = NewNode;
Queue->Count++;
}
}
|
큐가 비어 있는 경우는 새 노드를 넣어주고, 해당 노드는 데이터를 제거할 위치이기 때문에 Front으로 지정합니다.
6. 연결 리스트 큐 - 데이터 제거(Dequeue)
큐에서 데이터를 제거하는 연산입니다.
Front의 위치의 노드를 삭제합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// LQ 데이터 제거
Node* LLQ_Dequeue(LinkedListQueue* Queue)
{
Node* Front = Queue->Front;
// 노드가 한 개인 경우
if (Queue->Front->NextNode == NULL)
{
Queue->Front = NULL;
Queue->Rear = NULL;
}
// 큐의 Front를 다음 노드로 변경
else
{
Queue->Front = Queue->Front->NextNode;
}
// 큐의 노드 개수 감소
Queue->Count--;
return Front;
}
|
7. 연결 리스트 큐 - 비어있는지 확인
연결 리스트 큐가 비여있는지 확인하는 연산입니다.
|
1
2
3
4
5
|
// LLQ가 비어있는지 확인
int LLQ_IsEmpty(LinkedListQueue* Queue)
{
return (Queue->Front == NULL);
}
|
댓글