큐(Queue)

큐란?(What is Queue)

---

 큐(Queue)는 데이터가 들어가는 곳과 나가는 곳이 한 곳으로 정해져있는 자료 구조를 말한다. 매표소에 사람들이 줄을 서 있으면 먼저 온 순서대로 표를 구매하게 된다. 큐는 먼저 온 데이터를 먼저 처리하는 형태를 띈다. 이를 FIFO(First-In-First-Out) 또는 LILO(Last-In-Last-Out)이라고 한다. 둘 다 맞는 표현이지만 FIFO를 더 많이 사용한다.

 

 큐에서 데이터가 삽입되는 부분을 rear라고 하고 데이터가 삭제되는 곳을 front라고 한다. rear가 가리키는 데이터는 가장 최근에 삽입된 데이터이고 front가 가리키는 데이터는 가장 먼저 삽입된 데이터이다.

 

큐(Queue)

 

 

큐의 연산(Queue Operation)

---

큐의 기본 연산은 다음과 같다.

• Enqueue(Q, D) : 큐 Q에 데이터 D를 삽입한다.
• Dequeue(Q) : 큐 Q에서 1개의 데이터를 삭제한다.

 

큐의 삽입, 삭제 과정

 먼저 큐를 만들게 되면 front와 rear를 모두 -1로 맞추어 준다. Enqeue(Q, A)로 큐 Q에 A를 삽입한다. rear가 가리키는 위치에서 +1을 하여 다음 위치로 rear를 옮기고 rear가 가리키는 곳에 'A'를 삽입한다. 나머지도 같은 방식으로 B, C를 삽입하면 된다. 다음 Dequeue(Q)로 데이터를 삭제하게 된다. Dequeue도 Enqueue와 마찬가지로 현재 front가 가리키는 곳에서 +1을 한 다음 front가 가리키는 위치의 데이터를 삭제한다. 이렇게 삽입과 삭제를 하다보면 마지막 경우처럼 front와 rear가 서로 같은 상황이 오는데 이는 큐가 공백상태임을 알려준다. 여기서 한 가지 문제점이 생긴다. 위 예시에서도 보이듯이 큐가 공백상태일 때 front와 rear는 큐의 중간을 가리키고 있다. 그리고 Dequeue와 Enqueue의 연산에는 오직 증가하는 방향으로만 연산을 진행하게 되어있다. 이는 rear와 front가 queue의 마지막을 가리키면서 공백상태를 나타내면 더이상 큐를 사용할 수 없다는 뜻이다. 그러면 우리는 해결책으로 front의 왼쪽에 공간이 없도록 꽉채우는 방법을 쓰거나 공백이 될때마다 초기화를 해주는 방법을 쓸 수 있다. 하지만 전자는 데이터가 많은 상황이면 데이터를 옮길 때 상당히 많은 시간이 소요되며, 후자 또한 항상 공백여부를 체크해야하기 때문에 처리속도가 느려질 수 밖에 없다. 이런 문제를 해결하기 위한 방법으로 제시된 것이 원형큐(Circular Queue)이다.

 

 

원형 큐란?(What is Circular Queue)

---

원형 큐(Circular Queue)는 물리적으로는 선형 구조를 띄고 있지만 논리적으로 큐의 시작점과 끝점을 연결한 원형 연결 구조이다. 큐의 시작점과 끝점은 다음과 같은 방법으로 이을 수 있다.

 

rear = (rear + 1) % (size of queue)

front = (front + 1) % (size of queue)

 

앞서 Enqueue와 Dequeue를 할 때 rear와 front를 1씩 증가시키는 연산을 해주었다. 이 증가시키는 연산을 위 식으로 대체해주면 큐의 마지막에서 증가연산을하면 다시 처음으로 돌아오게 된다. 이해가 안된다면 숫자를 통해 예시를 보이겠다. 큐의 사이즈가 8이라고 가정한다면 큐의 인덱스는 0 ~ 7까지이다. 여기서 rear가 7을 가리키고 있을 때 1을 증가하는 연산을 하게 되면 8 mod 8 = 0이기 때문에 다시 큐의 처음 인덱스인 0번 인덱스로 돌아오게 된다.

 

 

원형 큐의 연산(Circular queue Operation)

---

원형 큐의 연산은 위에서 설명한 약간의 식의 변형이 생기는 것과 논리적 구조가 변형된 것을 제외하면 선형 큐의 연산과 다르지 않다. 다음은 원형 큐의 연산을 그림으로 나타낸 것이다.(첫번째 그림과 두번째 그림의 front의 값은 -1이나 이해를 위해 7번 인덱스를 가리키도록 하였다.)

 

큐의 삽입, 삭제 과정

 

위 그림에서 마지막은 포화 상태의 큐를 나타낸 것이다. 포화 상태임에도 마지막 인덱스의 값이 비어있는 것을 보면 자연스레 궁금증이 생긴다. 이는 큐의 포화 상태와 공백 상태를 구분하기 위함인데 선형 큐에서는 공백과 포화를 나타내는 조건이 달랐지만 원형 큐에서는 큐를 모두 채우는 순간 공백과 포화를 구분할 수 없다. 마지막 그림에서 rear를 1개만 더 증가시켜도 rear==front가 된다. 그렇기 때문에 rear + 1 == front이면 포화상태로 rear == front이면 공백상태로 정의한다. 물론 모든 공간을 채워서 사용할 수 있는 방법은 있다. 값을 채운 후 포화상태를 검사할 때 front앞의 값이 있는지 확인하면 된다. 하지만 검사를 계속하기에는 추가적인 연산이 필요할 뿐 아니라 실제 front를 움직이면 안되기 때문에 임시의 front값을 할당하여 검사를 진행해야하는데 이는 추가적인 공간을 위해 도입한 방법이 오히려 공간적, 시간적 손해가 생기게 된다.

 

 

큐의 응용(Queue Application)

---

큐는 다음과 같은 방법으로 사용되어질 수 있다.

1. CPU의 작업 스케쥴링 (CPU task scheduling)
2. 인터럽트 핸들링(interrupt handling)
3. 버퍼(buffer)
4. 음악 플레이 리스트에서 반복 재생하는 경우(원형 큐)

 

큐의 구현

---

구현은 아래 필자의 깃허브에 있으니 참고하길 바란다. 기본적인 원리만 구현을 했기 때문에 실제 사용에는 무리가 있다.참고만 하길 바란다.

GitHub - LimeTree0/Data-Structure