큐(Queue) & 환원큐 Circular Queue

큐, 환원큐 모두 양방향 리스트 또는 배열로 구현 할 수 있는데

*리스트로 짤 경우 양방향리스트로 구성해야 한다

배열로 하면 배열값을 밀어내야 하는 상황이 발생 함으로

양방향 리스트로 만드는 것이 일반적으로 효율적이다

환원큐가 비었을 때는 front == real 이며

꽉 찾을때는 하나의 공간을 두고 front 와 real 이 1 간격으로 배치하게 된다

real 에서 데이터 추가, front 에서 데이터 빼온다

real 에 추가시 현재 가르키고 있는 곳에 데이터를 추가 한 후 real++

front 에서는 현재 가르키고 있는 곳에서 데이터를 빼낸 후 front++

그냥 front의 값만 가져오려면 {리스트&배열}[ front ] 의 값을 가져오고

(+ 가 순방향이라고 가정했을때)

real 의 값만 가져오려면 {리스트&배열}[Dec(real-1 )] 을 가져오면 된다

환원큐의 인덱싱은 % 를 활용

m_size 가 배열 사이즈 만약 10 이라고 한다면

현재 가르키는 곳의 다음 번지를 알기 위하여

가르키는 곳 n 에 +1 을 한 후

전체 사이즈로 나누면 배열 사이즈 버위 내에서

순환하는 인덱스 번호를 얻어올 수 있다

감소 ( Dec() )는 (n-1) % m_size;