자료구조 5. 순환 큐

큐 : FIFO를 구현한 자료구조 

-> 퍼스트 인 퍼스트 아웃 

 

기본적으로, AWS 공부 당시, SQS 등의 서비스에서 

중요하게 접한 개념이라, 받아들이는 게 전혀 어렵지 않았다. 

 

스택은 인/아웃이 일어나는 주소 자료구조가 Top만 추종하면 되었지만,

큐는 인과 아웃의 주소가 다르므로, Front/Rear를 동시 추종하게 설계된다. 

 

---

배열을 이용한 큐 -> 순환 큐 

 

배열은 시작점과 끝이 있으므로, 전단에서 Dequeue가 일어날 때 마다,

Enqueue가 가능한 가용영역이 점점 좁아진다는 문제가 있다.

따라서, 일반 배열은 큐 구조로 구현할 수가 없다.

 

1. 

이 문제를 해결하기 위해서, 마지막 노드가 첫 노드를 가리키도록

순환 큐를 만듦으로써 해결 할 수 있다. 

 

2. 

한 가지 더 문제가 남아있는데, 바로 순환 큐가 가득 찼을 때,

또 순환 큐가 완전 비었을 때, 상태 구분이 어렵다는 점이다. 

이런 문제를 해결하기 위해서, 실제 큐 용량을 하나 더 늘려 더미노드를 활용한다. 

Front는 큐의 시작 노드를 가리키고,

Rear는 항상 순환 큐가 끝나고 다음 노드인 더미노드를 가리키게 설정한다.

---

순환큐는 아래 요소를 갖는다.

- Front

- Rear

- Capacity 

- 노드 주소 

 

Front / Rear는 큐라는 자료 구조형이 갖는 특성이고,

Capacity는 순환큐 특성상 미리 지정되어야 하는 값이 된다. -> 더미노드까지 계산해야하므로

노드 주소는 순환큐의 첫 주소를 조회하는 데 사용되며

한편으로, 노드와 순환큐의 자료형을 별도로 구분하여

탄력적인 코드 운용을 가능하게 하기 위함이다. 

 

 

GitHub - Sukmin-LanternK/Data_Structure_Queue