[Programming] Queue: 원형 큐(Circular Queue) 단계별 과정

 Queue: 원형 큐(Circular Queue) 추가 설명 #01

 

Q: 공식만 봐서는 이해가 되지 않아서 원형 큐 추가 설명해주세요.

---

앞선 큐(Queue) 관련 포스트에서 Linear Queue와 Circular Queue에 대해서 살펴보았다.

[Programming] Queue(큐): 선형 큐(Linear Queue), 원형 큐(Circular Queue)

Bro 중에서 원형 큐에 대해서 구현 과정을 보여줬으면 좋겠다는 요청이 있어서 원형 큐에 대해서 조금 더 살펴보자.

 

원형 큐 공식: (rear+1)% arraysize == front, front == rear

원형 큐에 대해서 이해하기 위해서는 2가지 공식을 알고 정확히 알고 있으면 된다. 일단 원형 큐라는 것이 선행 큐의 단점을 보완한 방식의 큐라는 건 저번 포스트에서 살펴보았다. 문제는 원형 큐가 작동하기 위해서는 공백이 존재해야 한다는 것이다. 공백이 존재하는 이유는 해당 공백이 원형 큐에 데이터가 꽉 찬 상태, 즉 포화 상태인지 아니면 공간이 남아 있는 상태인지를 확인해주는 역할을 수행하기 때문이다. 이를 토대로 Enqueue와 Dequeue가 이루어진다. 이렇게 말로 표현한 공식이 바로 (rear+1)% arraysize == front, front == rear 이 2가지 공식을 의미한다. 조금 더 구체적으로 이야기를 해보자면, 일단 front는 앞부분의 데이터를 의미하고 rear는 뒷부분을 의미한다. Linear queue에서 앞과 뒤가 존재하듯이 원형 큐이지만 임의로 앞과 뒤라는 부분을 설정해준 셈이다.

front == rear

front == rear는 앞과 뒤가 같은 위치에 존재한다고 이해할 수 있다. front와 rear가 같은 공간을 나타 낸다는 것이다. front와 rear가 같다는 의미는 원형 큐의 변화가 필요하다는 걸 나타내는데, 원형 큐가 공백인 상태이거나 포화인 상태일 때 front == rear 조건이 성립한다.

Enqueue

(rear+1)% arraysize == front은 원형 큐의 데이터를 입력할 때 사용하는 공식이다. rear의 위치에 1을 더해주고 전체 배열 사이즈에 module를 하고 나서 front와 같은지를 비교한다. front와 같지 않다면 데이터는 추가가 되며, 해당 공식에서 rear와 front가 같아질 때까지 반복하여 데이터를 입력한다. 한마디로 Enqueue가 이루어진다고 보면 된다.

 

Dequeue

(rear+1)%arraysize == front 결과가 성립이 된다면 더 이상 Enqueue가 이뤄지지 않는다. 왜냐하면 공식을 적용한 결과 원형 큐가 포화 상태라는 걸 알 수 있기 때문이다. 따라서 front == rear가 되어버리면 포화 상태로써 Enqueue에서 Dequeue로 전환된다. Dequeue는 front == rear가 다시 될 때까지 이루어진다.

 

아래의 예제를 통해 단계별 변화하는 원형 큐를 살펴보면 이해가 훨씬 수월하다.

---

4개의 arraysize를 가지고 있다.

---

array index가 표기되어져 있다.

---

Index 0에서 front와 rear 모두 시작한다.

---

(rear+1)% arraysize == front 조건 성립하지 않기 때문에 Enqueue가 일어난다.

---

(rear+1)% arraysize == front가 성립되지 않아 추가 Enqueue 성립한다.

---

(rear+1)% arraysize == front가 성립하지 않아 Index 3까지 데이터가 추가된다.

---

(3+1)% 4== 0이기 때문에 포화상태이므로 Enqueue -> Dequeue로 전환된다.

---

Front = Rear가 성립될때까지 반복한다.

---

Front = Rear임으로 Dequeue에서 Enqueue로 전환된다.

---