[Queue개념] Queue/원형 Queue

Queue의 특징

---

 

FIFO -> 선입선출 구조를 가지고 있다. 

enqueue: 데이터를 넣는 행위

dequeue: 데이터를 빼는 행위 

 

원형 Queue

---

 

- 큐의 용량을 정하고, 원소를 넣어준다.

- 큐의 맨 앞을 front, 큐의 맨 뒤를 rear라고 한다.

- 원형 큐를 Linear구조로 만들어야 하고, 이때 사용되는 것이 array이다.

 

큐의 용량이 6이고 , 배열에 3,5,7이 있다. 여기에 2,4,6,8이 enque되려고 한다.

 

 

이렇게 되면 3이 있는자리에 8이 들어오면서 overflow가 발생한다. 

 

이를 해결하기 위해서는 인덱스의 나머지를 이용하는 방법이 있다. 

 

아까와 마찬가지로 먼저 배열과 원형큐에 1,3,5,7을 넣는다.

 

이 상태에서 2번 deque를 해준다. 

 

이 상태에서 2,4,6을 enque해주면

원형큐의 경우

문제는 배열에서 나타나게 된다.

 

 

6을 넣으려 할 때, 배열의 끝을 넘어가게 된다. 이때는 숫자 6의 인덱스가 0번째로 돌아가서 0번째 인덱스에 6이 들어간다. 여기서 규칙을 찾아볼 수 있다. 6번째 인덱스인 숫자 6을 큐의 전체용량인 6으로 나눴을 때의 나머지가 0이고, 이것이 숫자 6이 들어간 큐의 인덱스이다.

 

정리하자면 인덱스 = (원소가 들어온 차례) %(큐의 용량) 으로 생각하면 된다.