Kim's Programming
이번에는 큐를 동적으로 만들어 보겠습니다.
큐(Queue) - 동적 - 구조
큐를 동적으로 만들 때는 다음과 같은 구조체를 이용하게 됩니다.
#include<stdio.h> #include<malloc.h> struct QueueNode { QueueNode *Link; int VALUE; }; struct Queue { QueueNode *header;//제일 앞 포인터 QueueNode *tailer;//제일 뒤 포인터 QueueNode *Temp_Tail;//제일 뒤 바로 앞 포인터 }; | cs |
이번엔 포인터를 3개를 사용했습니다. 큐를 만들때 이번엔 단순연결 리스트를 이용하여 만들었습니다. 단순 연결리스트는 다시 뒤로 돌아가기 힘들기 때문에 포인터를 하나더 썼습니다.
큐(Queue) - 동적 - ADT
- void init()
초기화 함수입니다. 포인터들을 초기화 해 줍니다.void init(Queue *Target_Queue)
{
Target_Queue->header = NULL;
Target_Queue->tailer = NULL;
Target_Queue->Temp_Tail = NULL;
}
cs - bool is_empty()
bool is_empty(Queue *Target_Queue)
{
if (Target_Queue->header == NULL)
{
printf("비었습니다.\n");
return true;
}
else
{
printf("아직 값이 있습니다.\n");
return false;
}
}
cs 포인터 상태를 확인하여 비었는지 찼는지 확인을 합니다. 동적 할당을 하여 만드는 큐는 메모리 사이즈가 되는 만큼 만들 수 있기 때문에 가득 찬 경우는 제외했습니다. 가득찬경우 true 그렇지 않은 경우 false를 반환합니다
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
void enqueue(Queue *Target_Queue, int Item)
{
QueueNode *New = (QueueNode *)malloc(sizeof(QueueNode));
if (is_empty(Target_Queue))//첫 번째 노드 추가
{
Target_Queue->header = New;
Target_Queue->tailer = New;
New->VALUE = Item;
New->Link = NULL;
return;
}
else
if (Target_Queue->Temp_Tail == NULL)// 두 번째 노드 추가
{
New->Link = Target_Queue->header;
New->VALUE = Item;
Target_Queue->Temp_Tail = New;
Target_Queue->header = New;
}
else// 이후 노드 추가
{
New->Link = Target_Queue->header;
New->VALUE = Item;
Target_Queue->header = New;
}
}
cs 큐에 데이터를 추가하는 함수입니다. 포인터 3개를 할당해야하기 때문에 3부분으로 나눠서 단계별로 포인터들을 할당하게 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dequeue(Queue *Target_Queue)
{
int Value = 0;
QueueNode *Temp= NULL;
QueueNode *Delete = NULL;
QueueNode *Cur = Target_Queue->header;
while (Cur!=Target_Queue->Temp_Tail)
{
Temp = Cur;//temp Tail 이전의 노드를 가리키는 포인터 저장
Cur = Cur->Link;
}
Delete = Target_Queue->tailer;
Value = Delete->VALUE;
Target_Queue->Temp_Tail = Temp;
Target_Queue->tailer = Temp->Link;
Target_Queue->tailer->Link = NULL;
free(Delete);
return Value;
}
cs 큐에서 Temp_Tail 포인터가 가르키는 노드 이전의 노드를 카리키는 노드를 이용하여 가장 마지막 노드를 삭제하기 전 tailer 노드와 Temp_Tail 노드를 할당할 위치를 저장하게 됩니다. 위에서 Temp 포인터는 기존의 Temp_Tail이 가리키던 노드의 바로 이전 노드를 가리키는 포인터 이며 Delete 노드는 동적해제할 노드를 저장하는 포인터입니다.
void printing(Queue *Target_Queue)
{
QueueNode *Cur = Target_Queue->header;
while (Cur!=NULL)
{
printf("%d ", Cur->VALUE);
Cur = Cur->Link;
}
printf("\n");
}
cs 출력하는 함수입니다. 제일 끝으로 갈때까지 출력하게 됩니다.
사실 큐는 이중연결로 짜도 상관은 없지만 뒤에서 포스팅할 덱(deque)에서 이중연결으로 구현하며 또 덱으로도 큐를 표현할 수 있기 때문에 단순연결로 한번 짜봤습니다. 다음 포스팅에서는 덱(deque)을 포스팅 하겠습니다.