큐 - 원형 큐

1. 선형 큐 이용시의 문제점

앞서서 큐(Queue) 즉, 선형 큐에 대해서 배웠습니다.(2024.06.02 - [알고리즘] - 큐(Queue))

1-1. 잘못된 포화상태 인식

선형 큐를 이용하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불고하고, rear = n - 1인 상태 즉, 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게 됩니다.

---

1-2. 해결방법 1

매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시킵니다.

원소 이동에 많은 시간이 소요되어 큐의 효율성이 급격히 떨어집니다.

---

1-3. 해결방법 2

1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용합니다.

원형 큐의 논리적 구조입니다.

---

2. 원형 큐의 구조

2-1. 초기 공백 상태

front = rear = 0

---

2-2. Index의 순환

• front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야합니다.
• 이를 위해 나머지 연산자 mod를 사용합니다.

---

2-3. front 변수

 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리도 둡니다.

---

---

3. 원형 큐의 연산 과정

---

---

---

4. 원형 큐의 구현

4-1. 초기 공백 큐 생성

• 크기 n인 1차원 배열을 생성합니다.
• front와 rear를 0으로 초기화합니다.

---

4-2. 공백상태 및 포화상태 검사 : isEmpty(), isFull()

---

4-3. 삽입 : enQueue(item)

---

4-4. 삭제 : deQueue(), delete()