자료구조 - 큐(배열 기반)

큐란 가장 먼저 들어간 것이 가장 먼저 나오는 특성을 가진 자료구조를 말한다.

다음 그림처럼 먼저 들어간 Data는 나올 때 가장 먼저 나온다.

이러한 구조를 First In First Out(FIFO) 또는 Last In Last Out(LILO) 라 한다.

 

큐의 ADT는 다음과 같은 연산들을 정의한다.

- 큐에 데이터를 넣는 연산 enqueue

- 큐에서 데이터를 꺼내는 연산 dequeue

 

---

● enqueue 연산 방식

다음 그림은 길이가 4인 배열 대상의 enqueue 연산을 보이며

여기서 F는 Front 를 의미하고 R은 Rear 를 의미하는데

새 데이터는 Rear 부분에 저장되고 R은 그 다음 칸을 가리키게 된다.

 

 

 

● 일반적이지 않은 dequeue 방식

위 그림에서 보이는 방식은 dequeue 연산 시 데이터를 앞에서부터 삭제를 하는 방식으로 

연산 시마다 저장된 데이터를 한 칸씩 이동시켜야 하는 단점이 있다.

따라서 배열 기반의 큐에서는 위의 방식으로 dequeue 연산을 진행하지 않는다. 

 

 

 

● 일반적인 dequeue 방식

위 dequeue 방식은 연산 시 F를 이동시키고 있다. 이 방식을 취하게 되면 dequeue 과정에서 데이터의 이동이 필요치 않다.

하지만 이 방식도 완전하지는 않다. 다음과 같은 경우가 발생하기 때문이다.

 

다음 그림처럼 문자 D가 배열 끝에 저장된 상태인데

이 경우 더 이상 R을 오른쪽으로 이동시킬 수 없기에 enqueue 연산을 진행시킬 수 없게 된다.

 

 

따라서 원형 큐라는 것을 구현하면 이 문제를 해결할 수 있다.

원형 큐에서는 새로운 데이터가 enqueue 될 때마다 R이 새 데이터를 가리키는 식이 된다.

(즉 R은 뒤로 한 칸씩 밀려남)

 

 

다음 그림은 dequeue 연산을 할 때 F가 가리키는 데이터는 반환되고 F는 그 다음 데이터를 가리키는 식이다. 

(즉 F는 R로 한 칸씩 접근함)

 

이처럼 데이터가 꽉 찬 원형 큐와 텅 빈 원형 큐는 F가 R보다 한 칸 앞서 있다는 것을 알 수 있는데

이런 경우 F와 R의 위치만 가지고서는 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없다.

 

 

이에 대한 해결책으로 배열을 꽉 채우지 않고

배열의 길이가 N이라면 데이터가 N-1 개가 채워졌을 때 이를 꽉 찬 것으로 간주한 경우의 그림이다. 

 

 

위에서 말한 것처럼 enqueue 연산으로 인해 원형 큐가 꽉 찬 상황이다.