[자료구조] 큐(Queue), 원형 큐(Circular Queue)

shj718 2021. 10. 9. 16:33

큐(Queue)는 FIFO(First In First Out = 선입선출) 구조를 가진다.

큐의 사이즈가 N이고, 위와 같은 초기 상태를 가질 때

- 큐가 꽉 찬 상태: rear==N-1

- 큐가 비어 있는 상태: front==rear (원소의 개수 = rear - front 가 0)

- 삽입: rear+1 을 한 뒤에 그 자리에 원소를 삽입

- 삭제: front+1 을 한 뒤에 그 자리의 원소를 삭제

앞이 비어있음에도 불구하고, rear==N-1이 되어 큐가 꽉 찬 상태로 인식된다. (더 이상 삽입이 불가능하다.)

원형 큐는 앞서 말한 큐의 단점을 보완한 구조이다.

- 큐가 꽉 찬 상태: (rear+1)%N==front (비어 있는 상태와 구분하기 위해 한 칸이 비었을 때를 꽉 찬 상태로 본다.)

- 큐가 비어 있는 상태: front==rear

- 삽입: (rear+1)%N 자리에 원소를 삽입

- 삭제: (front+1)%N 자리의 원소를 삭제

- 주의할 점: 선형 큐에서는 배열의 인덱스로 원소의 개수를 나타낼 수 있었지만(위의 선형 큐 예시에서 'rear-front'), 원형 큐에서는 원소의 개수를 나타내는 변수를 따로 선언해서 관리해야 한다.