Queue - LinkedList로 구현

Queue를 리스트로 구현해보자

 

다음과 같이 그림을 그린 후 코드로 구현했다.

 

초기화

코드 구현

typedef struct __LinkedList
{
	int data;
	struct __LinkedList *next;

}LinkedList;


typedef struct __Queue
{
	LinkedList *front;
	LinkedList *rear;
	LinkedList *body;

} LQueue_Struct;


void LQueue_init(LQueue_Struct *lqueue)
{
	lqueue->body = (LinkedList*) malloc(sizeof(LinkedList));
	lqueue->body->data = '\0';
	lqueue->front = lqueue->body;
	lqueue->rear = lqueue->body;
}

 

Queue에 데이터를 넣을 때

 

1. Malloc으로 넣을 Buffer를 생성한다.

2. 데이터를 넣는다.

3. 이전 포인터(Body Pointer)에서 만들어진 LinkedList 버퍼와 연결한다.

4. Body포인터를 현재 만들어진 LinkedList 버퍼로 옮긴다.

(옮겨나야 다시 Data를 삽입할 때 Rear Pointer가 Malloc으로 할당 후 Body Pointer를 통해 

만들어진 LinkedList 버퍼와 연결 할 수 있다.)

 

코드 구현 순서

 

EnQueue 함수 구현

void EnLQueue(LQueue_Struct *lqueue, int data)
{
	lqueue->rear = (LinkedList*) malloc(sizeof(LinkedList));  //1번

	lqueue->rear->data = data; //2번

	lqueue->body->next = lqueue->rear; //3번

	lqueue->body = lqueue->rear; //4번

}

 

Queue에 데이터를 뺄 때

 

Queue에서 데이터를 뺄려고 보면 다음과 같은 그림으로 메모리는 잡혀 있다.

 

초기 메모리 구조

1. Delete Pointer 선언 후 FrontPointer와 같은 리스트를 나타내게 한다.

 

2. Front 포인터를 다음 리스트로 이동한다.

 

3. Delete 포인터를 해제한다.

 

4. Front Pointer의 데이터를 Return 한다.

 

 

DeQueue 함수 구현

int DeLQueue(LQueue_Struct *lqueue)
{
	LinkedList *DelList;

	DelList = lqueue->front;   //1번

	lqueue->front = lqueue->front->next;  //2번

	free(DelList); //3번

	return lqueue->front->data; //4번

}

 

이전에 공부 했듯이 Rear 포인터와 Front 포인터가 같으면 Queue는 텅 비어있다

따라서 데이터를 집어넣고 Rear 포인터와 Front 포인터가 같을 때 까지 데이터를 출력시켰다.

 

main 함수 구현

int main(void)
{
	LQueue_Struct LQueue;

	LQueue_init(&LQueue);

	EnLQueue(&LQueue, 10);
	EnLQueue(&LQueue, 20);
	EnLQueue(&LQueue, 30);
	printf("Deleted Data is %d \r\n", DeLQueue(&LQueue));
	EnLQueue(&LQueue, 40);
	EnLQueue(&LQueue, 50);
	EnLQueue(&LQueue, 30);
	EnLQueue(&LQueue, 40);

	printf("Start\r\n");

	while(LQueue.front != LQueue.rear)
	printf("Deleted Data is %d \r\n", DeLQueue(&LQueue));

}

 

실행 결과