728x90
연결 리스트 기반의 큐 구현
- 구조체 정의
typedef struct _node
{
Data data;
struct _node * next;
} Node;
typedef struct _lQueue
{
Node * front; // 삭제를 위한 노드 포인터
Node * rear; // 삽입을 위한 노드 포인터
} LQueue;
- 초기화
void QueueInit(Queue * pq)
{
pq->front = NULL;
pq->rear = NULL;
}
- 비어있는지 확인
-> rear는 볼 필요 없이 front만으로 비어있는지 판단
-> 노드가 삽입 후 모두 삭제하면 front는 null로 설정되게 정의하기 때문에 front만 비교
int QIsEmpty(Queue * pq)
{
if(pq->front == NULL)
return TRUE;
else
return FALSE;
}
- 삽입
-> 첫 삽입때는 front와 rear 모두 new node를 가르키고 그 이후에는 rear는 새 new node를 가르킴
-> 첫 삽입 때 바로 rear는 new node를 가르키고 QIsEmpty에도 front만 비교하기 때문에 굳이 rear를 NULL로 초기화 할 필요는 없음
void Enqueue(Queue * pq, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->next = NULL;
newNode->data = data;
if(QIsEmpty(pq))
{
pq->front = newNode;
pq->rear = newNode;
} // 비어있었으면(첫 삽입) front와 rear 모두 새 노드를 가르킴
else
{
pq->rear->next = newNode;
pq->rear = newNode;
} // 마지막으로 rear 였던 노드의 next에 새 노드를 설정
}
- 데이터 조회(삭제 O)
-> 모두 삭제를 하면 front는 NULL을 가르키지만 rear는 쓰레기 값을 가지게 됨
-> 그렇기 때문에 QIsEmpty에서 front만 비교하는 것이 맞음
Data Dequeue(Queue * pq)
{
Node * delNode;
Data retData;
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
} // 비어있으면 종료
delNode = pq->front; // 현재 front의 노드를 따로 저장
retData = delNode->data;
pq->front = pq->front->next; // front를 현재 front의 next로 설정
free(delNode); // 삭제(소멸)
return retData;
}
- 데이터 조회(삭제 X)
Data QPeek(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->front->data; // 현재 front의 데이터를 반환
}
728x90
'Programming > Data Structure' 카테고리의 다른 글
열혈 자료구조 - 8-1 트리의 개요 (0) | 2021.01.01 |
---|---|
열혈 자료구조 - 7-4 덱(Deque)의 이해와 구현 (0) | 2020.12.30 |
열혈 자료구조 - 7-2 큐의 배열 기반 구현(2) (0) | 2020.12.22 |
열혈 자료구조 - 7-2 큐의 배열 기반 구현(1) (0) | 2020.12.22 |
열혈 자료구조 - 7-1 큐의 이해와 ADT 정의 (0) | 2020.12.21 |