(C언어)연결 리스트로 큐 구현해 보기[자료구조]

 

(C언어) 연결 리스트(1) [자료구조]

(C언어) 연결 리스트(1) [자료구조]

연결 리스트로 큐를 구현해 보자.

배열로 구현한 큐

큐를 배열로 구현했을 때의 모습이다. 배열로 구현했기 때문에 크기가 제한됐었다.

연결 리스트로 큐를 구현해 본다면 어떤 모습일까??

 

연결리스트로 구현한 큐

위와 같은 모습이 될 것이다. 쉽게 생각하면 단순 연결 리스트에다 Front, Rear 2개의 포인터를 추가한 것이다. Front는 삭제, Rear에는 추가 혹은 삽입이 관련된다. 이렇게 연결 리스트로 구현한다면 코드가 보다 복잡해지고 링크 필드로 인해 메모리 공간 차지가 클 수 있다.

​

C언어로 직접 구현해 보자.

---

##함수

1. 리스트 구조체의 선언

-> 큐의 특성에 맞게 Front, Rear 포인터를 추가하여 노드를 선언

2. init

->큐의 초기화 함수​

3. is_empty

-> 큐가 비어있는지 검사하는 함수

4. enqueue

-> 큐의 Rear(맨 뒤 요소)에 노드를 추가하는 함수

5. dequeue

-> 큐의 Front(맨 앞 요소)에 노드를 제거하여 반환하는 함수

6. print_queue

-> 큐의 요소들을 출력해 주는 함수

---

1) 리스트의 구조체 선언

typedef struct Node{
	int data;
	struct Node *link;
}Node; // 연결 리스트의 형태를 갖추기 위한 구조체

typedef struct{
	Node *front, *rear;
}Queue; // 큐의 형태를 갖추기 위한 구조체

기본적으로 연결 리스트의 형태를 갖추기 위한 구조체에다가 큐의 형태를 갖추기 위한 front, rear 포인터를 추가하였다. 쉽게 말하면 단순 연결 리스트에다 2개의 포인터만 추가했다고 봐도 무방하다. 연결 리스트로 스택을 구현했을 때 top 포인터와 역할이 같다.

2) init

void init(Queue *q)
{
	q->front = q->rear = NULL;
}

front와 rear 포인터를 NULL 값으로 초기화해준다. 

​3) is_empty

int is_empty(Queue *q)
{
	return (q->front == NULL);
}

큐가 비어있다면 front 포인터가 NULL 값 인지에 대한 참 거짓을 반환하게 한다. 큐의 맨 앞쪽 부분인 front가 NULL 값이라면 맨 후단 부분을 보지 않아도 큐는 비어있는 게 당연하기 때문이다.

 

4) enqueue

삽입 연산 같은 경우에는 경우를 나눠서 생각해야 한다.

 

i) 큐가 공백 상태인 경우

공백 상태인 경우 삽입 연산

공백 상태인 경우에 front, rear 포인터는 NULL 값이다. 그 상황에서 새로운 노드를 삽입하면 front, rear 모두 새로운 노드를 가리키도록 하면 된다.

 

ii) 큐가 공백 상태가 아닌 경우

공백 상태가 아닌 경우 삽입연산

큐가 공백 상태가 아니라면 연결 리스트에서 rear가 가리키는 노드의 링크가 삽입할 노드로 가게 한 후 rear을 새로운 노드를 가리키도록 한다.

void enqueue(Queue *q,int data)
{
	Node* temp = (Node *)malloc(sizeof(Node)); // 삽입할 노드 동적 선언
	temp->data = data; // 삽입할 데이터 복사
	temp->link = NULL; // rear부분 즉 큐의 마지막에 들어가므로 새로운 노드의 링크부분은 NULL이여야 한다.
	if(is_empty(q)) // 큐가 비어있는 경우
	{
		q->front = temp; 
		q->rear = temp; // front,rear모두 새로운 노드를 가리키도록 함
	}
	else // 큐가 비어있지 않는 경우
	{
		q->rear->link = temp; // rear노드의 링크가 삽입할 노드를 가리키도록 함
		q->rear = temp; // rear포인터를 삽입할 노드를 가리키도록 선언
	}
}

5) dequeue

삭제 연산은 노드의 개수가 1개인 경우와 공백 상태가 아닌 여러 개로 연결된 경우로 나와서 생각해 봐야 한다.

 

i) 노드의 개수가 1개인 경우

노드가 1개인 경우 삭제연산

노드가 하나인 경우에는 front, rear 모두 다시 NULL 값을 가지는 공백 상태가 된다.

 

ii) 공백 상태가 아니고 노드가 여러 개인 경우

 

노드가 여러 개인 경우 삭제 연산

연결 리스트에서 삭제하는 방식과 같으며 마지막에는 front를 이전 front가 가리키던 노드를 가리키도록 하면 된다.

int dequeue(Queue *q)
{
	Node *temp; //삭제할 노드를 위한 임시 노드 선언
	int data;
	if(is_empty(q)) // 큐가 공백상태인지 검사
	{
		printf("error");
	}
	else{
		temp = q->front; // temp가 q->front 노드 가리킴
		data = temp->data;
		q->front = temp->link; // front가 다음 노드를 가리키도록 함( 삭제후 첫번째 노드가 될 노드)
		if(q->front==NULL) // 공백상태를 만들어 주기 위함
			q->rear ==NULL;
		free(temp); // 동적메모리 해제
		return data; // 데이터 반환
	}
}

6) print_queue

void print_queue(Queue *q)
{
	Node *p;
	for(p=q->front;p!=NULL;p=p->link)
		printf("%d->",p->data);
	printf("NULL\n");
}

front부터 NULL이 아닐 때까지(rear까지) 출력하도록 하는 함수이다.

---

int main()
{
	Queue que; 
	
	init(&que); // 초기화 
	
	enqueue(&que,10); print_queue(&que); // 10 삽입
	enqueue(&que,30); print_queue(&que); // 30 삽입
	enqueue(&que,40); print_queue(&que); // 40 삽입
	enqueue(&que,60); print_queue(&que); // 60 삽입
	dequeue(&que); print_queue(&que); // 10 삭제
	dequeue(&que); print_queue(&que); // 30 삭제
	dequeue(&que); print_queue(&que); // 40 삭제
	dequeue(&que); print_queue(&que); // 60 삭제
	return 0;
}

다음과 같이 메인 함수를 실행해 보자.

결괏값을 보면 큐가 잘 실행됨을 알 수 있다. 배열로 구현한 큐와 차이점을 느끼면서 공부해보자.