[C언어]44일차 - 순환큐 (이것이 C언어 자료구조&알고리즘)

[C언어]44일차 - 순환큐 (이것이 C언어 자료구조&알고리즘)

 

큐의 개념

큐의 삽입과 제거

순환 큐의 구조와 구현

링크드 큐의 구조와 구현

 

 

큐의 개념

큐는 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나오는 ADT 입니다.

 

 

큐의 삽입과 제거

큐의 가장 앞 요소를 전단이라고 하고, 가장 마지막 요소를 후단이라고 부릅니다.

 

 

삽입은 아래와 같이 후단에 노드를 덧붙여서 새로운 후단을 만드는 연산이다.

 

 

 

제거는 다음과 같이 전단의 노드를 없애서 전단 뒤에 있는 노드를 새로운 전단으로 만드는 연산을 말한다.

 

 

 

기존 큐의 문제점

 

기존 큐의 문제점은 전단의 데이터를 제거하면 뒤쪽의 데이터를 앞으로 한칸씩 이동 시켜야 된다는 점이다.

 

해결책으로는 전단을 가리키는 변수를 하나 만들어서 배열의 요소를 이동시키지 말고 전단의 index만 이동시킨다.

 

 

후단을 가리키는 변수에는 실제 후단의 위치 + 1 한 값을 담는다.

 

삽입이 이루어질 때 후단이 가리키는 위치에 데이터를 바로 입력하면 되도록 처리한다.

 

 

장점 : 배열 요소들의 이동으로 인한 부하 문제를 해결할 수 있다.

단점 : 제거 연산을 수행할 때마다 큐의 가용 용량도 줄어든다.

순환 큐의 구조와 구현

 

순환 큐는 아래와 같이 생겼다.

 

 

배열의 끝과 시작을 연결했다고 가정하고 8과 9를 각각 삽입해보기

 

배열의 마지막 요소가 후단이었을 때 8을 삽입했다. (배열의 첫번째 요소가 후단이 되었다.)

 

여기서 9를 삽입함으로써 배열의 두 번째 요소가 후단이 되었다.

 

삽입이 이루어질 때마다 후단이 뒤로 후퇴하다가 전단을 만나면 큐는 '가득 찬 상태' 가 된다.

 

시작과 끝을 연결해서 효율적인 삽입/삭제 연산이 가능하도록 고안된 큐를 순환 큐라고 한다.

 

 

순환 큐의 문제점

 

공백상태일때와 포화상태일때 모두 전단,후단이 같은 위치에 있다.

 

 

문제 해결 방법은 큐 배열을 생성할 때 실제 용량보다 1만큼 더 크게 만들어서 전단과 후단(실제후단) 사이를 비우는 것이다.

 

이렇게 하면 큐가 공백 상태일 때, 전단과 후단이 같은 곳을 가리키고,

 

큐가 포화상태일 때 후단이 전단 보다 1작은 값을 가지므로 구분이 용이 해진다.

 

순환큐의 기본 연산

 

순환 큐 선언

 

 

순환큐를 나타내는 CircularQueue 구조체는 Queue의 용량(capacity) 전단의 위치(Front) , 후단의 위치(Rear) 순환 큐 요소의 배열에 대한 포인터를 갖고 있다.

 

 

CircularQueue 구조체의 Nodes 포인터가 가리키는 배열은 다음 그림과 같이 자유 저장소에 생성된다.

 

 

Capacity는 순환 큐의 용량, 즉 Nodes 배열의 크기를 나타내는데 실제로 Nodes를 메모리에 할당할 때는 Capacity + 1 만큼의 크기를 할당한다.

 

노드 하나를 공백/포화 상태 구분용 더미 노드로 사용하기 때문이다.

 

Front는 전단 위치를 Rear는 후단 위치를 가리킨다.

 

이들이 갖는 값은 실제 메모리 주소가 아니라 배열 내의 인덱스이다.

 

Rear는 실제 후단보다 1 더 큰 값을 갖는다는 사실을 기억해야 한다.

 

 

순환큐 생성

 

 

순환큐 제거

 

 

노드 삽입 연산

 

순환 큐에서 삽입 연산 구현은 후단의 위치를 가리키는 Rear를 다루는 것이 핵심이다.

 

if 블록에서 Rear의 값이 *Queue->Capacity + 1 과 같은 값이라면 후단이 배열 끝에 도달했다는 의미이므로

Rear와 Position을 0으로 지정한다.

 

그렇지 않은 경우(후단이 배열 끝에 도달하지 않은 경우) else 블록으로 넘어가서 현재 Rear의 위치를 Position에 저장하고 Rear의 값을 1증가 시킨다.

 

 

 

노드 제거연산

 

노드 제거 연산에서는 Front를 잘 관리해야 한다.

 

이 코드에서는 가장 먼저 전단의 위치를 Position에 저장한다.

 

Position은 큐의 전단에 저장되어 있던 데이터를 반환할 때 Nodes 배열의 인덱스로 사용되는 변수이다.

 

front의 값이 capacity와 같을 때,

 

즉 전단이 배열 끝에 도달한 경우 front를 0으로 초기화 하고,

 

그렇지 않은 경우, front를 1만큼 증가 시킨다.

 

 

 

공백 상태 확인

 

전단과 후단의 값이 같으면 공백 상태라는 의미다.

 

포화 상태 확인

 

먼저 두가지 상황을 고려해야 한다.

 

1. 전단이 후단 앞에 있을때

 

후단과 전단의차 (Rear - Front) 가 큐의 용량 (Capacity)과 동일하면 큐는 포화상태다.

 

2.후단이 전단 앞에 있을때

 

전단이 후단과 같은 위치 또는 뒤에 있고 후단에 1을 더한 값이 (Rear + 1)이 전단(Front)과 동일한 때.